रेंज क्वेरी (डेटा संरचनाएं)

For finding items that fall within a range, see range query (database).

डेटा संरचनाओं में, रेंज क्वेरी में डेटा प्री-प्रोसेसिंग शामिल होती है | इनपुट के किसी भी सबसेट पर किसी भी संख्या में प्रश्नों का कुशलतापूर्वक उत्तर देने के लिए डेटा संरचना में कुछ इनपुट डेटा को प्री-प्रोसेस किया जाता है। विशेष रूप से, समस्याओं का समूह है जिसका बड़े पैमाने पर अध्ययन किया गया है जहां इनपुट अवर्गीकृत संख्याओं की सरणी डेटा संरचना है और क्वेरी में सरणी की विशिष्ट सीमा पर कुछ फ़ंक्शन, जैसे न्यूनतम, की गणना करना शामिल है।

परिभाषा

एक श्रेणी क्वेरी $q_{f}(A,i,j)$ सरणी पर $A=[a_{1},a_{2},..,a_{n}]$ किसी समुच्चय के n तत्वों का S, निरूपित $A[1,n]$, दो सूचकांक लेता है $1\leq i\leq j\leq n$, समारोह f के तत्वों की सरणियों पर परिभाषित S और आउटपुट $f(A[i,j])=f(a_{i},\ldots ,a_{j})$.

उदाहरण के लिए, के लिए $f=\sum$ और $A[1,n]$ संख्याओं की सारणी, श्रेणी क्वेरी $\sum _{i,j}A$ गणना करता है $\sum A[i,j]=(a_{i}+\ldots +a_{j})$, किसी के लिए $1\leq i\leq j\leq n$. इन प्रश्नों का उत्तर निरंतर समय और उपयोग में दिया जा सकता है $O(n)$ पहले के योग की गणना करके अतिरिक्त स्थान i घटक A और उन्हें सहायक सरणी में संग्रहीत करना B, ऐसा है कि $B[i]$ प्रथम का योग सम्मिलित है i घटक A हरएक के लिए $0\leq i\leq n$. इसलिए, किसी भी प्रश्न का उत्तर ऐसा करके दिया जा सकता है $\sum A[i,j]=B[j]-B[i-1]$.

इस रणनीति को प्रत्येक समूह (गणित) ऑपरेटर के लिए बढ़ाया जा सकता है f जहां की धारणा $f^{-1}$ अच्छी तरह से परिभाषित और आसानी से गणना योग्य है। अंत में, इस समाधान को समान पूर्व-प्रसंस्करण के साथ द्वि-आयामी सरणियों तक बढ़ाया जा सकता है।

उदाहरण

सेमीग्रुप ऑपरेटर

Main article: Range minimum query

जब किसी श्रेणी क्वेरी में रुचि का कार्य एक अर्धसमूह ऑपरेटर होता है, तो इसकी धारणा $f^{-1}$ हमेशा परिभाषित नहीं किया जाता है, इसलिए पिछले अनुभाग की रणनीति काम नहीं करती है। एंड्रयू याओ ने दिखाया सेमीग्रुप ऑपरेटरों को शामिल करने वाली रेंज क्वेरीज़ के लिए कुशल समाधान मौजूद है। उन्होंने इसे किसी भी स्थिरांक के लिए सिद्ध किया c, समय और स्थान का पूर्व-प्रसंस्करण $\theta (c\cdot n)$ जहां सूचियों पर श्रेणी प्रश्नों का उत्तर देने की अनुमति देता है f सेमीग्रुप ऑपरेटर है $\theta (\alpha _{c}(n))$ समय, कहाँ $\alpha _{c}$ एकरमैन फ़ंक्शन का निश्चित कार्यात्मक व्युत्क्रम है।

कुछ सेमीग्रुप ऑपरेटर हैं जो थोड़ा बेहतर समाधान स्वीकार करते हैं। उदाहरण के लिए जब $f\in \{\max ,\min \}$. मान लीजिए $f=\min$ तब $\min(A[1..n])$ के न्यूनतम तत्व का सूचकांक लौटाता है $A[1..n]$. तब $\min _{i,j}(A)$ संबंधित न्यूनतम श्रेणी क्वेरी को दर्शाता है। ऐसी कई डेटा संरचनाएं हैं जो न्यूनतम सीमा में क्वेरी का उत्तर देने की अनुमति देती हैं $O(1)$ समय और स्थान की पूर्व-प्रसंस्करण का उपयोग करके $O(n)$. ऐसा समाधान इस समस्या और निम्नतम सामान्य पूर्वज समस्या के बीच समानता पर आधारित है।

