एक RMQ विस्तार

Question

RMQ problem के लिए द्विआधारी अनुक्रमित पेड़ का उपयोग करना तो जैसे बढ़ाया जा सकता है:

को देखते हुए n पूर्णांकों A की एक सरणी है।

क्वेरी (एक्स, वाई): दिया दो पूर्णांकों 1 ≤ x, y ≤ n, A[x], A[x+1], ... A[y] की न्यूनतम प्राप्त होता है;

अद्यतन (एक्स, v): एक पूर्णांक v और 1 ≤ x ≤ nA[x] = v कर दिया।

segment trees का उपयोग कर दोनों परिचालनों के लिए इस समस्या को O(log n) में हल किया जा सकता है।

यह कागज पर एक कुशल समाधान है, लेकिन व्यावहारिक रूप से, सेगमेंट पेड़ में बहुत अधिक उपर है, विशेष रूप से यदि पुनरावर्ती रूप से कार्यान्वित किया जाता है।

मुझे इस तथ्य के बारे में पता है कि द्विआधारी अनुक्रमित पेड़ (अधिक संसाधन मिल सकते हैं, लेकिन this का उपयोग करके, संचालन के एक (या दोनों, मुझे यकीन नहीं है) के लिए O(log^2 n) में समस्या का समाधान करने का कोई तरीका है। this क्रमशः सबसे संक्षिप्त और संपूर्ण, आईएमओ हैं)। n के मानों के लिए यह समाधान, स्मृति में फिट है, अभ्यास में तेज़ है, क्योंकि बीआईटी के पास बहुत कम ओवरहेड है।

हालांकि, मुझे नहीं पता कि बीआईटी संरचना का उपयोग दिए गए कार्यों को करने के लिए कैसे किया जाता है। मुझे केवल यह पता है कि उदाहरण के लिए अंतराल राशि पूछने के लिए इसका उपयोग कैसे किया जाए। न्यूनतम खोजने के लिए मैं इसका उपयोग कैसे कर सकता हूं?

यदि यह मदद करता है, तो मेरे पास कोड है जो दूसरों ने लिखा है जो मैं पूछ रहा हूं, लेकिन मैं इसका एहसास नहीं कर सकता। यहाँ कोड में से एक इस तरह के टुकड़ा है:

int que(int l, int r) { 
    int p, q, m = 0; 

    for(p=r-(r&-r); l<=r; r=p, p-=p&-p) { 
     q = (p+1 >= l) ? T[r] : (p=r-1) + 1; 
     if(a[m] < a[q]) 
      m = q; 
    } 

    return m; 
} 

void upd(int x) { 
    int y, z; 
    for(y = x; x <= N; x += x & -x) 
     if(T[x] == y) { 
      z = que(x-(x&-x) + 1, x-1); 
      T[x] = (a[z] > a[x]) ? z : x; 
     } 
     else 
      if(a[ T[x] ] < a[ y ]) 
       T[x] = y; 
} 

उपरोक्त कोड में, T 0 के साथ आरंभ नहीं हो जाता, a दिया सरणी, N इसके आकार और upd (वे जो भी कारण के लिए 1 से इंडेक्सिंग करते हैं) पर कहा जाता है पहले प्रत्येक पढ़ने के मूल्य के लिए। upd से पहले a[x] = v को निष्पादित किया जाता है।

इसके अलावा, p & -p कुछ बीआईटी स्रोतों में p^(p & (p - 1)) जैसा ही है और इंडेक्सिंग शून्य से शुरू होने वाले शून्य तत्व के साथ 1 से शुरू होता है।

क्या कोई बता सकता है कि ऊपर दिए गए कार्यों या मैं बीआईटी के साथ दी गई समस्या को कैसे हल कर सकता हूं?

Answer 1

बिट नगण्य के ऊपर एक स्तर से, इस हमारे पास क्या है है।

g[k] = sum{ i = D(k) + 1 .. k } a[i] 

जहां D(k) सिर्फ सबसे कम आदेश 1 बिट 0 पर सेट के साथ k है यहाँ हम बजाय

T[k] = min{ i = D(k) + 1 .. k } a[i] 

है क्वेरी परिवर्तन यह है कि न्यूनतम के साथ एक सामान्य बीआईटी रेंज योग क्वेरी की तरह वास्तव में काम करता है subranges की राशि के रूप में पूछताछ के रूप में लिया जाता है। a में एन वस्तुओं के लिए, एन में छत (लॉग एन) बिट्स हैं, जो रन टाइम निर्धारित करती हैं।

अद्यतन अधिक काम करता है क्योंकि ओ (लॉग एन) subrange minima - i.e. g के तत्व - परिवर्तन से प्रभावित होते हैं, और प्रत्येक को हल करने के लिए स्वयं ओ (लॉग एन) क्वेरी लेती है। यह अद्यतन ओ (लॉग^2 एन) कुल मिलाकर बनाता है।

बिट फिडलिंग स्तर पर यह बेहद चालाक कोड है। कथन x += x & -xx में 1 की निम्नतम क्रम की लगातार स्ट्रिंग को साफ़ करता है और उसके बाद अगले उच्चतम क्रम शून्य को 1 पर सेट करता है। यह वही है जो आपको मूल पूर्णांक x के लिए बीआईटी को "ट्रैवर्स" करने की आवश्यकता है।

Answer 2

सेगमेंट पेड़ भी अभ्यास में एक कुशल समाधान हैं। हालांकि, आप उन्हें पेड़ों के रूप में लागू नहीं करते हैं। दौर n दो की अगली शक्ति तक और 2*n आकार के rmq का उपयोग करें। rmq की प्रविष्टियां A हैं। यदि j < n, तो rmq[j] = min(rmq[2*j], rmq[2*j+1])। श्रेणी-न्यूनतम क्वेरी का उत्तर देने के लिए आपको केवल rmq की लॉगरिदमिक रूप से कई प्रविष्टियों को देखने की आवश्यकता है। और A की प्रविष्टि अपडेट होने पर आपको rmq की लॉगरिदमिक रूप से कई प्रविष्टियों को अपडेट करने की आवश्यकता है।

मुझे आपका कोड समझ में नहीं आया, हालांकि, मैं इस पर टिप्पणी नहीं कर रहा हूं।

Answer 3

मैं विस्तार से कोड को देखा नहीं है, लेकिन यह निम्न योजना के साथ मोटे तौर पर संगत प्रतीत हो रहा है:

1) बीआईटी की संरचना रखें, कि, एक वृक्ष संरचना शक्तियों के आधार पर थोपना सरणी पर दो में से।

2) पेड़ के प्रत्येक नोड पर, उस नोड के किसी भी वंशज पर न्यूनतम मान रखें।

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

4) एक बार दो पॉइंटर्स एक ही पॉइंटर होते हैं, तो सीमा में न्यूनतम किसी भी नोड में न्यूनतम मान होता है जिसे आपने नोट किया है। पूर्णांक डेटा सरणी a भंडार लेकर रकम के लिए

एक सामान्य बीआईटी सरणी g: