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

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

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

परिभाषा

कुछ समुच्चय S के n तत्वों की एक सरणी $A=[a_{1},a_{2},..,a_{n}]$ पर एक श्रेणी क्वेरी $q_{f}(A,i,j)$, जिसे $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: न्यूनतम क्वेरी रेंज

जब किसी श्रेणी क्वेरी में रुचि का कार्य एक अर्धसमूह ऑपरेटर होता है, जिससे इसकी धारणा $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: रेंज मोड क्वेरी

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

रेंज मोड क्वेरीज़

स्पेस	प्रश्नोत्तरी समय	प्रतिबंध
$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}}$ सरणी .

rangeMedian(A, i, j, r) {
    if A.length() == 1
        return A[1]

    if A.low is undefined then
        m = median(A)
        A.low  = [e in A | e <= m]
        A.high = [e in A | e > m ]

    calculate t the number of elements of A[i, j] that belong to A.low

    if r <= t then
        return rangeMedian(A.low, i, j, r)
    else
        return rangeMedian(A.high, i, j, 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