RMQ समस्या - 2. लाइन ट्री

हमारे विषय के पहले भाग में , हमने (O (nlogn), O (1)) में स्थिर RMQ समस्या के समाधान की जाँच की। अब हम खंड, या अंतराल (अंग्रेजी साहित्य में - खंड वृक्ष या अंतराल वृक्ष) नामक वृक्ष की संरचना से निपटेंगे। इसका उपयोग करके, आप डायनामिक RMQ इन (O (n), O (logn)) को हल कर सकते हैं।

परिभाषा

हम खंडों के एक पेड़ की अवधारणा को पेश करते हैं। सुविधा के लिए, हम सरणी की लंबाई को दो की शक्ति में जोड़ते हैं। हम सरणी के जोड़े गए तत्वों में अनंतता को जोड़ते हैं (अनंत के लिए यह समझने के लिए सार्थक है, उदाहरण के लिए, एक संख्या अधिक है जिसमें डेटा में कुछ भी नहीं दिखता है)। तो, खंडों का वृक्ष एक द्विआधारी वृक्ष होता है, जिसके प्रत्येक शीर्ष पर एक निश्चित खंड पर एक दिए गए फलन का मान लिखा होता है। हमारे मामले में कार्य एक न्यूनतम है।

प्रत्येक शीट में एक सरणी तत्व होगा जिसमें पेड़ में शीट की क्रमिक संख्या के बराबर संख्या होती है। और प्रत्येक शिखर जो एक पत्ती नहीं है, इस शीर्ष के वंशज शीट्स के अनुरूप सरणी तत्वों के एक सेगमेंट के अनुरूप होगा।



परिभाषा की स्पष्ट संकीर्णता के पीछे एक पूरी तरह से सरल अवधारणा निहित है - हम अपनी आंखों को आकृति में बदल देते हैं।



आइए हम इसकी परिभाषा बताते हैं। चयनित वर्टेक्स चिह्नित सेगमेंट के अनुरूप होगा, क्योंकि यह दिए गए वर्टेक्स के सभी वंशज शीट्स का मिलन है (इस क्षण से शुरू होने पर, हम शीट और सरणी तत्व की पहचान करते हैं जो यह दर्शाता है)।

हम पेड़ को बाइनरी हीप की तरह स्टोर करेंगे। हमें सरणी T [2n - 1] मिलती है। जड़ सरणी के पहले तत्व में झूठ होगा, और आई-वें शीर्ष के बेटे क्रमशः 2i और 2i + 1 के साथ तत्वों में झूठ बोलेंगे - बाएं और दाएं, क्रमशः। आप तुरंत स्पष्ट संपत्ति नोटिस कर सकते हैं: टीथ [i] = मिनट (टी [2 आई], टी [2 आई + 1]) के लिए आईथ वर्टेक्स जो कि एक पत्ती नहीं है। शीट, वैसे, एन के 2 एन - 1 से संख्या वाले तत्वों में इस तरह के नंबरिंग के साथ झूठ होगा।

इमारत

हम (n - 1) वें से तत्वों के ऊपर जाकर एक पेड़ का निर्माण करेंगे, जो कि उनके शीर्ष के लिए बेटों में न्यूनतम मूल्यों को गिना जाएगा।
इस लेख से शुरू करके मैं अधिक स्पष्टता के लिए एक कोड दूंगा।