कार्तीय वृक्ष $T_{A}$ सरणी का $A[1,n]$ जड़ के रूप में है $a_{i}=\min\{a_{1},a_{2},\ldots ,a_{n}\}$ और बाएँ और दाएँ उपवृक्ष के रूप में कार्तीय वृक्ष $A[1,i-1]$ और कार्तीय वृक्ष $A[i+1,n]$ क्रमश। श्रेणी न्यूनतम क्वेरी $\min _{i,j}(A)$ में निम्नतम सामान्य पूर्वज है $T_{A}$ का $a_{i}$ और $a_{j}$. क्योंकि सबसे कम सामान्य पूर्वज को समय और स्थान की पूर्व-प्रसंस्करण का उपयोग करके निरंतर समय में हल किया जा सकता है $O(n)$, रेंज न्यूनतम क्वेरी भी कर सकते हैं। समाधान जब $f=\max$ अनुरूप है. कार्तीय वृक्षों का निर्माण रैखिक समय में किया जा सकता है।

मोड

Main article: Range mode query

किसी सरणी A का मोड (सांख्यिकी) वह तत्व है जो A में सबसे अधिक दिखाई देता है। उदाहरण के लिए का मोड $A=[4,5,6,7,4]$ है 4. संबंधों के मामले में सबसे अधिक बार आने वाले तत्वों में से किसी को मोड के रूप में चुना जा सकता है। रेंज मोड क्वेरी में प्री-प्रोसेसिंग शामिल होती है $A[1,n]$ जैसे कि हम किसी भी रेंज में मोड पा सकते हैं $A[1,n]$. इस समस्या को हल करने के लिए कई डेटा संरचनाएं तैयार की गई हैं, हम निम्नलिखित तालिका में कुछ परिणामों का सारांश प्रस्तुत करते हैं।

Range Mode Queries

Space	Query Time	Restrictions
$O(n^{2-2\epsilon })$	$O(n^{\epsilon }\log n)$	$0\leq \epsilon \leq {\frac {1}{2}}$
$O\left({\frac {n^{2}\log \log n}{\log n}}\right)$	$O(1)$

हाल ही में जोर्गेनसेन एट अल। के सेल-जांच मॉडल पर निचली सीमा साबित हुई $\Omega \left({\tfrac {\log n}{\log(Sw/n)}}\right)$ उपयोग करने वाली किसी भी डेटा संरचना के लिए S कोशिकाएं.

माध्यिका

यह विशेष मामला विशेष रुचि का है क्योंकि माध्यिका ज्ञात करने के कई अनुप्रयोग हैं। दूसरी ओर, माध्यिका समस्या, चयन समस्या का विशेष मामला, माध्यिका एल्गोरिथ्म का उपयोग करके O(n) में हल किया जा सकता है। हालाँकि रेंज मीडियन प्रश्नों के माध्यम से इसका सामान्यीकरण हाल ही में हुआ है।एक श्रेणी माध्यिका क्वेरी $\operatorname {median} (A,i,j)$ जहां A,i और j के सामान्य अर्थ हैं, का मध्य तत्व लौटाता है $A[i,j]$. समान रूप से, $\operatorname {median} (A,i,j)$ का तत्व वापस करना चाहिए $A[i,j]$ रैंक का ${\frac {j-i}{2}}$. सेमीग्रुप ऑपरेटरों के लिए याओ के दृष्टिकोण सहित ऊपर चर्चा की गई किसी भी पिछली विधि का पालन करके रेंज मीडियन प्रश्नों को हल नहीं किया जा सकता है।

इस समस्या के दो प्रकारों का अध्ययन किया गया है, ऑफ़लाइन एल्गोरिदम संस्करण, जहां रुचि के सभी k प्रश्न बैच में दिए गए हैं, और संस्करण जहां सभी पूर्व-प्रसंस्करण पहले ही किया जाता है। ऑफ़लाइन संस्करण के साथ हल किया जा सकता है $O(n\log k+k\log n)$ समय और $O(n\log k)$ अंतरिक्ष।

