Range query (computer science)
কম্পিউটার বিজ্ঞানে, পরিসীমা অনুসন্ধান সমস্যা একটি অ্যারের মধ্যে উপাদানগুলির একটি নির্দিষ্ট ব্যবধান সম্পর্কিত বেশ কয়েকটি প্রশ্নের দক্ষতার সাথে উত্তর দিয়ে গঠিত। উদাহরণস্বরূপ, একটি সাধারণ কাজ, যা ন্যূনতম পরিসর অনুসন্ধান নামে পরিচিত, হল সংখ্যার তালিকার মধ্যে প্রদত্ত পরিসরের মধ্যে ক্ষুদ্রতম মান খুঁজে বের করা। সংজ্ঞা একটি অ্যারে গ্রহণ করে এমন একটি ফাংশন দেওয়া, একটি অ্যারেতে একটি পরিসীমা অনুসন্ধান দুটি সূচক নেয় এবং সাব-অ্যারেতে প্রয়োগ করার সময় ফলাফল প্রদান করে। উদাহরণস্বরূপ, একটি ফাংশনের জন্য যা একটি অ্যারেতে সমস্ত মানের যোগফল প্রদান করে, পরিসীমা অনুসন্ধান পরিসীমার সমস্ত মানের যোগফল প্রদান করে। সমাধান উপসর্গ সমষ্টি অ্যারে পরিসর সমষ্টি প্রশ্নের উত্তর স্থির সময় এবং রৈখিক স্থানে ইনপুটের মতো একই দৈর্ঘ্যের একটি অ্যারে প্রাক-গণনা করে দেওয়া যেতে পারে যাতে প্রতিটি সূচকের জন্য, উপাদানটি এর প্রথম উপাদানগুলির সমষ্টি হয়। যে কোনও প্রশ্ন তারপর নিম্নরূপ গণনা করা যেতে পারেঃ এই কৌশলটি অন্য যে কোনও বাইনারি ক্রিয়াকলাপে প্রসারিত করা যেতে পারে যার বিপরীত ফাংশনটি ভালভাবে সংজ্ঞায়িত এবং সহজেই গণনাযোগ্য। এটি অনুরূপ প্রাক-প্রক্রিয়াকরণের সাথে দ্বি-মাত্রিক অ্যারেগুলিতেও প্রসারিত করা যেতে পারে। গতিশীল পরিসীমা প্রশ্ন সমস্যার একটি আরও কঠিন উপসেট গতিশীল ডেটাতে পরিসীমা প্রশ্নগুলি কার্যকর করে; অর্থাৎ, ডেটা যা প্রতিটি প্রশ্নের মধ্যে পরিবর্তিত হতে পারে। অ্যারে মানগুলি দক্ষতার সাথে আপডেট করার জন্য, সেগমেন্ট ট্রি-র মতো আরও পরিশীলিত ডেটা কাঠামো প্রয়োজন। উদাহরণ সেমিগ্রুপ অপারেটর যখন একটি রেঞ্জ ক্যোয়ারিতে আগ্রহের ফাংশনটি একটি সেমিগ্রুপ অপারেটর হয়, তখন এর ধারণাটি সর্বদা সংজ্ঞায়িত হয় না, তাই পূর্ববর্তী বিভাগের কৌশলটি কাজ করে না। অ্যান্ড্রু ইয়াও দেখিয়েছেন যে সেমিগ্রুপ অপারেটরদের জড়িত পরিসীমা প্রশ্নের জন্য একটি কার্যকর সমাধান রয়েছে। তিনি প্রমাণ করেছেন যে যে কোনও ধ্রুবকের জন্য, সময় এবং স্থানের একটি প্রাক-প্রক্রিয়াকরণ তালিকার পরিসীমা প্রশ্নের উত্তর দেওয়ার অনুমতি দেয় যেখানে সময়ে একটি সেমিগ্রুপ অপারেটর, যেখানে অ্যাকারম্যান ফাংশনের একটি নির্দিষ্ট কার্যকরী বিপরীত। কিছু সেমিগ্রুপ অপারেটর রয়েছে যারা সামান্য ভাল সমাধান স্বীকার করে। উদাহরণস্বরূপ, কখন। ধরে নিন তারপর এর ন্যূনতম উপাদানটির সূচক প্রদান করে। তারপর সংশ্লিষ্ট ন্যূনতম পরিসীমা প্রশ্ন নির্দেশ করে। বেশ কয়েকটি তথ্য কাঠামো রয়েছে যা সময় এবং স্থানের প্রাক-প্রক্রিয়াকরণ ব্যবহার করে সময়ের মধ্যে একটি ন্যূনতম প্রশ্নের উত্তর দেওয়ার অনুমতি দেয়। এই ধরনের একটি সমাধান এই সমস্যা এবং সর্বনিম্ন সাধারণ পূর্বপুরুষ সমস্যার মধ্যে সমতুল্যতার উপর ভিত্তি করে। একটি অ্যারের কার্টেসিয়ান গাছের মূল এবং বাম ও ডানদিকে যথাক্রমে কার্টেসিয়ান গাছ এবং কার্টেসিয়ান গাছ রয়েছে। একটি ন্যূনতম পরিসীমা প্রশ্ন হল এবং-এর সর্বনিম্ন সাধারণ পূর্বপুরুষ। যেহেতু সর্বনিম্ন সাধারণ পূর্বপুরুষকে সময় এবং স্থানের প্রাক-প্রক্রিয়াকরণ ব্যবহার করে স্থির সময়ে সমাধান করা যেতে পারে, তাই ন্যূনতম প্রশ্নও হতে পারে। সমাধানটি যখন সাদৃশ্যপূর্ণ হয়। কার্টেসিয়ান গাছগুলি রৈখিক সময়ে তৈরি করা যেতে পারে। মোড একটি অ্যারের মোড হল সেই উপাদান যা এতে সবচেয়ে বেশি প্রদর্শিত হয়। উদাহরণস্বরূপ মোড হল। টাই হওয়ার ক্ষেত্রে, সবচেয়ে ঘন ঘন যে কোনও উপাদানকে মোড হিসাবে বেছে নেওয়া যেতে পারে। একটি রেঞ্জ মোড কোয়েরিতে প্রি-প্রসেসিং থাকে যাতে আমরা যে কোনও পরিসরে মোডটি খুঁজে পেতে পারি। এই সমস্যা সমাধানের জন্য বেশ কয়েকটি তথ্য কাঠামো তৈরি করা হয়েছে, আমরা নিম্নলিখিত টেবিলে কিছু ফলাফলের সংক্ষিপ্তসার করছি। সম্প্রতি জর্জেনসন এবং অন্যান্যরা। কোষ ব্যবহার করে এমন যে কোনও তথ্য কাঠামোর জন্য কোষ-অনুসন্ধান মডেলের উপর একটি নিম্ন সীমা প্রমাণিত হয়েছিল। মিডিয়ান এই বিশেষ ক্ষেত্রে বিশেষ আগ্রহ রয়েছে কারণ মিডিয়ান খুঁজে বের করার বেশ কয়েকটি প্রয়োগ রয়েছে। অন্যদিকে, মধ্যমা সমস্যা, নির্বাচন সমস্যার একটি বিশেষ ক্ষেত্রে, মধ্যমা অ্যালগরিদমের মধ্যমা ব্যবহার করে ও (এন)-এ সমাধানযোগ্য। তবে রেঞ্জ মিডিয়ান প্রশ্নের মাধ্যমে এর সাধারণীকরণ সাম্প্রতিক। একটি পরিসীমা মধ্যমা প্রশ্ন যেখানে A, i এবং j এর স্বাভাবিক অর্থ রয়েছে তার মধ্যমা উপাদানটি প্রদান করে। সমতুল্যভাবে, র্যাঙ্কের উপাদানটি ফেরত দেওয়া উচিত। সেমিগ্রুপ অপারেটরদের জন্য ইয়াওর পদ্ধতি সহ উপরে আলোচিত পূর্ববর্তী কোনও পদ্ধতি অনুসরণ করে রেঞ্জ মিডিয়ান প্রশ্নের সমাধান করা যায় না। এই সমস্যার দুটি রূপ নিয়ে গবেষণা করা হয়েছে, অফলাইন সংস্করণ, যেখানে আগ্রহের সমস্ত কে প্রশ্ন একটি ব্যাচে দেওয়া হয় এবং একটি সংস্করণ যেখানে সমস্ত প্রাক-প্রক্রিয়াকরণ সামনে করা হয়। অফলাইন সংস্করণটি সময় এবং স্থান দিয়ে সমাধান করা যেতে পারে। কুইক সিলেক্ট অ্যালগরিদমের নিম্নলিখিত সিউডোকোডটি দেখায় যে আমরা যে রেঞ্জ মিডিয়ানগুলি সেট করি তা খুঁজে বের করার জন্য কীভাবে স্বতন্ত্র উপাদানগুলির একটি অনির্ধারিত অ্যারেতে র্যাঙ্কের উপাদানটি খুঁজে বের করতে হয়। রেঞ্জ মিডিয়ান (এ, আই, জে, আর) {যদি A.length () = = 1 রিটার্ন এ [1] যদি A.low অনির্ধারিত হয় তবে এম = মিডিয়ান (এ) A.low = [ই ইন এ। ই <= এম] A.high = [ই ইন এ। ই> এম] গণনা করুন এ [আই, জে] এর উপাদানগুলির সংখ্যা যা A.low এর অন্তর্গত যদি আর <= টি রিটার্ন রেঞ্জ মিডিয়ান (A.low, আই, জে, আর) অন্যথায় রিটার্ন রেঞ্জ মিডিয়ান (A.high, আই, জে, আর-টি)} পদ্ধতি পার্টিশনগুলি, 'এস মিডিয়ান' ব্যবহার করে, দুটি অ্যারেতে এবং যেখানে পূর্ববর্তীটি রয়েছে যদি আমরা জানি যে সেই উপাদানগুলির সংখ্যা শেষ হয় এবং এই সংখ্যাটি তার চেয়ে বড় হয় তবে আমাদের র্যাঙ্কের উপাদানটি সন্ধান করা উচিত; অন্যথায় আমাদের র্যাঙ্কের উপাদানটি সন্ধান করা উচিত। খুঁজে বের করার জন্য, সর্বাধিক সূচকটি খুঁজে বের করা যথেষ্ট যেমনটি রয়েছে এবং সর্বাধিক সূচকটি যেমনটি রয়েছে। তারপর। পার্টিশন অংশটি বিবেচনা না করে যে কোনও প্রশ্নের জন্য মোট খরচ হল যেহেতু সর্বাধিক পুনরাবৃত্তিমূলক কল করা হয় এবং তাদের প্রত্যেকটিতে কেবলমাত্র একটি ধ্রুবক সংখ্যক অপারেশন করা হয় (ভগ্নাংশ ক্যাসকেডিংয়ের মান পেতে ব্যবহার করা উচিত)। যদি মিডিয়ানগুলি খুঁজে বের করার জন্য একটি রৈখিক অ্যালগরিদম ব্যবহার করা হয়, তবে রেঞ্জ মিডিয়ান প্রশ্নের জন্য প্রাক-প্রক্রিয়াকরণের মোট খরচ হল। সমস্যার অনলাইন সংস্করণ সমাধানের জন্য অ্যালগরিদমটিও সংশোধন করা যেতে পারে। সংখ্যাগরিষ্ঠ একটি নির্দিষ্ট জিনিসের মধ্যে ঘন ঘন উপাদান খুঁজে বের করা ডেটা মাইনিংয়ের সবচেয়ে গুরুত্বপূর্ণ কাজগুলির মধ্যে একটি। বেশিরভাগ আইটেমের একই ফ্রিকোয়েন্সি থাকলে ঘন ঘন উপাদানগুলি খুঁজে বের করা একটি কঠিন কাজ হতে পারে। অতএব, এই ধরনের জিনিসগুলি সনাক্ত করার জন্য যদি তাৎপর্যের কিছু সীমা ব্যবহার করা হয় তবে এটি আরও বেশি উপকারী হতে পারে। বেশিরভাগ অ্যারে খুঁজে বের করার জন্য সবচেয়ে বিখ্যাত অ্যালগরিদমগুলির মধ্যে একটি বোয়ার এবং মুর দ্বারা প্রস্তাবিত হয়েছিল যা বোয়ার-মুর সংখ্যাগরিষ্ঠ ভোট অ্যালগরিদম নামেও পরিচিত। বোয়ার এবং মুর একটি অ্যালগরিদম প্রস্তাব করেছিলেন যাতে একটি স্ট্রিংয়ের সংখ্যাগরিষ্ঠ উপাদান (যদি থাকে) সময়মতো খুঁজে বের করা যায় এবং স্থান ব্যবহার করা যায়। বোয়ার এবং মুরের কাজের প্রসঙ্গে এবং সাধারণভাবে বলতে গেলে, আইটেমগুলির একটি সেটের সংখ্যাগরিষ্ঠ উপাদান (উদাহরণস্বরূপ স্ট্রিং বা একটি অ্যারে) এমন একটি উপাদান যার দৃষ্টান্তের সংখ্যা সেই সেটের আকারের অর্ধেকেরও বেশি। কয়েক বছর পরে, মিশ্র এবং গ্রিস বোয়ার এবং মুরের অ্যালগরিদমের আরও সাধারণ সংস্করণের প্রস্তাব করেছিলেন যা একটি অ্যারেতে সমস্ত আইটেম খুঁজে বের করার জন্য তুলনা ব্যবহার করে যার আপেক্ষিক ফ্রিকোয়েন্সি কিছু প্রান্তিকের চেয়ে বেশি। একটি পরিসীমা-সংখ্যাগরিষ্ঠ প্রশ্ন হল এমন একটি প্রশ্ন যা একটি উপশ্রেণীর আকারের ডেটা স্ট্রাকচার (উদাহরণস্বরূপ একটি অ্যারে) দেওয়া হলে, সেই নির্দিষ্ট পরিসরে (বা কিছু প্রকাশনায় সমান) বারের চেয়ে বেশি প্রদর্শিত সমস্ত স্বতন্ত্র আইটেমের সেট প্রদান করে। বিভিন্ন কাঠামোতে যা পরিসীমা-সংখ্যাগরিষ্ঠ প্রশ্নগুলিকে সমর্থন করে, তা স্থির (প্রাক-প্রক্রিয়াকরণের সময় নির্দিষ্ট) বা গতিশীল (অনুসন্ধানের সময় নির্দিষ্ট) হতে পারে। এই ধরনের অনেক পন্থা এই সত্যের উপর ভিত্তি করে যে, সীমার আকার নির্বিশেষে, একটি প্রদত্ত ক্ষেত্রে অন্তত আপেক্ষিক ফ্রিকোয়েন্সি সহ সর্বাধিক স্বতন্ত্র প্রার্থী থাকতে পারে। এই প্রার্থীদের প্রত্যেককে স্থির সময়ে যাচাই করে, প্রশ্নের সময় অর্জন করা হয়। একটি পরিসীমা-সংখ্যাগরিষ্ঠ প্রশ্ন এই অর্থে বিচ্ছিন্ন করা যায় যে বিভাজন সহ একটি পরিসরে একটি-সংখ্যাগরিষ্ঠতা এবং উভয় বা উভয় ক্ষেত্রেই একটি-সংখ্যাগরিষ্ঠতা থাকতে হবে। এই ডিকম্পোসেবিলিটির কারণে, কিছু ডেটা স্ট্রাকচার রেঞ্জ ট্রি-তে কোয়েরি রেঞ্জের শেষ পয়েন্টগুলির সর্বনিম্ন সাধারণ পূর্বপুরুষ (এলসিএ) খুঁজে বের করে এবং প্রতিটি শেষ পয়েন্ট থেকে সর্বনিম্ন সাধারণ পূর্বপুরুষ পর্যন্ত দুই সেট প্রার্থীকে (আকারের) বৈধ করে এক-মাত্রিক অ্যারেতে সংখ্যাগরিষ্ঠ প্রশ্নের উত্তর দেয়, যার ফলে অনুসন্ধানের সময় হয়। দ্বি-মাত্রিক অ্যারে গ্যাগি এবং অন্যান্য। একটি ডেটা কাঠামো প্রস্তাব করা হয়েছে যা একটি অ্যারেতে পরিসীমা-সংখ্যাগরিষ্ঠ প্রশ্নগুলিকে সমর্থন করে। এই তথ্য কাঠামোর প্রতিটি প্রশ্নের জন্য একটি প্রান্তিক এবং একটি আয়তক্ষেত্রাকার পরিসীমা নির্দিষ্ট করা হয় এবং যে সমস্ত উপাদানের আপেক্ষিক ফ্রিকোয়েন্সি (সেই আয়তক্ষেত্রাকার পরিসীমার মধ্যে) এর চেয়ে বেশি বা সমান থাকে সেগুলির সেট আউটপুট হিসাবে ফেরত দেওয়া হয়। এই তথ্য কাঠামো গতিশীল সীমা (অনুসন্ধানের সময় নির্দিষ্ট) এবং একটি প্রাক-প্রক্রিয়াকরণ সীমা সমর্থন করে যার উপর ভিত্তি করে এটি নির্মিত হয়। প্রাক-প্রক্রিয়াকরণের সময়, অ্যারের উপর উল্লম্ব এবং অনুভূমিক ব্যবধানের একটি সেট তৈরি করা হয়। একসঙ্গে, একটি উল্লম্ব এবং একটি অনুভূমিক ব্যবধান একটি ব্লক গঠন করে। প্রতিটি ব্লক একটি সুপারব্লকের অংশ যা তার চেয়ে নয় গুণ বড় (ব্লকের অনুভূমিক ব্যবধানের তিনগুণ এবং উল্লম্বটির তিনগুণ আকার)। প্রতিটি ব্লকের জন্য প্রার্থীদের একটি সেট (সর্বাধিক উপাদান সহ) সংরক্ষণ করা হয় যা তার নিজ নিজ সুপারব্লকে কমপক্ষে আপেক্ষিক ফ্রিকোয়েন্সি (উপরে উল্লিখিত প্রাক-প্রক্রিয়াকরণ সীমা) রয়েছে এমন উপাদান নিয়ে গঠিত। এই উপাদানগুলি তাদের ফ্রিকোয়েন্সি অনুসারে অ-ক্রমবর্ধমান ক্রমে সংরক্ষণ করা হয় এবং এটি সহজেই দেখা যায় যে, যে কোনও উপাদান যার কমপক্ষে একটি ব্লকে আপেক্ষিক ফ্রিকোয়েন্সি রয়েছে তাকে অবশ্যই তার প্রার্থীদের সেট উপস্থিত করতে হবে। প্রতিটি সংখ্যাগরিষ্ঠ প্রশ্নের উত্তর প্রথমে প্রশ্ন ব্লক বা প্রদত্ত প্রশ্ন আয়তক্ষেত্রের মধ্যে থাকা সবচেয়ে বড় ব্লকটি খুঁজে বের করে দেওয়া হয়। প্রাপ্ত ক্যোয়ারি ব্লকের জন্য, প্রথম প্রার্থীরা সময়মতো ফিরে আসে (যাচাই না করে), তাই এই প্রক্রিয়াটি কিছু মিথ্যা পজিটিভ দিতে পারে। অন্যান্য অনেক তথ্য কাঠামো (নীচে আলোচনা করা হয়েছে) প্রতিটি প্রার্থীকে স্থির সময়ে যাচাই করার জন্য পদ্ধতিগুলি প্রস্তাব করেছে এবং এইভাবে কোনও মিথ্যা ইতিবাচক ফেরত না দিয়ে অনুসন্ধানের সময় বজায় রেখেছে। যে ক্ষেত্রে কোয়েরি ব্লকটি এর চেয়ে ছোট হয় সেগুলি নিম্নলিখিত ফর্মের এই ডেটা কাঠামোর বিভিন্ন দৃষ্টান্ত সংরক্ষণ করে পরিচালনা করা হয়ঃ-তম দৃষ্টান্তের প্রাক-প্রক্রিয়াকরণ সীমা কোথায়। সুতরাং,-তম দৃষ্টান্তের চেয়ে ছোট প্রশ্ন ব্লকের জন্য প্রশ্ন করা হয়। উপরে উল্লিখিত হিসাবে, এই তথ্য কাঠামোর অনুসন্ধানের সময় রয়েছে এবং এর একটি হাফম্যান-এনকোডেড অনুলিপি সংরক্ষণ করে কিছুটা জায়গার প্রয়োজন হয় (ফ্যাক্টরটি নোট করুন এবং হাফম্যান কোডিংও দেখুন)। এক-মাত্রিক অ্যারে চ্যান এট আল। একটি তথ্য কাঠামো প্রস্তাব করা হয়েছে যা একটি এক-মাত্রিক অ্যারে, একটি উপশ্রেণী (অনুসন্ধানের সময়ে নির্দিষ্ট) এবং একটি প্রান্তিক (অনুসন্ধানের সময়ে নির্দিষ্ট) দেওয়া হয়েছে, স্থানের শব্দের প্রয়োজনের সময় সমস্ত-সংখ্যাগরিষ্ঠের তালিকা ফেরত দিতে সক্ষম। এই ধরনের প্রশ্নের উত্তর দেওয়ার জন্য, চ্যান এবং অন্যান্যরা। লক্ষ্য করা শুরু করুন যে একটি ডেটা স্ট্রাকচার রয়েছে যা স্থানের শব্দের প্রয়োজন সময়সীমার মধ্যে শীর্ষ-কে সর্বাধিক ঘন ঘন আইটেমগুলি ফেরত দিতে সক্ষম। একটি এক-মাত্রিক অ্যারের জন্য, একটি একতরফা শীর্ষ-কে পরিসরের প্রশ্ন ফর্মের হতে দিন। একটি সর্বাধিক পরিসীমার জন্য যেখানে একটি স্বতন্ত্র উপাদানের ফ্রিকোয়েন্সি অপরিবর্তিত (এবং সমান) থাকে, একটি অনুভূমিক রেখা বিভাগ তৈরি করা হয়। এই লাইন সেগমেন্টের-ব্যবধান এর সাথে মিলে যায় এবং এর একটি-মান এর সমান। যেহেতু প্রতিটি উপাদান যোগ করে ঠিক একটি স্বতন্ত্র উপাদানের ফ্রিকোয়েন্সি পরিবর্তন করা হয়, তাই পূর্বোক্ত প্রক্রিয়াটি লাইন বিভাগ তৈরি করে। উপরন্তু, একটি উল্লম্ব রেখার জন্য এটি ছেদকারী সমস্ত দিগন্ত রেখা বিভাগগুলি তাদের ফ্রিকোয়েন্সি অনুসারে সাজানো হয়। লক্ষ্য করুন যে,-বিরতি সহ প্রতিটি অনুভূমিক রেখা বিভাগ ঠিক একটি স্বতন্ত্র উপাদানের সাথে মিলে যায়, যেমন। একটি টপ-কে প্রশ্নের উত্তর দেওয়া যেতে পারে একটি উল্লম্ব রশ্মি নিক্ষেপ করে এবং প্রথম অনুভূমিক রেখার অংশগুলি যা এটিকে ছেদ করে তা সময়মতো রিপোর্ট করে (উপর থেকে মনে রাখবেন যে এই লাইন লাইন বিভাগগুলি ইতিমধ্যে তাদের ফ্রিকোয়েন্সি অনুসারে সাজানো হয়েছে)। চ্যান এবং অন্যান্য। প্রথমে একটি পরিসীমা গাছ তৈরি করুন যেখানে প্রতিটি শাখা নোড একতরফা পরিসীমা শীর্ষ-কে প্রশ্নের জন্য উপরে বর্ণিত ডেটা কাঠামোর একটি অনুলিপি সংরক্ষণ করে এবং প্রতিটি পাতা থেকে একটি উপাদানকে উপস্থাপন করে। প্রতিটি নোডের টপ-কে ডেটা স্ট্রাকচার সেই নোডের সাবট্রিতে বিদ্যমান মানগুলির উপর ভিত্তি করে তৈরি করা হয় এবং এটি একতরফা রেঞ্জ টপ-কে প্রশ্নের উত্তর দেওয়ার জন্য। দয়া করে মনে রাখবেন যে একটি এক-মাত্রিক অ্যারের জন্য, একটি পরিসীমা গাছ দুটি অর্ধে বিভক্ত করে এবং উভয় অর্ধে পুনরাবৃত্তি করে তৈরি করা যেতে পারে; অতএব, ফলস্বরূপ পরিসীমা গাছের প্রতিটি নোড একটি পরিসীমা উপস্থাপন করে। এটিও দেখা যায় যে এই পরিসীমা গাছের জন্য জায়গার শব্দের প্রয়োজন, কারণ স্তর রয়েছে এবং প্রতিটি স্তরে নোড রয়েছে। অধিকন্তু, যেহেতু একটি পরিসীমা গাছের প্রতিটি স্তরে সমস্ত নোডের তাদের সাবট্রিতে মোট উপাদান থাকে এবং যেহেতু স্তর রয়েছে, তাই এই পরিসীমা গাছের স্থান জটিলতা হল। এই কাঠামোটি ব্যবহার করে, একটি পরিসীমা-সংখ্যাগরিষ্ঠ প্রশ্নের উত্তর নিম্নরূপ দেওয়া হয়। প্রথমত, লিফ নোডের সর্বনিম্ন সাধারণ পূর্বপুরুষ (এলসিএ) এবং স্থির সময়ে পাওয়া যায়। লক্ষ্য করুন যে একটি তথ্য কাঠামো রয়েছে যার জন্য কিছু জায়গার প্রয়োজন যা সময়মতো এলসিএ প্রশ্নের উত্তর দিতে সক্ষম। এবং-এর এল. সি. এ-কে নির্দেশ করা যাক, পরিসীমা-সংখ্যাগরিষ্ঠ প্রশ্নের (উপরে এবং ভিতরে বর্ণিত) পচনযোগ্যতা ব্যবহার করে এবং অনুযায়ী, দ্বিমুখী পরিসীমা প্রশ্নটিকে দুটি একতরফা পরিসীমা শীর্ষ-কে প্রশ্নের (থেকে এবং) রূপান্তরিত করা যেতে পারে। এই দুটি একতরফা পরিসীমা শীর্ষ-কে প্রশ্নগুলি তাদের প্রতিটি নির্দিষ্ট পরিসরে শীর্ষ-() সর্বাধিক ঘন ঘন উপাদানগুলি ফেরত দেয়। এই ঘন ঘন উপাদানগুলি সংখ্যাগরিষ্ঠদের জন্য প্রার্থীদের সেট তৈরি করে যেখানে প্রার্থী রয়েছে যার মধ্যে কিছু মিথ্যা ইতিবাচক হতে পারে। প্রতিটি প্রার্থীকে একটি রৈখিক-স্থান তথ্য কাঠামো (লেমা 3 ইঞ্চি বর্ণিত) ব্যবহার করে ধ্রুবক সময়ে মূল্যায়ন করা হয় যা একটি অ্যারের প্রদত্ত উপশ্রেণীতে কমপক্ষে একটি নির্দিষ্ট উপাদানের দৃষ্টান্ত রয়েছে কিনা তা সময়মতো নির্ধারণ করতে সক্ষম হয়। গাছের পথ গ্যাগি এবং অন্যান্য। একটি তথ্য কাঠামো প্রস্তাব করা হয়েছে যা প্রশ্নগুলিকে সমর্থন করে যেমন, দুটি নোড দেওয়া হয়েছে এবং একটি গাছে, এমন উপাদানগুলির তালিকা রিপোর্ট করতে সক্ষম যা থেকে পথের তুলনায় বেশি আপেক্ষিক ফ্রিকোয়েন্সি রয়েছে। আরও আনুষ্ঠানিকভাবে, একটি লেবেলযুক্ত গাছ হতে দিন যেখানে প্রতিটি নোডের আকারের বর্ণমালা থেকে একটি লেবেল থাকে। আসুন নোডের লেবেলটি নির্দেশ করি। আসুন সেই অনন্য পথটি নির্দেশ করি যেখানে মাঝের নোডগুলি যে ক্রমে পরিদর্শন করা হয়েছে সেই ক্রমে তালিকাভুক্ত করা হয়েছে। প্রদত্ত, এবং একটি নির্দিষ্ট (প্রাক-প্রক্রিয়াকরণের সময় নির্দিষ্ট) সীমা, একটি প্রশ্ন অবশ্যই সমস্ত লেবেলের সেট ফেরত দিতে হবে যা একাধিকবার প্রদর্শিত হয়। এই তথ্য কাঠামোটি তৈরি করতে, প্রথম নোডগুলি চিহ্নিত করা হয়। এটি এমন কোনও নোড চিহ্নিত করে করা যেতে পারে যার কমপক্ষে তিনটির (উচ্চতা) নীচে থেকে দূরত্ব রয়েছে এবং যার গভীরতা দ্বারা বিভাজ্য। এটি করার পরে, এটি লক্ষ্য করা যায় যে প্রতিটি নোড এবং তার নিকটতম চিহ্নিত পূর্বপুরুষের মধ্যে দূরত্ব এর চেয়ে কম। একটি চিহ্নিত নোডের জন্য, বিভিন্ন ক্রম (মূলের দিকে পথ) সংরক্ষণ করা হয়, যেখানে নোডের সরাসরি প্যারেন্টের লেবেল প্রদান করা হয়। অন্যভাবে বললে, প্রতিটি চিহ্নিত নোডের জন্য, মূলের দিকে দুটি দৈর্ঘ্যের (নোডের জন্য একটি যোগ) শক্তি সহ সমস্ত পথের সেট সংরক্ষণ করা হয়। উপরন্তু, প্রত্যেকের জন্য, সমস্ত সংখ্যাগরিষ্ঠ প্রার্থীদের সেট সংরক্ষণ করা হয়। আরও সুনির্দিষ্টভাবে, সমস্ত-সংখ্যাগরিষ্ঠতা বা লেবেলগুলির সেট রয়েছে যা একাধিকবার প্রদর্শিত হয়। এটা সহজেই দেখা যায় যে প্রার্থীদের সেটের প্রত্যেকের জন্য সর্বাধিক স্বতন্ত্র লেবেল থাকতে পারে। গ্যাগি এবং অন্যান্য। তারপর লক্ষ্য করুন যে কোনও চিহ্নিত নোড থেকে তার পূর্বপুরুষদের মধ্যে একটিতে যাওয়ার পথে সমস্ত-সংখ্যাগরিষ্ঠতার সেটটি কিছুতে (লেমা 2 ইঞ্চি) অন্তর্ভুক্ত করা হয়েছে কারণ এর দৈর্ঘ্য সমান তাই একটি রয়েছে যার দৈর্ঘ্য x এবং z এর মধ্যে দূরত্বের মধ্যে রয়েছে। এই ধরনের অস্তিত্ব বোঝায় যে থেকে যাওয়ার পথে একটি-সংখ্যাগরিষ্ঠতা অবশ্যই একটি-সংখ্যাগরিষ্ঠতা হতে হবে, এবং তাই অবশ্যই উপস্থিত হতে হবে। এটি সহজেই দেখা যায় যে এই তথ্য কাঠামোর জন্য জায়গার শব্দের প্রয়োজন হয়, কারণ নির্মাণ পর্যায়ে উপরে উল্লিখিত নোডগুলি চিহ্নিত করা হয় এবং প্রতিটি চিহ্নিত নোডের জন্য কিছু প্রার্থী সেট সংরক্ষণ করা হয়। সংজ্ঞা অনুসারে, এই ধরনের সেটের প্রতিটি চিহ্নিত নোডের জন্য স্টোর রয়েছে, যার প্রত্যেকটিতে প্রার্থী রয়েছে। অতএব, এই তথ্য কাঠামোর জন্য স্থানের শব্দের প্রয়োজন। দয়া করে মনে রাখবেন যে প্রতিটি নোড এমনও সঞ্চয় করে যা মূল থেকে পথের দৃষ্টান্তের সংখ্যার সমান, এটি স্থান জটিলতা বাড়ায় না কারণ এটি কেবল প্রতি নোডে ধ্রুবক সংখ্যক শব্দ যোগ করে। দুটি নোডের মধ্যে প্রতিটি প্রশ্নের উত্তর দেওয়া যেতে পারে পরিসীমা-সংখ্যাগরিষ্ঠ প্রশ্নের ডিকম্পোসেবিলিটি বৈশিষ্ট্য (উপরে বর্ণিত) ব্যবহার করে এবং চারটি উপপথের মধ্যে অনুসন্ধানের পথটি ভেঙে। ধরা যাক এবং এর সর্বনিম্ন সাধারণ পূর্বপুরুষ এবং যথাক্রমে এবং এর নিকটতম চিহ্নিত পূর্বপুরুষ। থেকে যাওয়ার পথটি যথাক্রমে থেকে আসা এবং যাওয়ার পথে বিভক্ত করা হয় (এই পথগুলির আকার সংজ্ঞা অনুসারে ছোট, যার সবকটিই প্রার্থী হিসাবে বিবেচিত হয়), এবং থেকে আসা এবং যাওয়ার পথগুলি (উপরে বর্ণিত হিসাবে উপযুক্ত খুঁজে বের করে এবং এর সমস্ত লেবেলকে প্রার্থী হিসাবে বিবেচনা করে)। দয়া করে মনে রাখবেন যে, সীমানা নোডগুলি সেই অনুযায়ী পরিচালনা করতে হবে যাতে এই সমস্ত উপপথগুলি বিচ্ছিন্ন হয় এবং তাদের থেকে প্রার্থীদের একটি সেট উদ্ভূত হয়। এই প্রার্থীদের প্রত্যেককে তারপর প্রশ্নের সংমিশ্রণ ব্যবহার করে যাচাই করা হয় যা নোডের সর্বনিম্ন পূর্বপুরুষকে প্রদান করে যার লেবেল এবং প্রতিটি নোডের ক্ষেত্র রয়েছে। একটি-বিট র্যাম এবং আকারের একটি বর্ণমালায়, রৈখিক স্থানের প্রয়োজনীয়তা থাকা সত্ত্বেও প্রশ্নের উত্তর সময়মতো দেওয়া যেতে পারে। অতএব, প্রতিটি প্রার্থীকে সময়মতো যাচাই করার ফলে থেকে যাওয়ার পথে সমস্ত সংখ্যাগরিষ্ঠের সেট ফেরত দেওয়ার জন্য মোট প্রশ্ন সময় পাওয়া যায়। সম্পর্কিত সমস্যাগুলি উপরে বর্ণিত সমস্ত সমস্যাগুলি উচ্চতর মাত্রার পাশাপাশি তাদের গতিশীল সংস্করণগুলির জন্য অধ্যয়ন করা হয়েছে। অন্যদিকে, পরিসীমা প্রশ্নগুলি গাছের মতো অন্যান্য তথ্য কাঠামোতে প্রসারিত করা যেতে পারে, যেমন স্তরের পূর্বপুরুষ সমস্যা। সমস্যাগুলির একটি অনুরূপ পরিবার হল অর্থোগোনাল পরিসীমা প্রশ্ন, যা গণনা প্রশ্ন হিসাবেও পরিচিত। আরও দেখুন স্তর পূর্বপুরুষ সমস্যা নিম্নতম সাধারণ পূর্বপুরুষ রেফারেন্স বাহ্যিক লিঙ্ক ওপেন ডেটা স্ট্রাকচার-অধ্যায় 13-ডেটা স্ট্রাকচার ফর ইন্টিজার ডেটা স্ট্রাকচার ফর রেঞ্জ মিডিয়ান প্রশ্ন-গার্থ স্টল্টিং ব্রোডাল এবং অ্যালান গ্রোনলান্ড জর্গেনসেন অ্যারে