const int INF = INT_MAX; void build_tree(const vector<int>& V) { // ,     int n = (1 << (log(n - 1) + 1)); V.resize(2 * n, INF); //   for (int i = n; i < 2 * n; i++) V[i] = V[i - n]; //     for (int i = n - 1; i > 0; i--) V[i] = min(V[2 * i], V[2 * i + 1]); } 

Build_tree (V) फ़ंक्शन इस सरणी के लिए सरणी V को एक लाइन ट्री में बदल देता है। तो, अब इस पर एक सेगमेंट में न्यूनतम खोजने के लिए कैसे? ऐसा करने के लिए, हम एक मौलिक खंड की अवधारणा को पेश करते हैं।

न्यूनतम अनुरोध

हम सरणी में मूलभूत सेगमेंट को ऐसे सेगमेंट में कहते हैं कि पेड़ में एक शीर्ष होता है जिससे यह मेल खाती है। हम अपने सेगमेंट को न्यूनतम आधारभूत संख्या में विभाजित करते हैं। हम बताते हैं कि प्रत्येक स्तर पर उनकी संख्या 2 से अधिक नहीं है।



विभाजन में सबसे बड़ा मौलिक खंड लें। इसकी लंबाई 2t होने दें। ध्यान दें कि लंबाई 2t के मूलभूत खंड अधिकतम दो (1) हैं। बाईं ओर अधिकतम उपलब्ध मौलिक ले लो। हम इसे बाईं ओर स्थानांतरित करेंगे। ध्यान दें, फिर से, कि खंडों की लंबाई घट जाएगी (2)। तो यह अधिकतम के अधिकार के साथ है। इस प्रकार, हम यह प्राप्त करते हैं कि मूलभूत सेगमेंट अधिकतम 2t पर है, जो 2logn से अधिक नहीं है। पैराग्राफ (1) और (2) प्रमाण में मैं आत्म-प्रतिबिंब के लिए छोड़ दूँगा।

यह हमें कैसे मदद करता है? अब हम नीचे से न्यूनतम अनुरोध को लागू कर सकते हैं। यदि आवश्यक हो, तो हम नीचे से ऊपर उठेंगे, प्रत्येक स्तर पर उत्तर के लिए, एक मूल खंड।

हमें दो बिंदु मिलते हैं - l और r, जिसकी मदद से हम विभाजन के अगले मूलभूत खंडों को पाएंगे। प्रारंभ में, क्वेरी खंड के सिरों के अनुरूप शीट को इंगित करने के लिए l और r सेट करें। ध्यान दें कि यदि एल एक शीर्ष बिंदु की ओर इशारा करता है जो कि उसके माता-पिता का सही पुत्र है, तो यह शीर्ष भाग मौलिक खंडों में विभाजन से संबंधित है, अन्यथा ऐसा नहीं होता है। इसी तरह सूचक आर के साथ - यदि यह एक शीर्ष बिंदु की ओर इशारा करता है जो इसके माता-पिता का बायां पुत्र है, तो हम इसे विभाजन में जोड़ते हैं। उसके बाद, हम दोनों बिंदुओं को एक उच्च स्तर पर ले जाते हैं और ऑपरेशन को दोहराते हैं। हम ऑपरेशन जारी रखते हैं जब तक कि पॉइंटर्स एक के बाद एक आते हैं।

अगले मूलभूत सेगमेंट को खोजते हुए, हम उस पर न्यूनतम की तुलना वर्तमान में पाए जाने वाले न्यूनतम से करते हैं और यदि आवश्यक हो तो इसे कम करते हैं। एल्गोरिथ्म का स्पर्शोन्मुख व्यवहार O (logn) है, क्योंकि प्रत्येक स्तर पर हम निरंतर संचालन करते हैं, और कुल स्तर logn है।

 int rmq_up(vector<int>& T, int l, int r) { int ans = INF; int n = T.size() / 2; l += n - 1, r += n - 1; while (l <= r) { //  l -    , //     if (l & 1) ans = min(ans, T[l]); //  r -    , //     if (!(r & 1)) ans = min(ans, T[r]); //      l = (l + 1) / 2, r = (r - 1) / 2; } return ans; } 

परिवर्तन

अब हम सीखेंगे कि पेड़ के तत्व का मूल्य कैसे बदलें। ध्यान दें कि प्रत्येक पत्ती के लिए मूल खंडों के लॉग होते हैं जो इसमें समाहित होते हैं - ये सभी हमारे पत्ती से जड़ तक मार्ग पर पड़े हुए कोने के अनुरूप होते हैं।



इसलिए, एक तत्व को बदलते समय, बस इसके पत्ते से जड़ तक जाने और सूत्र T [i] = min (T [2i], T [2i + 1]) के अनुसार रास्ते के सभी कोने पर मूल्य को अद्यतन करने के लिए पर्याप्त है।

 void update(vector<int>& T, int i, int x) { int n = T.size() / 2; i += n – 1; T[i] = x; while (i /= 2) T[i] = min(T[2 * i], T[2 * i + 1]); } 

हुर्रे! हम (O (n), O (logn)) में गतिशील RMQ समस्या का समाधान प्राप्त करते हैं।

अगले लेख में, हम सीखेंगे कि ऊपर से अनुरोध कैसे करें। इस तथ्य के बावजूद कि ऊपर से अनुरोध का स्पर्शोन्मुख एक ही होगा, इसमें एक बड़ा गोखरू है - एक खंड पर संशोधन को आसानी से और आसानी से पेंच करने की क्षमता। जल्द मिलते हैं!