तुरंत चयन का निम्नलिखित छद्मकोड दिखाता है कि रैंक के तत्व को कैसे खोजा जाए r में $A[i,j]$ हमारे द्वारा निर्धारित सीमा माध्यिकाओं को खोजने के लिए, अलग-अलग तत्वों की अवर्गीकृत सरणी $r={\frac {j-i}{2}}$. रेंजमेडियन(ए, आई, जे, आर) {

    यदि A.लंबाई() == 1
        वापसी ए[1]

    यदि A.low अपरिभाषित है तो
        एम = माध्यिका(ए)
        A.low = [e in A | ई <= एम]
        ए.हाई = [ई इन ए | ई > एम ]

    A[i, j] के उन तत्वों की संख्या की गणना करें जो A.low से संबंधित हैं

    यदि r <= t तो
        रिटर्न रेंजमेडियन(ए.लो, आई, जे, आर)
    अन्य
        रिटर्न रेंजमेडियन(ए.हाई, आई, जे, आरटी)
}

प्रक्रिया rangeMedian विभाजन A, का उपयोग करना A का माध्यिका, दो सरणियों में A.low और A.high, जहां पूर्व शामिल है के तत्व A जो माध्यिका से कम या उसके बराबर हैं m और बाद वाले के बाकी तत्व A. यदि हम जानते हैं कि तत्वों की संख्या $A[i,j]$ वह में खत्म A.low है t और यह संख्या इससे भी बड़ी है r तो हमें रैंक के तत्व की तलाश करते रहना चाहिए r में A.low; अन्यथा हमें रैंक के तत्व की तलाश करनी चाहिए $(r-t)$ में A.high. ढूँढ़ने के लिए t, यह अधिकतम सूचकांक ज्ञात करने के लिए पर्याप्त है $m\leq i-1$ ऐसा है कि $a_{m}$ में है A.low और अधिकतम सूचकांक $l\leq j$ ऐसा है कि $a_{l}$ में है A.high. तब $t=l-m$. विभाजन भाग पर विचार किए बिना, किसी भी प्रश्न की कुल लागत है $\log n$ चूँकि अधिक से अधिक $\log n$ रिकर्सन कॉल किए जाते हैं और उनमें से प्रत्येक में केवल निरंतर संख्या में ऑपरेशन किए जाते हैं (मान प्राप्त करने के लिए)। tआंशिक प्रपात का उपयोग किया जाना चाहिए)। यदि मध्यस्थों को खोजने के लिए रैखिक एल्गोरिथ्म का उपयोग किया जाता है, तो पूर्व-प्रसंस्करण की कुल लागत kश्रेणी माध्यिका प्रश्न है $n\log k$. समस्या के ऑनलाइन एल्गोरिदम संस्करण को हल करने के लिए एल्गोरिथम को भी संशोधित किया जा सकता है।

बहुमत

किसी दिए गए आइटम सेट में लगातार तत्वों को ढूंढना डेटा माइनिंग में सबसे महत्वपूर्ण कार्यों में से है। जब अधिकांश वस्तुओं की आवृत्तियाँ समान हों तो बारंबार तत्वों को ढूँढना कठिन कार्य हो सकता है। इसलिए, यह अधिक फायदेमंद हो सकता है यदि ऐसी वस्तुओं का पता लगाने के लिए महत्व की कुछ सीमा का उपयोग किया जाए। किसी सरणी के अधिकांश भाग को खोजने के लिए सबसे प्रसिद्ध एल्गोरिदम में से बॉयर और मूर द्वारा प्रस्तावित किया गया था जिसे बॉयर-मूर बहुमत वोट एल्गोरिदम के रूप में भी जाना जाता है। बॉयर और मूर ने स्ट्रिंग के अधिकांश तत्व (यदि इसमें है) को खोजने के लिए एल्गोरिदम प्रस्तावित किया $O(n)$ समय और उपयोग $O(1)$ अंतरिक्ष। बॉयर और मूर के काम के संदर्भ में और आम तौर पर बोलते हुए, वस्तुओं के सेट में बहुसंख्यक तत्व (उदाहरण के लिए स्ट्रिंग या सरणी) वह होता है जिसके उदाहरणों की संख्या उस सेट के आकार के आधे से अधिक होती है। कुछ साल बाद, मिश्रा और ग्रिज़ बॉयर और मूर के एल्गोरिदम का अधिक सामान्य संस्करण प्रस्तावित किया $O\left(n\log \left({\frac {1}{\tau }}\right)\right)$ किसी सारणी में सभी वस्तुओं को खोजने के लिए तुलना जिनकी सापेक्ष आवृत्तियाँ कुछ सीमा से अधिक हैं $0<\tau <1$. दायरा $\tau$-अधिकांश क्वेरी वह होती है, जिसमें डेटा संरचना (उदाहरण के लिए सरणी) के आकार की उपश्रेणी दी जाती है $|R|$, उन सभी अलग-अलग आइटमों का सेट लौटाता है जो (या कुछ प्रकाशनों में इसके बराबर) से अधिक दिखाई देते हैं $\tau |R|$ उस दी गई सीमा में कई बार. विभिन्न संरचनाओं में जो रेंज का समर्थन करते हैं $\tau$-अधिकांश प्रश्न, $\tau$ या तो स्थिर हो सकता है (पूर्व-प्रसंस्करण के दौरान निर्दिष्ट) या गतिशील (क्वेरी समय पर निर्दिष्ट)। ऐसे कई दृष्टिकोण इस तथ्य पर आधारित हैं कि, किसी दिए गए दायरे के आकार की परवाह किए बिना $\tau$ ज्यादा से ज्यादा हो सकता है $O(1/\tau )$ कम से कम सापेक्ष आवृत्तियों वाले विशिष्ट उम्मीदवार $\tau$. इनमें से प्रत्येक उम्मीदवार का निरंतर समय में सत्यापन करके, $O(1/\tau )$ क्वेरी का समय प्राप्त हो गया है. दायरा $\tau$-अधिकांश क्वेरी विघटित करने योग्य है इस अर्थ में कि ए $\tau$-एक सीमा में बहुमत $R$ विभाजन के साथ $R_{1}$ और $R_{2}$ होना चाहिए $\tau$-दोनों में बहुमत $R_{1}$या $R_{2}$. इस विघटनशीलता के कारण, कुछ डेटा संरचनाएँ उत्तर देती हैं $\tau$- रेंज वृक्ष में क्वेरी रेंज के अंतिम बिंदुओं के निम्नतम सामान्य पूर्वज (एलसीए) को ढूंढकर और उम्मीदवारों के दो सेट (आकार के) को मान्य करके एक-आयामी सरणियों पर अधिकांश प्रश्न $O(1/\tau )$) प्रत्येक समापन बिंदु से निम्नतम सामान्य पूर्वज तक निरंतर समय के परिणामस्वरूप $O(1/\tau )$ पूछताछ का समय.

