Range query (computer science)
कंप्यूटर विज्ञान में, रेंज क्वैरी समस्या में एक सरणी के भीतर तत्वों के दिए गए अंतराल के बारे में कई प्रश्नों का कुशलता से उत्तर देना शामिल है। उदाहरण के लिए, एक सामान्य कार्य, जिसे रेंज मिनिमम क्वेरी के रूप में जाना जाता है, संख्याओं की सूची के भीतर दी गई सीमा के भीतर सबसे छोटे मूल्य का पता लगाना है। परिभाषा एक फ़ंक्शन को देखते हुए जो एक सरणी को स्वीकार करता है, एक सरणी पर एक रेंज क्वेरी दो सूचकांक लेती है और जब उप-सरणी पर लागू होती है तो उसका परिणाम बताती है। उदाहरण के लिए, एक फ़ंक्शन के लिए जो एक सरणी में सभी मूल्यों का योग देता है, रेंज क्वेरी सीमा में सभी मूल्यों का योग देता है। समाधान उपसर्ग सम ऐरे रेंज सम प्रश्नों का उत्तर स्थिर समय और रैखिक स्थान में इनपुट के समान लंबाई की एक सरणी की पूर्व-गणना करके दिया जा सकता है जैसे कि प्रत्येक सूचकांक के लिए, तत्व के पहले तत्वों का योग है। फिर किसी भी प्रश्न की गणना निम्नानुसार की जा सकती हैः इस रणनीति को किसी भी अन्य द्विआधारी संचालन तक बढ़ाया जा सकता है जिसका व्युत्क्रम कार्य अच्छी तरह से परिभाषित और आसानी से गणना योग्य है। इसे एक समान पूर्व-प्रसंस्करण के साथ द्वि-आयामी सरणी तक भी बढ़ाया जा सकता है। गतिशील सीमा प्रश्न समस्या के एक अधिक कठिन उपसमुच्चय में गतिशील डेटा पर सीमा प्रश्नों को निष्पादित करना शामिल है; अर्थात, डेटा जो प्रत्येक प्रश्न के बीच उत्परिवर्तित हो सकता है। सरणी मूल्यों को कुशलता से अद्यतन करने के लिए, खंड वृक्ष जैसी अधिक परिष्कृत डेटा संरचनाएं आवश्यक हैं। उदाहरण सेमीग्रुप प्रचालक जब किसी रेंज क्वेरी में रुचि का कार्य एक सेमीग्रुप प्रचालक होता है, तो की धारणा हमेशा परिभाषित नहीं होती है, इसलिए पिछले खंड में रणनीति काम नहीं करती है। एंड्रयू याओ ने दिखाया कि सीमा प्रश्नों के लिए एक कुशल समाधान मौजूद है जिसमें अर्ध-समूह संचालक शामिल हैं। उन्होंने साबित किया कि किसी भी स्थिरांक के लिए, समय और स्थान का एक पूर्व-प्रसंस्करण सूचियों पर सीमा प्रश्नों का उत्तर देने की अनुमति देता है जहां समय में एक अर्धसमूह प्रचालक है, जहां एकरमैन फलन का एक निश्चित कार्यात्मक व्युत्क्रम है। कुछ अर्धसमूह प्रचालक हैं जो थोड़े बेहतर समाधान स्वीकार करते हैं। उदाहरण के लिए कब। मान लीजिए कि फिर न्यूनतम तत्व का सूचकांक देता है। फिर संबंधित न्यूनतम रेंज क्वेरी को दर्शाता है। कई डेटा संरचनाएँ हैं जो समय और स्थान के पूर्व-प्रसंस्करण का उपयोग करके समय में न्यूनतम प्रश्न का उत्तर देने की अनुमति देती हैं। ऐसा ही एक समाधान इस समस्या और सबसे कम सामान्य पूर्वज समस्या के बीच समानता पर आधारित है। एक सरणी के कार्टेशियन पेड़ की जड़ होती है और बाएं और दाएं हिस्से में क्रमशः कार्टेशियन पेड़ और कार्टेशियन पेड़ होते हैं। एक सीमा न्यूनतम क्वेरी और में सबसे कम सामान्य पूर्वज है। क्योंकि सबसे कम सामान्य पूर्वज को समय और स्थान के पूर्व-प्रसंस्करण का उपयोग करके निरंतर समय में हल किया जा सकता है, न्यूनतम प्रश्न भी हो सकता है। समाधान जब समान होता है। कार्टेशियन पेड़ों का निर्माण रैखिक समय में किया जा सकता है। एक सरणी का मोड वह तत्व है जो इसमें सबसे अधिक दिखाई देता है। उदाहरण के लिए का मोड है। एक टाई के मामले में, सबसे अधिक बार होने वाले तत्वों में से किसी को भी मोड के रूप में चुना जा सकता है। एक रेंज मोड क्वेरी में प्री-प्रोसेसिंग शामिल होती है ताकि हम किसी भी रेंज में मोड पा सकें। इस समस्या को हल करने के लिए कई डेटा संरचनाएं तैयार की गई हैं, हम निम्नलिखित तालिका में कुछ परिणामों को संक्षेप में प्रस्तुत करते हैं। हाल ही में जॉर्गेनसन एट अल। कोशिकाओं का उपयोग करने वाली किसी भी डेटा संरचना के लिए कोशिका-जांच मॉडल पर एक निचली सीमा साबित हुई। माध्यिका यह विशेष मामला विशेष रुचि का है क्योंकि माध्यिका का पता लगाने के कई अनुप्रयोग हैं। दूसरी ओर, माध्यिका समस्या, चयन समस्या का एक विशेष मामला, माध्यिका एल्गोरिथ्म के माध्यिका का उपयोग करके ओ (एन) में हल किया जा सकता है। हालांकि रेंज मीडियन प्रश्नों के माध्यम से इसका सामान्यीकरण हाल ही में हुआ है। एक श्रेणी माध्यिका क्वेरी जहाँ A, i और j के सामान्य अर्थ हैं, का माध्यिका तत्व देता है। समान रूप से, रैंक के तत्व को वापस करना चाहिए। सेमीग्रुप ऑपरेटरों के लिए याओ के दृष्टिकोण सहित ऊपर चर्चा की गई पिछली किसी भी विधि का पालन करके रेंज मीडियन प्रश्नों को हल नहीं किया जा सकता है। इस समस्या के दो रूपों का अध्ययन किया गया है, ऑफ़लाइन संस्करण, जहां रुचि के सभी के प्रश्न एक बैच में दिए गए हैं, और एक संस्करण जहां सभी पूर्व-प्रसंस्करण पहले किया जाता है। ऑफ़लाइन संस्करण को समय और स्थान के साथ हल किया जा सकता है। क्विकसेलेक्ट एल्गोरिदम के निम्नलिखित छद्म कोड से पता चलता है कि हमारे द्वारा निर्धारित रेंज मीडियंस को खोजने के लिए, अलग-अलग तत्वों की एक असंरचित सरणी में रैंक के तत्व को कैसे खोजना है। मध्यमान (A, i, j, r) {यदि A.length () = = 1 लौटाता है A [1] यदि A.low अनिर्धारित है तो m = मध्यमान (A) A.low = [e में A। e <= m] A.high = [e में A। e> m] की गणना करें कि A [i, j] के तत्वों की संख्या जो A.low से संबंधित है यदि r <= t तो लौटाता है सीमा मध्यमान (A.low, i, j, r) अन्यथा लौटाता है सीमा मध्यमान (A.high, i, j, r-t)} प्रक्रिया विभाजन, 's मध्यमान का उपयोग करते हुए, दो सरणी में और जहां पूर्व में शामिल है यदि हम जानते हैं कि उस अंत में तत्वों की संख्या है और यह संख्या उससे बड़ी है तो हमें रैंक के तत्व की तलाश करते रहना चाहिए; अन्यथा हमें रैंक के तत्व की तलाश करनी चाहिए। पता लगाने के लिए, यह अधिकतम सूचकांक खोजने के लिए पर्याप्त है जैसे कि में है और अधिकतम सूचकांक जैसे कि में है। फिर. विभाजन भाग पर विचार किए बिना किसी भी प्रश्न के लिए कुल लागत यह है कि अधिकांश पुनरावृत्ति कॉल किए जाते हैं और उनमें से प्रत्येक में केवल निरंतर संख्या में संचालन किए जाते हैं (आंशिक कैस्केडिंग का मूल्य प्राप्त करने के लिए उपयोग किया जाना चाहिए)। यदि माध्यकों को खोजने के लिए एक रैखिक एल्गोरिथ्म का उपयोग किया जाता है, तो सीमा माध्यिका प्रश्नों के लिए पूर्व-प्रसंस्करण की कुल लागत है। समस्या के ऑनलाइन संस्करण को हल करने के लिए एल्गोरिथ्म को भी संशोधित किया जा सकता है। अधिकांश वस्तुओं के दिए गए समूह में लगातार तत्वों को खोजना डेटा माइनिंग में सबसे महत्वपूर्ण कार्यों में से एक है। जब अधिकांश वस्तुओं की आवृत्ति समान होती है तो लगातार तत्वों को खोजना एक कठिन काम हो सकता है। इसलिए, यह अधिक फायदेमंद हो सकता है यदि ऐसी वस्तुओं का पता लगाने के लिए महत्व की कुछ सीमा का उपयोग किया जाए। सरणी के बहुमत को खोजने के लिए सबसे प्रसिद्ध एल्गोरिदम में से एक बोयर और मूर द्वारा प्रस्तावित किया गया था जिसे बोयर-मूर बहुमत वोट एल्गोरिदम के रूप में भी जाना जाता है। बोयर और मूर ने समय पर एक स्ट्रिंग के बहुसंख्यक तत्व (यदि इसमें एक है) को खोजने और स्थान का उपयोग करने के लिए एक एल्गोरिथ्म का प्रस्ताव रखा। बोयर और मूर के काम के संदर्भ में और आम तौर पर, वस्तुओं के एक सेट में एक बहुमत तत्व (उदाहरण के लिए स्ट्रिंग या एक सरणी) वह है जिसके उदाहरणों की संख्या उस सेट के आकार के आधे से अधिक है। कुछ साल बाद, मिश्रा और ग्रिस ने एक सरणी में सभी वस्तुओं को खोजने के लिए तुलना का उपयोग करते हुए बोयर और मूर के एल्गोरिदम के एक अधिक सामान्य संस्करण का प्रस्ताव रखा, जिनकी सापेक्ष आवृत्तियाँ कुछ सीमा से अधिक हैं। एक रेंज-मेजॉरिटी क्वेरी वह है जो आकार की डेटा संरचना (उदाहरण के लिए एक सरणी) की एक उपश्रेणी को देखते हुए, सभी अलग-अलग वस्तुओं के सेट को लौटाता है जो उस सीमा में (या कुछ प्रकाशनों में बराबर) बार से अधिक दिखाई देते हैं। विभिन्न संरचनाओं में जो सीमा-बहुलता प्रश्नों का समर्थन करते हैं, वे या तो स्थिर (पूर्व-प्रसंस्करण के दौरान निर्दिष्ट) या गतिशील (प्रश्न के समय निर्दिष्ट) हो सकते हैं। इस तरह के कई दृष्टिकोण इस तथ्य पर आधारित हैं कि, सीमा के आकार की परवाह किए बिना, दिए गए के लिए कम से कम सापेक्ष आवृत्तियों के साथ सबसे अलग उम्मीदवार हो सकते हैं। इनमें से प्रत्येक उम्मीदवार को निरंतर समय में सत्यापित करके, पूछताछ का समय प्राप्त किया जाता है। एक रेंज-मेजॉरिटी क्वेरी इस अर्थ में विघटित की जा सकती है कि विभाजन के साथ एक रेंज में एक-मेजॉरिटी और या दोनों में से एक में-मेजॉरिटी होनी चाहिए। इस अपघटनीयता के कारण, कुछ डेटा संरचनाएं एक-आयामी सरणी पर अधिकांश प्रश्नों का उत्तर रेंज ट्री में क्वेरी रेंज के अंतिम बिंदुओं के सबसे कम सामान्य पूर्वज (एलसीए) को ढूंढकर और प्रत्येक अंतिम बिंदु से सबसे कम सामान्य पूर्वज तक उम्मीदवारों (आकार के) के दो सेटों को स्थिर समय में मान्य करके देती हैं, जिसके परिणामस्वरूप क्वेरी समय होता है। द्वि-आयामी सरणी गैगी एट अल। एक डेटा संरचना का प्रस्ताव दिया जो एक सरणी पर सीमा-बहुल प्रश्नों का समर्थन करता है। इस डेटा संरचना में प्रत्येक प्रश्न के लिए एक सीमा और एक आयताकार सीमा निर्दिष्ट की जाती है, और उन सभी तत्वों का समूह जिनकी सापेक्ष आवृत्तियाँ (उस आयताकार सीमा के अंदर) से अधिक या बराबर होती हैं, उन्हें आउटपुट के रूप में वापस किया जाता है। यह डेटा संरचना गतिशील सीमा (पूछताछ समय पर निर्दिष्ट) और एक पूर्व-प्रसंस्करण सीमा का समर्थन करती है जिसके आधार पर इसका निर्माण किया जाता है। पूर्व-प्रसंस्करण के दौरान, सरणी पर ऊर्ध्वाधर और क्षैतिज अंतरालों का एक समूह बनाया जाता है। एक साथ, एक ऊर्ध्वाधर और एक क्षैतिज अंतराल एक खंड बनाता है। प्रत्येक ब्लॉक अपने से नौ गुना बड़े सुपरब्लॉक का हिस्सा है (ब्लॉक के क्षैतिज अंतराल के आकार का तीन गुना और इसके ऊर्ध्वाधर के आकार का तीन गुना)। प्रत्येक ब्लॉक के लिए उम्मीदवारों का एक समूह (अधिक से अधिक तत्वों के साथ) संग्रहीत किया जाता है जिसमें ऐसे तत्व होते हैं जिनकी संबंधित सुपरब्लॉक में कम से कम सापेक्ष आवृत्तियाँ (पूर्व-प्रसंस्करण सीमा जैसा कि ऊपर उल्लेख किया गया है) होती हैं। इन तत्वों को उनकी आवृत्तियों के अनुसार गैर-बढ़ते क्रम में संग्रहीत किया जाता है और यह देखना आसान है कि, कोई भी तत्व जिसकी सापेक्ष आवृत्ति कम से कम एक ब्लॉक में होती है, उसे अपने उम्मीदवारों का समूह दिखाई देना चाहिए। प्रत्येक-बहुमत प्रश्न का उत्तर पहले प्रश्न खंड, या समय पर प्रदान किए गए प्रश्न आयत में निहित सबसे बड़े खंड को ढूंढकर दिया जाता है। प्राप्त क्वेरी ब्लॉक के लिए, पहले उम्मीदवारों को समय पर (सत्यापित किए बिना) वापस कर दिया जाता है, इसलिए यह प्रक्रिया कुछ गलत सकारात्मक परिणाम दे सकती है। कई अन्य डेटा संरचनाओं (जैसा कि नीचे चर्चा की गई है) ने प्रत्येक उम्मीदवार को स्थिर समय में सत्यापित करने के लिए प्रस्तावित तरीके हैं और इस प्रकार प्रश्न समय को बनाए रखते हुए कोई गलत सकारात्मक नहीं देते हैं। जिन मामलों में क्वेरी ब्लॉक छोटा है, उन्हें निम्नलिखित प्रपत्र के इस डेटा संरचना के विभिन्न उदाहरणों को संग्रहीत करके संभाला जाता हैः-th उदाहरण की पूर्व-प्रसंस्करण सीमा कहाँ है। इस प्रकार,-th उदाहरण से छोटे क्वेरी ब्लॉकों के लिए पूछताछ की जाती है। जैसा कि ऊपर उल्लेख किया गया है, इस डेटा संरचना में पूछताछ का समय होता है और इसकी हफमैन-एन्कोडेड प्रति को संग्रहीत करके थोड़ी सी जगह की आवश्यकता होती है (कारक पर ध्यान दें और हफमैन कोडिंग भी देखें)। एक-आयामी सरणी चैन एट अल। एक प्रस्तावित डेटा संरचना जो एक-आयामी सरणी, एक उपश्रेणी (प्रश्न समय पर निर्दिष्ट) और एक सीमा (प्रश्न समय पर निर्दिष्ट) दी गई है, स्थान के शब्दों की आवश्यकता वाले समय में सभी-बहुमत की सूची को वापस करने में सक्षम है। इस तरह के प्रश्नों का उत्तर देने के लिए, चैन और अन्य। यह ध्यान में रखते हुए शुरू करें कि एक डेटा संरचना मौजूद है जो स्थान के शब्दों की आवश्यकता वाले समय में शीर्ष-के सबसे अधिक बार वस्तुओं को वापस करने में सक्षम है। एक-आयामी सरणी के लिए, एक तरफा शीर्ष-के रेंज क्वेरी को फॉर्म का होने दें। श्रेणियों की एक अधिकतम सीमा के लिए जिसमें एक अलग तत्व की आवृत्ति अपरिवर्तित (और उसके बराबर) रहती है, एक क्षैतिज रेखा खंड का निर्माण किया जाता है। इस रेखा खंड का-अंतराल इसके अनुरूप है और इसका-मान इसके बराबर है। चूँकि प्रत्येक तत्व को जोड़ने से ठीक एक अलग तत्व की आवृत्ति बदल जाती है, उपरोक्त प्रक्रिया रेखा खंड बनाती है। इसके अलावा, एक ऊर्ध्वाधर रेखा के लिए इसे काटते हुए सभी क्षैतिज रेखा खंडों को उनकी आवृत्तियों के अनुसार क्रमबद्ध किया जाता है। ध्यान दें कि,-अंतराल वाला प्रत्येक क्षैतिज रेखा खंड ठीक एक अलग तत्व से मेल खाता है, जैसे कि। एक शीर्ष-के प्रश्न का उत्तर एक ऊर्ध्वाधर किरण को शूट करके और पहले क्षैतिज रेखा खंडों की रिपोर्ट करके दिया जा सकता है जो इसे काटते हैं (ऊपर से याद रखें कि इन रेखा रेखा खंडों को पहले से ही उनकी आवृत्तियों के अनुसार क्रमबद्ध किया गया है)। चैन एट अल। पहले एक रेंज ट्री का निर्माण करें जिसमें प्रत्येक शाखा नोड एक तरफा रेंज टॉप-के प्रश्नों के लिए ऊपर वर्णित डेटा संरचना की एक प्रति संग्रहीत करता है और प्रत्येक पत्ता एक तत्व का प्रतिनिधित्व करता है। प्रत्येक नोड पर टॉप-के डेटा संरचना का निर्माण उस नोड के सबट्री में मौजूद मूल्यों के आधार पर किया जाता है और यह एकतरफा रेंज टॉप-के प्रश्नों का उत्तर देने के लिए होता है। कृपया ध्यान दें कि एक-आयामी सरणी के लिए, एक रेंज ट्री का निर्माण दो हिस्सों में विभाजित करके और दोनों हिस्सों पर पुनरावृत्ति करके किया जा सकता है; इसलिए, परिणामी रेंज ट्री का प्रत्येक नोड एक सीमा का प्रतिनिधित्व करता है। यह भी देखा जा सकता है कि इस रेंज ट्री को स्थान के शब्दों की आवश्यकता होती है, क्योंकि स्तर होते हैं और प्रत्येक स्तर में नोड्स होते हैं। इसके अलावा, क्योंकि एक रेंज ट्री के प्रत्येक स्तर पर सभी नोड्स में उनके सबट्री पर कुल तत्व होते हैं और चूंकि स्तर होते हैं, इसलिए इस रेंज ट्री की अंतरिक्ष जटिलता है। इस संरचना का उपयोग करते हुए, एक सीमा-बहुल प्रश्न का उत्तर निम्नानुसार दिया जाता है। सबसे पहले, लीफ नोड्स का सबसे कम सामान्य पूर्वज (एल. सी. ए.) और स्थिर समय में पाया जाता है। ध्यान दें कि एक डेटा संरचना मौजूद है जिसके लिए जगह की आवश्यकता होती है जो समय पर एलसीए प्रश्नों का उत्तर देने में सक्षम है। आइए और के एल. सी. ए. को दर्शाते हैं, उपयोग करते हुए और सीमा-बहुलता प्रश्नों (जैसा कि ऊपर और में वर्णित है) की अपघटनीयता के अनुसार, दो-तरफा सीमा प्रश्न को दो एकतरफा सीमा शीर्ष-के प्रश्नों (से और) में परिवर्तित किया जा सकता है। ये दो एकतरफा रेंज टॉप-के प्रश्न समय पर अपनी-अपनी श्रेणियों में शीर्ष-() सबसे अधिक बार आने वाले तत्वों को वापस करते हैं। ये नियमित तत्व-बहुमत के लिए उम्मीदवारों का समूह बनाते हैं जिसमें उम्मीदवार होते हैं जिनमें से कुछ गलत सकारात्मक हो सकते हैं। प्रत्येक उम्मीदवार का मूल्यांकन एक रैखिक-अंतरिक्ष डेटा संरचना (जैसा कि लेम्मा 3 इंच में वर्णित है) का उपयोग करके निरंतर समय में किया जाता है जो समय पर यह निर्धारित करने में सक्षम है कि किसी सरणी की दी गई उपश्रेणी में किसी विशेष तत्व के कम से कम उदाहरण हैं या नहीं। ट्री पाथ गैगी एट अल। एक डेटा संरचना का प्रस्ताव दिया जो प्रश्नों का समर्थन करता है जैसे कि दो नोड्स और एक ट्री में दिए गए हैं, उन तत्वों की सूची की रिपोर्ट करने में सक्षम हैं जिनकी सापेक्ष आवृत्ति एक से दूसरे के रास्ते की तुलना में अधिक है। अधिक औपचारिक रूप से, एक लेबल वाला वृक्ष होने दें जिसमें प्रत्येक नोड में आकार की वर्णमाला से एक लेबल होता है। आइए नोड के लेबल को निरूपित करें। आइए उस अद्वितीय पथ को दर्शाते हैं जिसमें मध्य नोड्स को उस क्रम में सूचीबद्ध किया गया है जिस क्रम में उनका दौरा किया गया है। दिए गए, और एक निश्चित (पूर्व-प्रसंस्करण के दौरान निर्दिष्ट) सीमा, एक प्रश्न को उन सभी लेबलों के सेट को वापस करना चाहिए जो बार-बार दिखाई देते हैं। इस डेटा संरचना के निर्माण के लिए, पहले नोड्स को चिह्नित किया जाता है। यह किसी भी नोड को चिह्नित करके किया जा सकता है जिसकी दूरी कम से कम तीन (ऊंचाई) के नीचे से है और जिसकी गहराई द्वारा विभाज्य है। ऐसा करने के बाद, यह देखा जा सकता है कि प्रत्येक नोड और उसके निकटतम चिह्नित पूर्वज के बीच की दूरी उससे कम है। एक चिह्नित नोड के लिए, विभिन्न अनुक्रम (मूल की ओर पथ) संग्रहीत किए जाते हैं, जिसके लिए नोड के प्रत्यक्ष मूल का लेबल लौटाता है। दूसरे तरीके से कहें, प्रत्येक चिह्नित नोड के लिए, रूट की ओर दो लंबाई (प्लस नोड के लिए ही एक) की शक्ति वाले सभी पथों का सेट संग्रहीत किया जाता है। इसके अलावा, प्रत्येक के लिए, सभी बहुमत वाले उम्मीदवारों का समूह संग्रहीत किया जाता है। अधिक विशेष रूप से, इसमें सभी-बहुमत या लेबलों का सेट होता है जो एक से अधिक बार दिखाई देते हैं। यह देखना आसान है कि उम्मीदवारों के समूह में प्रत्येक के लिए सबसे अलग लेबल हो सकते हैं। गैगी एट अल। फिर ध्यान दें कि किसी भी चिह्नित नोड से उसके पूर्वजों में से एक तक के मार्ग में सभी-बहुलताओं का समूह कुछ (लेम्मा 2 इंच) में शामिल है क्योंकि की लंबाई इस प्रकार के बराबर है जिसकी लंबाई के लिए एक मौजूद है जहां x और z के बीच की दूरी है। इस तरह के अस्तित्व का तात्पर्य है कि से आने वाले मार्ग में एक-बहुमत एक-बहुमत होना चाहिए, और इसलिए इसमें दिखाई देना चाहिए। यह देखना आसान है कि इस डेटा संरचना के लिए स्थान के शब्दों की आवश्यकता होती है, क्योंकि जैसा कि निर्माण चरण नोड्स में ऊपर उल्लेख किया गया है और प्रत्येक चिह्नित नोड के लिए कुछ उम्मीदवार सेट संग्रहीत किए जाते हैं। परिभाषा के अनुसार, ऐसे सेटों के प्रत्येक चिह्नित नोड के लिए स्टोर होते हैं, जिनमें से प्रत्येक में उम्मीदवार होते हैं। इसलिए, इस डेटा संरचना के लिए स्थान के शब्दों की आवश्यकता होती है। कृपया ध्यान दें कि प्रत्येक नोड भी संग्रहीत करता है जो रूट से रूट तक के उदाहरणों की संख्या के बराबर है, यह स्थान जटिलता को नहीं बढ़ाता है क्योंकि यह केवल प्रति नोड शब्दों की एक स्थिर संख्या जोड़ता है। दो नोड्स के बीच प्रत्येक प्रश्न का उत्तर रेंज-मेजॉरिटी प्रश्नों के अपघटक गुण (जैसा कि ऊपर बताया गया है) का उपयोग करके और क्वेरी पथ को चार उपपथों में विभाजित करके दिया जा सकता है। मान लीजिए कि क्रमशः और के सबसे निकटतम चिह्नित पूर्वजों के साथ और होने के साथ सबसे कम सामान्य पूर्वज हैं। से आने वाले मार्ग को क्रमशः आने और जाने वाले मार्गों में विघटित किया जाता है (इन मार्गों का आकार परिभाषा की तुलना में छोटा होता है, जिनमें से सभी को उम्मीदवार माना जाता है), और आने और जाने वाले मार्ग (जैसा कि ऊपर बताया गया है, उपयुक्त को ढूंढकर और उम्मीदवारों के रूप में इसके सभी लेबलों पर विचार करके)। कृपया ध्यान दें कि, सीमा नोड्स को तदनुसार संभाला जाना चाहिए ताकि ये सभी उपपथ असंबद्ध हों और उन सभी से उम्मीदवारों का एक समूह प्राप्त हो। इन उम्मीदवारों में से प्रत्येक को क्वेरी के संयोजन का उपयोग करके सत्यापित किया जाता है जो नोड के सबसे निचले पूर्वज को बताता है जिसमें लेबल और प्रत्येक नोड के क्षेत्र होते हैं। एक-बिट रैम और आकार की वर्णमाला पर, रैखिक स्थान आवश्यकताओं के साथ प्रश्न का उत्तर समय पर दिया जा सकता है। इसलिए, समय पर प्रत्येक उम्मीदवार को सत्यापित करने के परिणामस्वरूप सभी-बहुमत के समूह को वापस करने के लिए कुल प्रश्न समय मिलता है। संबंधित समस्याओं ऊपर वर्णित सभी समस्याओं का अध्ययन उच्च आयामों के साथ-साथ उनके गतिशील संस्करणों के लिए किया गया है। दूसरी ओर, सीमा प्रश्नों को अन्य डेटा संरचनाओं जैसे पेड़ों तक बढ़ाया जा सकता है, जैसे कि स्तर पूर्वज समस्या। समस्याओं का एक समान परिवार ऑर्थोगोनल रेंज प्रश्न हैं, जिन्हें गणना प्रश्नों के रूप में भी जाना जाता है। स्तर पूर्वज समस्या भी देखें सबसे कम सामान्य पूर्वज संदर्भ बाहरी लिंक ओपन डेटा स्ट्रक्चर-अध्याय 13-डेटा स्ट्रक्चर फॉर इंटीजर्स डेटा स्ट्रक्चर फॉर रेंज मीडियन क्वेरीज़-गेर्थ स्टोल्टिंग ब्रोडल और एलन ग्रोनलंड जॉर्गेनसन सरणी