द्वि-आयामी सरणियाँ

गैगी एट अल. डेटा संरचना प्रस्तावित की जो रेंज का समर्थन करती है $\tau$-अधिकांश प्रश्न पर $m\times n$ सरणी $A$. प्रत्येक प्रश्न के लिए $\operatorname {Q} =(\operatorname {R} ,\tau )$ इस डेटा संरचना में सीमा है $0<\tau <1$ और आयताकार श्रेणी $\operatorname {R}$ निर्दिष्ट हैं, और उन सभी तत्वों का सेट जिनकी सापेक्ष आवृत्तियाँ (उस आयताकार सीमा के अंदर) से अधिक या उसके बराबर हैं $\tau$ आउटपुट के रूप में लौटाए जाते हैं। यह डेटा संरचना गतिशील थ्रेशोल्ड (क्वेरी समय पर निर्दिष्ट) और प्री-प्रोसेसिंग थ्रेशोल्ड का समर्थन करती है $\alpha$ जिसके आधार पर इसका निर्माण किया गया है। पूर्व-प्रसंस्करण के दौरान, ऊर्ध्वाधर और क्षैतिज अंतराल का सेट बनाया जाता है $m\times n$ सरणी. ऊर्ध्वाधर और क्षैतिज अंतराल मिलकर ब्लॉक बनाते हैं। प्रत्येक ब्लॉक अपने से नौ गुना बड़े सुपरब्लॉक का हिस्सा है (ब्लॉक के क्षैतिज अंतराल के आकार का तीन गुना और इसके ऊर्ध्वाधर के आकार का तीन गुना)। प्रत्येक ब्लॉक के लिए उम्मीदवारों का सेट (साथ) ${\frac {9}{\alpha }}$ अधिक से अधिक तत्व) संग्रहित किया जाता है जिसमें कम से कम सापेक्ष आवृत्तियों वाले तत्व शामिल होते हैं ${\frac {\alpha }{9}}$ (पूर्व-प्रसंस्करण सीमा जैसा कि ऊपर बताया गया है) अपने संबंधित सुपरब्लॉक में। इन तत्वों को उनकी आवृत्तियों के अनुसार गैर-बढ़ते क्रम में संग्रहीत किया जाता है और यह देखना आसान है कि, कोई भी तत्व जिसकी कम से कम सापेक्ष आवृत्ति होती है $\alpha$ किसी ब्लॉक में उसके उम्मीदवारों का समूह उपस्थित होना चाहिए। प्रत्येक $\tau$-अधिकांश क्वेरी का उत्तर सबसे पहले क्वेरी ब्लॉक, या दिए गए क्वेरी आयत में शामिल सबसे बड़े ब्लॉक को ढूंढकर दिया जाता है $O(1)$ समय। प्राप्त क्वेरी ब्लॉक के लिए, पहला ${\frac {9}{\tau }}$ अभ्यर्थियों को (सत्यापित किए बिना) लौटा दिया जाता है $O(1/\tau )$ समय, इसलिए यह प्रक्रिया कुछ ग़लत सकारात्मक परिणाम दे सकती है। कई अन्य डेटा संरचनाओं (जैसा कि नीचे चर्चा की गई है) ने प्रत्येक उम्मीदवार को निरंतर समय में सत्यापित करने और इस प्रकार बनाए रखने के तरीकों का प्रस्ताव दिया है $O(1/\tau )$ कोई गलत सकारात्मकता न लौटाते हुए क्वेरी का समय। वे मामले जिनमें क्वेरी ब्लॉक छोटा है $1/\alpha$ भण्डारण द्वारा किया जाता है $\log \left({\frac {1}{\alpha }}\right)$ निम्नलिखित प्रपत्र की इस डेटा संरचना के विभिन्न उदाहरण:

$\beta =2^{-i},\;\;i\in \left\{1,\dots ,\log \left({\frac {1}{\alpha }}\right)\right\}$ कहाँ $\beta$ की प्री-प्रोसेसिंग सीमा है $i$-वाँ उदाहरण. इस प्रकार, क्वेरी ब्लॉक से छोटे के लिए $1/\alpha$ $\lceil \log(1/\tau )\rceil$-वें उदाहरण पर सवाल उठाया गया है। जैसा कि ऊपर बताया गया है, इस डेटा संरचना में क्वेरी समय है $O(1/\tau )$ और आवश्यकता है $O\left(mn(H+1)\log ^{2}\left({\frac {1}{\alpha }}\right)\right)$ हफ़मैन-एन्कोडेड प्रतिलिपि को संग्रहीत करके अंतरिक्ष के टुकड़े (ध्यान दें)। $\log({\frac {1}{\alpha }})$ फ़ैक्टर और हफ़मैन कोडिंग भी देखें)।

एक-आयामी सरणियाँ

चान एट अल. डेटा संरचना का प्रस्ताव रखा जिसने आयामी सरणी दी$A$, उपश्रेणी $R$ का $A$ (क्वेरी समय पर निर्दिष्ट) और सीमा $\tau$ (क्वेरी समय पर निर्दिष्ट), सभी की सूची वापस करने में सक्षम है $\tau$-में बहुमत $O(1/\tau )$ समय की आवश्यकता है $O(n\log n)$ अंतरिक्ष के शब्द. ऐसे प्रश्नों का उत्तर देने के लिए, चैन एट अल।यह ध्यान देकर प्रारंभ करें कि डेटा संरचना मौजूद है जो किसी श्रेणी में शीर्ष-के सबसे अधिक बार आने वाली वस्तुओं को वापस करने में सक्षम है $O(k)$ समय की आवश्यकता है $O(n)$ अंतरिक्ष के शब्द. एक-आयामी सरणी के लिए $A[0,..,n-1]$, तरफा टॉप-के रेंज क्वेरी को फॉर्म का होने दें $A[0..i]{\text{ for }}0\leq i\leq n-1$. श्रेणियों की अधिकतम सीमा के लिए $A[0..i]{\text{ through }}A[0..j]$ जिसमें विशिष्ट तत्व की आवृत्ति होती है $e$ में $A$ अपरिवर्तित रहता है (और बराबर होता है $f$), क्षैतिज रेखा खंड का निर्माण किया जाता है। $x$वें>-इस रेखाखंड का अंतराल से मेल खाता है $[i,j]$ और इसमें है $y$-मूल्य के बराबर $f$. प्रत्येक तत्व को जोड़ने के बाद से $A$ ठीक विशिष्ट तत्व की आवृत्ति को बदलता है, उपरोक्त प्रक्रिया बनाता है $O(n)$ रेखा खंड। इसके अलावा, ऊर्ध्वाधर रेखा के लिए $x=i$ इसे प्रतिच्छेद करने वाले सभी क्षैतिज रेखाखंडों को उनकी आवृत्तियों के अनुसार क्रमबद्ध किया जाता है। ध्यान दें कि, प्रत्येक क्षैतिज रेखा खंड के साथ $x$-मध्यान्तर $[\ell ,r]$ बिल्कुल विशिष्ट तत्व से मेल खाता है $e$ में $A$, ऐसा है कि $A[\ell ]=e$. टॉप-के क्वेरी का उत्तर ऊर्ध्वाधर किरण को शूट करके दिया जा सकता है $x=i$ और सबसे पहले रिपोर्टिंग $k$ क्षैतिज रेखा खंड जो इसे प्रतिच्छेद करते हैं (ऊपर से याद रखें कि ये रेखा रेखा खंड पहले से ही उनकी आवृत्तियों के अनुसार क्रमबद्ध हैं) $O(k)$ समय।

चान एट अल.सबसे पहले रेंज ट्री का निर्माण करें जिसमें प्रत्येक ब्रांचिंग नोड तरफा रेंज टॉप-के प्रश्नों के लिए ऊपर वर्णित डेटा संरचना की प्रति संग्रहीत करता है और प्रत्येक पत्ता तत्व का प्रतिनिधित्व करता है $A$. प्रत्येक नोड पर टॉप-के डेटा संरचना का निर्माण उस नोड के उप-वृक्षों में मौजूद मूल्यों के आधार पर किया जाता है और इसका उद्देश्य एकतरफा रेंज टॉप-के प्रश्नों का उत्तर देना है। कृपया ध्यान दें कि एक-आयामी सरणी के लिए $A$, रेंज ट्री को विभाजित करके बनाया जा सकता है $A$ दो हिस्सों में और दोनों हिस्सों पर पुनरावृत्ति; इसलिए, परिणामी रेंज ट्री का प्रत्येक नोड रेंज का प्रतिनिधित्व करता है। यह भी देखा जा सकता है कि इस श्रेणी के पेड़ की आवश्यकता है $O(n\log n)$ अंतरिक्ष के शब्द, क्योंकि वहाँ हैं $O(\log n)$ स्तर और प्रत्येक स्तर $\ell$ है $2^{\ell }$ नोड्स. इसके अलावा, चूँकि प्रत्येक स्तर पर $\ell$ रेंज ट्री के सभी नोड्स का कुल योग होता है $n$ घटक $A$ उनके उपवृक्षों पर और चूँकि वहाँ हैं $O(\log n)$ स्तरों, इस रेंज ट्री की अंतरिक्ष जटिलता है $O(n\log n)$.

इस संरचना का उपयोग करते हुए, श्रेणी $\tau$-बहुमत प्रश्न $A[i..j]$ पर $A[0..n-1]$ साथ $0\leq i\leq j\leq n$ इसका उत्तर इस प्रकार दिया गया है। सबसे पहले, पत्ती नोड्स का निम्नतम सामान्य पूर्वज (LCA)। $i$ और $j$ स्थिर समय में पाया जाता है. ध्यान दें कि आवश्यक डेटा संरचना मौजूद है $O(n)$ अंतरिक्ष के टुकड़े जो एलसीए प्रश्नों का उत्तर देने में सक्षम हैं $O(1)$ समय। होने देना $z$ के एलसीए को निरूपित करें $i$ और $j$, का उपयोग करना $z$ और सीमा की विघटनशीलता के अनुसार $\tau$-अधिकांश प्रश्न (जैसा कि ऊपर और अंदर वर्णित है)। ), दो तरफा रेंज क्वेरी $A[i..j]$ दो एकतरफ़ा रेंज टॉप-के क्वेरीज़ (से) में परिवर्तित किया जा सकता है $z$ को $i$ और $j$). ये दो एकतरफ़ा रेंज टॉप-के क्वेरीज़ टॉप-( लौटाती हैं$1/\tau$) प्रत्येक संबंधित श्रेणी में सबसे अधिक बार आने वाले तत्व $O(1/\tau )$ समय। ये सामान्य तत्व उम्मीदवारों के समूह का निर्माण करते हैं $\tau$-में बहुमत $A[i..j]$ जिसमें हैं $O(1/\tau )$ उम्मीदवार जिनमें से कुछ गलत सकारात्मक हो सकते हैं। फिर प्रत्येक उम्मीदवार का रैखिक-अंतरिक्ष डेटा संरचना (जैसा कि लेम्मा 3 में वर्णित है) का उपयोग करके निरंतर समय में मूल्यांकन किया जाता है ) जो निर्धारित करने में सक्षम है $O(1)$ समय चाहे किसी सरणी की दी गई उपश्रेणी हो या नहीं $A$ कम से कम शामिल है $q$ किसी विशेष तत्व के उदाहरण $e$.

वृक्ष पथ

गैगी एट अल. डेटा संरचना प्रस्तावित की गई है जो दो नोड्स दिए गए प्रश्नों का समर्थन करती है $u$ और $v$ पेड़ में, उन तत्वों की सूची की रिपोर्ट करने में सक्षम हैं जिनकी तुलना में अधिक सापेक्ष आवृत्ति है $\tau$ से रास्ते पर $u$ को $v$. अधिक औपचारिक रूप से, आइए $T$ लेबल वाला पेड़ बनें जिसमें प्रत्येक नोड में आकार के वर्णमाला से लेबल हो $\sigma$. होने देना $label(u)\in [1,\dots ,\sigma ]$ नोड के लेबल को निरूपित करें $u$ में $T$. होने देना $P_{uv}$ से अद्वितीय पथ को निरूपित करें $u$ को $v$ में $T$ जिसमें मध्य नोड्स को उनके देखे जाने के क्रम में सूचीबद्ध किया गया है। दिया गया $T$, और निश्चित (पूर्व-प्रसंस्करण के दौरान निर्दिष्ट) सीमा $0<\tau <1$, पूछताछ $Q(u,v)$ से अधिक दिखाई देने वाले सभी लेबलों का सेट वापस करना होगा $\tau |P_{uv}|$ कई बार $P_{uv}$.

सबसे पहले इस डेटा संरचना का निर्माण करें ${O}(\tau n)$ नोड्स चिह्नित हैं. यह किसी भी नोड को चिह्नित करके किया जा सकता है जिसमें कम से कम दूरी हो $\lceil 1/\tau \rceil$ तीन के नीचे से (ऊंचाई) और जिसकी गहराई से विभाज्य है $\lceil 1/\tau \rceil$. ऐसा करने के बाद, यह देखा जा सकता है कि प्रत्येक नोड और उसके निकटतम चिह्नित पूर्वज के बीच की दूरी कम है $2\lceil 1/\tau \rceil$. चिह्नित नोड के लिए $x$, $\log(depth(x))$ विभिन्न अनुक्रम (जड़ की ओर पथ) $P_{i}(x)$ जमा हो जाती है,

$P_{i}(x)=\left\langle \operatorname {label} (x),\operatorname {par} (x),\operatorname {par} ^{2}(x),\ldots ,\operatorname {par} ^{2^{i}}(x)\right\rangle$ के लिए $0\leq i\leq \log(depth(x))$ कहाँ $\operatorname {par} (x)$ नोड के प्रत्यक्ष पैरेंट का लेबल लौटाता है $x$. दूसरे तरीके से कहें तो, प्रत्येक चिह्नित नोड के लिए, रूट की ओर दो लंबाई (प्लस नोड के लिए एक) की शक्ति वाले सभी पथों का सेट संग्रहीत किया जाता है। इसके अलावा, प्रत्येक के लिए $P_{i}(x)$, सभी बहुमत उम्मीदवारों का सेट $C_{i}(x)$ जमा हो जाती है। अधिक विशेष रूप से, $C_{i}(x)$ सभी का सेट शामिल है $(\tau /2)$-में बहुमत $P_{i}(x)$ या लेबल जो इससे अधिक दिखाई देते हैं $(\tau /2).(2^{i}+1)$ कई बार $P_{i}(x)$. यह देखना आसान है कि उम्मीदवारों का सेट $C_{i}(x)$ ज्यादा से ज्यादा हो सकता है $2/\tau$ प्रत्येक के लिए अलग-अलग लेबल $i$. गैगी एट अल.फिर ध्यान दें कि सभी का सेट $\tau$-किसी भी चिह्नित नोड से पथ में प्रमुखताएँ $x$ अपने पूर्वजों में से को $z$ कुछ में शामिल है $C_{i}(x)$ (लेम्मा 2 इंच) की लंबाई के बाद से $P_{i}(x)$ के बराबर है $(2^{i}+1)$ इस प्रकार वहाँ मौजूद है $P_{i}(x)$ के लिए $0\leq i\leq \log(depth(x))$ जिनकी लंबाई बीच में है $d_{xz}{\text{ and }}2d_{xz}$ कहाँ $d_{xz}$ x और z के बीच की दूरी है. ऐसे का अस्तित्व $P_{i}(x)$ तात्पर्य यह है कि ए $\tau$-बहुमत से रास्ते में $x$ को $z$ होना चाहिए $(\tau /2)$-बहुमत में $P_{i}(x)$, और इस प्रकार अवश्य प्रकट होना चाहिए $C_{i}(x)$. यह देखना आसान है कि इस डेटा संरचना की आवश्यकता है $O(n\log n)$ अंतरिक्ष के शब्द, क्योंकि जैसा कि निर्माण चरण में ऊपर बताया गया है $O(\tau n)$ नोड्स चिह्नित किए जाते हैं और प्रत्येक चिह्नित नोड के लिए कुछ उम्मीदवार सेट संग्रहीत किए जाते हैं। परिभाषा के अनुसार, प्रत्येक चिह्नित नोड के लिए $O(\log n)$ ऐसे सेट स्टोर हैं, जिनमें से प्रत्येक में शामिल है $O(1/\tau )$ उम्मीदवार। इसलिए, इस डेटा संरचना की आवश्यकता है $O(\log n\times (1/\tau )\times \tau n)=O(n\log n)$ अंतरिक्ष के शब्द. कृपया ध्यान दें कि प्रत्येक नोड $x$ भण्डारण भी करता है $count(x)$ जो कि उदाहरणों की संख्या के बराबर है $label(x)$ से रास्ते पर $x$ की जड़ तक $T$, इससे स्थान जटिलता नहीं बढ़ती क्योंकि यह केवल प्रति नोड शब्दों की स्थिर संख्या जोड़ता है।

दो नोड्स के बीच प्रत्येक क्वेरी $u$ और $v$ रेंज की डीकंपोज़बिलिटी प्रॉपर्टी (जैसा कि ऊपर बताया गया है) का उपयोग करके उत्तर दिया जा सकता है $\tau$-अधिकांश प्रश्न और बीच में प्रश्न पथ को तोड़कर $u$ और $v$ चार उपपथों में। होने देना $z$ का निम्नतम सामान्य पूर्वज हो $u$ और $v$, साथ $x$ और $y$ के निकटतम चिह्नित पूर्वज हैं $u$ और $v$ क्रमश। से रास्ता $u$ को $v$ से पथों में विघटित हो जाता है $u$ और $v$ को $x$ और $y$ क्रमशः (इन पथों का आकार छोटा है $2\lceil 1/\tau \rceil$ परिभाषा के अनुसार, इनमें से सभी को उम्मीदवार माना जाता है), और रास्ते $x$ और $y$ को $z$ (उपयुक्त ढूंढकर $C_{i}(x)$ जैसा कि ऊपर बताया गया है और इसके सभी लेबलों को उम्मीदवार के रूप में माना जा रहा है)। कृपया ध्यान दें कि, सीमा नोड्स को तदनुसार संभाला जाना चाहिए ताकि ये सभी उपपथ असंयुक्त हों और उन सभी से सेट हो $O(1/\tau )$ उम्मीदवार व्युत्पन्न है. इनमें से प्रत्येक उम्मीदवार को फिर के संयोजन का उपयोग करके सत्यापित किया जाता है $labelanc(x,\ell )$ क्वेरी जो नोड का निम्नतम पूर्वज लौटाती है $x$ उस पर लेबल है $\ell$ और यह $count(x)$ प्रत्येक नोड के फ़ील्ड. पर $w$-बिट रैम और आकार का वर्णमाला $\sigma$, द $labelanc(x,\ell )$ प्रश्न का उत्तर इसमें दिया जा सकता है $O\left(\log \log _{w}\sigma \right)$ रैखिक स्थान आवश्यकताओं के साथ समय। इसलिए, प्रत्येक का सत्यापन किया जा रहा है $O(1/\tau )$ उम्मीदवारों में $O\left(\log \log _{w}\sigma \right)$ समय परिणाम देता है $O\left((1/\tau )\log \log _{w}\sigma \right)$ सभी का सेट वापस करने के लिए कुल क्वेरी समय $\tau$-बहुसंख्यक राह पर हैं $u$ को $v$.

संबंधित समस्याएँ

ऊपर वर्णित सभी समस्याओं का अध्ययन उच्च आयामों के साथ-साथ उनके गतिशील संस्करणों के लिए भी किया गया है। दूसरी ओर, रेंज क्वेरीज़ को अन्य डेटा संरचनाओं जैसे ट्री (डेटा संरचना) तक बढ़ाया जा सकता है। जैसे कि स्तर पूर्वज समस्या। समस्याओं का समान परिवार श्रेणी खोज क्वेरीज़ हैं, जिन्हें गिनती क्वेरीज़ के रूप में भी जाना जाता है।

यह भी देखें

• स्तर पूर्वज समस्या
• निम्नतम सामान्य पूर्वज

बाहरी संबंध

• Open Data Structure - Chapter 13 - Data Structures for Integers
• Data Structures for Range Median Queries - Gerth Stolting Brodal and Allan Gronlund Jorgensen