data-structures
खंड वृक्ष
खोज…
सेगमेंट ट्री का परिचय
मान लीजिए कि हमारे पास एक सरणी है:
+-------+-----+-----+-----+-----+-----+-----+
| Index | 0 | 1 | 2 | 3 | 4 | 5 |
+-------+-----+-----+-----+-----+-----+-----+
| Value | -1 | 3 | 4 | 0 | 2 | 1 |
+-------+-----+-----+-----+-----+-----+-----+
हम इस सरणी पर कुछ क्वेरी करना चाहते हैं। उदाहरण के लिए:
- इंडेक्स- 2 से इंडेक्स- 4 तक न्यूनतम क्या है? -> ०
- इंडेक्स- 0 से इंडेक्स- 3 तक अधिकतम क्या है? -> ४
- सूचकांक- 1 से सूचकांक- 5 का योग क्या है? -> १०
हम इसे कैसे खोज सकते हैं?
पाशविक बल:
हम शुरुआती इंडेक्स से फिनिशिंग इंडेक्स तक सरणी को पार कर सकते हैं और अपनी क्वेरी का जवाब दे सकते हैं। इस दृष्टिकोण में, प्रत्येक क्वेरी O(n)
समय लेती है, जहाँ n प्रारंभिक सूचकांक और परिष्करण सूचकांक के बीच का अंतर है। लेकिन क्या होगा अगर लाखों की संख्या और लाखों प्रश्न हैं? M प्रश्नों के लिए, यह O(mn)
समय लेगा। हमारे सरणी में 10⁵ मानों के लिए, यदि हम 10, प्रश्नों का संचालन करते हैं, तो सबसे खराब स्थिति के लिए, हमें 10। आइटमों का पता लगाने की आवश्यकता होगी।
गतिशील प्रोग्रामिंग:
हम विभिन्न श्रेणियों के लिए मूल्यों को संग्रहीत करने के लिए 6X6 मैट्रिक्स बना सकते हैं। न्यूनतम क्वेरी (RMQ) की सीमा के लिए, हमारा सरणी ऐसा दिखेगा:
0 1 2 3 4 5
+-----+-----+-----+-----+-----+-----+-----+
| | -1 | 3 | 4 | 0 | 2 | 1 |
+-----+-----+-----+-----+-----+-----+-----+
0 | -1 | -1 | -1 | -1 | -1 | -1 | -1 |
+-----+-----+-----+-----+-----+-----+-----+
1 | 3 | | 3 | 3 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+
2 | 4 | | | 4 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+
3 | 0 | | | | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+
4 | 2 | | | | | 2 | 1 |
+-----+-----+-----+-----+-----+-----+-----+
5 | 1 | | | | | | 1 |
+-----+-----+-----+-----+-----+-----+-----+
एक बार जब हम इस मैट्रिक्स का निर्माण कर लेते हैं, तो सभी RMQ का उत्तर देना पर्याप्त होगा। यहां, मैट्रिक्स [i] [j] इंडेक्स- i से इंडेक्स- j तक के न्यूनतम मूल्य को स्टोर करेगा। उदाहरण के लिए: सूचकांक- 2 से सूचकांक- 4 तक न्यूनतम मैट्रिक्स [2] [4] = 0 है । यह मैट्रिक्स O(1)
समय में क्वेरी का उत्तर देता है, लेकिन इसे संग्रहीत करने के लिए इस मैट्रिक्स और O(n²)
store O(n²)
स्थान को बनाने में O (n time ) समय लगता है। तो अगर n वास्तव में बड़ी संख्या है, तो यह बहुत अच्छा नहीं है।
खंड वृक्ष:
एक खंड पेड़ अंतराल, या खंडों के भंडारण के लिए एक पेड़ डेटा संरचना है। यह क्वेरी करने की अनुमति देता है कि कौन से संग्रहीत खंडों में दिए गए बिंदु हैं। सेगमेंट ट्री बनाने में O(n)
समय लगता है, इसे बनाए रखने के लिए O(n)
स्थान लेता है और यह O(logn)
समय में क्वेरी का उत्तर देता है।
खंड वृक्ष एक द्विआधारी वृक्ष है और दिए गए सरणी के तत्व उस पेड़ के पत्ते होंगे। जब तक हम एक तत्व तक नहीं पहुँचेंगे, तब तक हम सरणी को आधे हिस्से में विभाजित करके खंड का पेड़ बनाएंगे। तो हमारा मंडल हमें प्रदान करेगा:
अब अगर हम गैर-पत्ती के नोड्स को उनके पत्तों के न्यूनतम मूल्य से प्रतिस्थापित करते हैं, तो हमें यह मिलता है:
तो यह हमारा खंड वृक्ष है। हम देख सकते हैं कि, रूट नोड में पूरे सरणी का न्यूनतम मान होता है (रेंज [0,5]), इसके बाएं बच्चे में हमारे बाएं सरणी का न्यूनतम मान होता है (रेंज [0,2]), सही बच्चे में न्यूनतम होता है हमारे सही सरणी का मान (रेंज [3,5]) और इसी तरह। पत्ती नोड्स में प्रत्येक व्यक्तिगत बिंदु का न्यूनतम मूल्य होता है। हमें मिला:
अब इस पेड़ पर एक श्रेणी क्वेरी करते हैं। श्रेणी क्वेरी करने के लिए, हमें तीन स्थितियों की जाँच करनी होगी:
- आंशिक ओवरलैप: हम दोनों पत्तियों की जांच करते हैं।
- कुल ओवरलैप: हम नोड में संग्रहीत मान लौटाते हैं।
- ओवरलैप नहीं: हम एक बहुत बड़े मूल्य या अनन्तता लौटाते हैं।
मान लीजिए, हम रेंज [2,4] की जांच करना चाहते हैं, इसका मतलब है कि हम इंडेक्स- 2 से 4 तक न्यूनतम खोजना चाहते हैं। हम रूट से शुरू करेंगे और जाँचेंगे कि हमारे नोड्स में रेंज हमारे क्वेरी रेंज द्वारा ओवरलैप की गई है या नहीं। यहाँ,
- [2,4] पूरी तरह से ओवरलैप नहीं [0,5] । इसलिए हम दोनों दिशाओं की जाँच करेंगे।
- बाएं सबट्री पर, [2,4] आंशिक रूप से ओवरलैप्स [0,2] । हम दोनों दिशाओं की जाँच करेंगे।
- बाएं सबट्री पर, [2,4] ओवरलैप नहीं करता है [0,1] , इसलिए यह हमारे उत्तर में योगदान देने वाला नहीं है। हम अनंत लौटते हैं।
- दायीं ओर सबट्री पर, [2,4] पूरी तरह से ओवरलैप्स [2,2] । हम 4 लौटाते हैं।
इन दो लौटा मूल्यों (4, अनंत) का न्यूनतम 4 है । हमें इस हिस्से से 4 मिलते हैं।
- दायीं ओर सबट्री, [2,4] आंशिक रूप से ओवरलैप्स। इसलिए हम दोनों दिशाओं की जाँच करेंगे।
- बाएं सबट्री पर, [2,4] पूरी तरह से ओवरलैप [3,4] । हम 0 वापस करते हैं।
- सही उपशीर्षक में, [2,4] ओवरलैप नहीं करता है [5,5] । हम अनंत लौटते हैं।
इन दो लौटा मूल्यों (0, अनंत) का न्यूनतम 0 है । हमें इस हिस्से से 0 मिलता है।
- बाएं सबट्री पर, [2,4] आंशिक रूप से ओवरलैप्स [0,2] । हम दोनों दिशाओं की जाँच करेंगे।
- लौटाए गए मानों की न्यूनतम (4,0) 0 है । यह हमारी वांछित न्यूनतम सीमा [2,4] है ।
अब हम जाँच सकते हैं कि, हमारी क्वेरी चाहे जो भी हो, इस सेगमेंट ट्री से वांछित मान ज्ञात करने के लिए अधिकतम 4 चरण होंगे।
उपयोग:
- न्यूनतम क्वेरी सीमा
- सबसे कम सामान्य पूर्वज
- आलसी प्रपंच
- डायनामिक सबट्री सम
- उपेक्षा और न्यूनतम
- दोहरी फील्ड्स
- के-वें सबसे छोटा तत्व खोजना
- अनियंत्रित जोड़े की संख्या का पता लगाना
ऐरे का उपयोग करके सेगमेंट ट्री का कार्यान्वयन
मान लीजिए, हमारे पास एक सरणी है: Item = {-1, 0, 3, 6}
। हम दिए गए रेंज में न्यूनतम मूल्य का पता लगाने के लिए सेगमेंट्री सरणी का निर्माण करना चाहते हैं। हमारा खंड वृक्ष जैसा दिखेगा:
नोड्स के नीचे की संख्या प्रत्येक मूल्यों के सूचकांकों को दर्शाती है जिन्हें हम अपने सेगमेंटट्री सरणी में संग्रहीत करेंगे। हम देख सकते हैं कि, 4 तत्वों को संग्रहीत करने के लिए, हमें आकार की एक सरणी की आवश्यकता है। 7. यह मान निम्न द्वारा निर्धारित किया जाता है:
Procedure DetermineArraySize(Item):
multiplier := 1
n := Item.size
while multiplier < n
multiplier := multiplier * 2
end while
size := (2 * multiplier) - 1
Return size
इसलिए यदि हमारी लंबाई 5 है, तो हमारे सेगमेंटरी सरणी का आकार होगा: ( 8 * 2 ) - 1 = 15 । अब, नोड के बाएं और दाएं बच्चे की स्थिति का निर्धारण करने के लिए, यदि कोई नोड इंडेक्स i में है , तो उसकी स्थिति:
- लेफ्ट चाइल्ड द्वारा निरूपित किया जाता है: (2 * i) + 1 ।
- राइट चाइल्ड द्वारा निरूपित किया जाता है: (2 * i) + 2 ।
और सूचकांक में किसी भी नोड के माता-पिता का सूचकांक मेरे द्वारा निर्धारित किया जा सकता है: (i - 1) / 2 ।
तो हमारे उदाहरण का प्रतिनिधित्व करने वाला सेगमेंटट्री एरे जैसा दिखेगा:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+
| -1 | -1 | 3 | -1 | 0 | 3 | 6 |
+-----+-----+-----+-----+-----+-----+-----+
आइए इस सरणी का निर्माण करने के लिए छद्म कोड देखें:
Procedure ConstructTree(Item, SegmentTree, low, high, position):
if low is equal to high
SegmentTree[position] := Item[low]
else
mid := (low+high)/2
constructTree(Item, SegmentTree, low, mid, 2*position+1)
constructTree(Item, SegmentTree, mid+1, high, 2*position+2)
SegmentTree[position] := min(SegmentTree[2*position+1], SegmentTree[2*position+2])
end if
सबसे पहले, हम मूल्यों का इनपुट लेते हैं और आइटम आकार की लंबाई का उपयोग करके infinity
साथ सेगमेंट्री सरणी को इसके आकार के रूप में आरंभीकृत करते हैं। हम प्रक्रिया का उपयोग करके कॉल करते हैं:
- निम्न = आइटम सरणी का आरंभिक सूचकांक।
- आइटम सरणी का उच्च = फिनिशिंग इंडेक्स।
- स्थिति = 0, हमारे सेगमेंट ट्री की जड़ को इंगित करता है।
अब, आइए एक उदाहरण का उपयोग करके प्रक्रिया को समझने का प्रयास करें:
हमारे आइटम सरणी का आकार 4 है । हम लंबाई की एक सरणी बनाते हैं (4 * 2) - 1 = 7 और उन्हें infinity
साथ प्रारंभ करते हैं। आप इसके लिए बहुत बड़े मूल्य का उपयोग कर सकते हैं। हमारे सरणी की तरह दिखेगा:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+
| inf | inf | inf | inf | inf | inf | inf |
+-----+-----+-----+-----+-----+-----+-----+
चूंकि यह एक पुनरावर्ती प्रक्रिया है, इसलिए हम एक पुनरावृत्ति तालिका का उपयोग करके ConstructTree
के संचालन को देखेंगे जो प्रत्येक कॉल पर low
, high
, position
, mid
और calling line
का ट्रैक रखता है। सबसे पहले, हम कंस्ट्रक्टट्री (आइटम, सेगमेंटट्री, 0, 3, 0) कहते हैं । इधर, low
समान नहीं है के रूप में high
, हम एक मिल जाएगा mid
। calling line
इंगित करती है कि कौन सा ConstructTree
इस बयान के बाद कहा जाता है। हम निरूपित ConstructTree
1 और 2 क्रमशः के रूप में प्रक्रिया के अंदर कॉल। हमारी तालिका इस तरह दिखाई देगी:
+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
| 0 | 3 | 0 | 1 | 1 |
+-----+------+----------+-----+--------------+
इसलिए जब हम ConstructTree-1
कहते हैं, तो हम पास होते हैं: low = 0
, high = mid = 1
, position = 2*position+1 = 2*0+1 = 1
। एक चीज जिसे आप नोटिस कर सकते हैं, वह है 2*position+1
, जड़ का बायाँ बच्चा है, जो कि 1 है । चूंकि low
high
बराबर नहीं है, हम एक mid
प्राप्त करते हैं। हमारी तालिका इस तरह दिखाई देगी:
+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
| 0 | 3 | 0 | 1 | 1 |
+-----+------+----------+-----+--------------+
| 0 | 1 | 1 | 0 | 1 |
+-----+------+----------+-----+--------------+
अगले पुनरावर्ती कॉल में, हम low = 0
, high = mid = 0
, position = 2*position+1 = 2*1+1=3
। फिर से इंडेक्स 1 का बायां बच्चा 3 है । यहां, low
ई high
, इसलिए हमने SegmentTree[position] = SegmentTree[3] = Item[low] = Item[0] = -1
। हमारा SegmentTree सरणी कैसा दिखेगा:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+
| inf | inf | inf | -1 | inf | inf | inf |
+-----+-----+-----+-----+-----+-----+-----+
हमारी पुनरावृत्ति तालिका इस तरह दिखाई देगी:
+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
| 0 | 3 | 0 | 1 | 1 |
+-----+------+----------+-----+--------------+
| 0 | 1 | 1 | 0 | 1 |
+-----+------+----------+-----+--------------+
| 0 | 0 | 3 | | |
+-----+------+----------+-----+--------------+
तो आप देख सकते हैं, -1 को अपनी सही स्थिति मिल गई है। चूंकि यह पुनरावर्ती कॉल पूर्ण है, इसलिए हम अपनी पुनरावर्ती तालिका की पिछली पंक्ति पर वापस जाते हैं। टेबल:
+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
| 0 | 3 | 0 | 1 | 1 |
+-----+------+----------+-----+--------------+
| 0 | 1 | 1 | 0 | 1 |
+-----+------+----------+-----+--------------+
हमारी प्रक्रिया में, हम ConstructTree-2
कॉल को निष्पादित करते हैं। इस बार, हम low = mid+1 = 1
, high = 1
, position = 2*position+2 = 2*1+2 = 4
। हमारी calling line
2 में बदल जाती है। हमें मिला:
+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
| 0 | 3 | 0 | 1 | 1 |
+-----+------+----------+-----+--------------+
| 0 | 1 | 1 | 0 | 2 |
+-----+------+----------+-----+--------------+
चूंकि, low
high
बराबर है, इसलिए हम सेट करते हैं: SegmentTree[position] = SegmentTree[4] = Item[low] = Item[1] = 2
। हमारा सेगमेंट्री सरणी:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+
| inf | inf | inf | -1 | 2 | inf | inf |
+-----+-----+-----+-----+-----+-----+-----+
हमारी पुनरावर्तन तालिका:
+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
| 0 | 3 | 0 | 1 | 1 |
+-----+------+----------+-----+--------------+
| 0 | 1 | 1 | 0 | 2 |
+-----+------+----------+-----+--------------+
| 1 | 1 | 4 | | |
+-----+------+----------+-----+--------------+
फिर से आप देख सकते हैं, 2 को इसकी सही स्थिति मिल गई है। इस पुनरावर्ती कॉल के बाद, हम अपनी पुनरावृत्ति तालिका की पिछली पंक्ति पर वापस जाते हैं। हमें मिला:
+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
| 0 | 3 | 0 | 1 | 1 |
+-----+------+----------+-----+--------------+
| 0 | 1 | 1 | 0 | 2 |
+-----+------+----------+-----+--------------+
हम अपनी प्रक्रिया की अंतिम पंक्ति, SegmentTree[position] = SegmentTree[1] = min(SegmentTree[2*position+1], SegmentTree[2*position+2]) = min(SegmentTree[3], SegmentTree[4]) = min(-1,2) = -1
। हमारा सेगमेंट्री सरणी:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+
| inf | -1 | inf | -1 | 2 | inf | inf |
+-----+-----+-----+-----+-----+-----+-----+
चूंकि यह पुनरावर्तन कॉल पूर्ण है, हम अपनी पुनरावृत्ति तालिका की पिछली पंक्ति पर वापस जाते हैं और ConstructTree-2
:
+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
| 0 | 3 | 0 | 1 | 2 |
+-----+------+----------+-----+--------------+
हम देख सकते हैं कि हमारे खंड के पेड़ का बायां हिस्सा पूरा हो गया है। यदि हम इस तरीके से जारी रखते हैं, तो पूरी प्रक्रिया को पूरा करने के बाद, हम आखिर में एक पूरा सेगमेंटट्री ऐरे प्राप्त करेंगे, जो इस तरह दिखेगा:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+
| -1 | -1 | 0 | -1 | 2 | 4 | 0 |
+-----+-----+-----+-----+-----+-----+-----+
इस सेगमेंट्री सरणी के निर्माण का समय और स्थान जटिलता है: O(n)
, जहां n आइटम सरणी में तत्वों की संख्या को दर्शाता है। हमारे निर्मित सेगमेंट्री सरणी का उपयोग रेंज न्यूनतम क्वेरी (आरएमक्यू) करने के लिए किया जा सकता है। श्रेणी अधिकतम क्वेरी करने के लिए एक सरणी बनाने के लिए, हमें लाइन को बदलने की आवश्यकता है:
SegmentTree[position] := min(SegmentTree[2*position+1], SegmentTree[2*position+2])
साथ में:
SegmentTree[position] := max(SegmentTree[2*position+1], SegmentTree[2*position+2])
एक सीमा न्यूनतम क्वेरी का प्रदर्शन
आरएमक्यू प्रदर्शन करने की प्रक्रिया पहले से ही परिचय में दिखाई गई है। रेंज न्यूनतम क्वेरी की जाँच के लिए छद्म कोड होगा:
Procedure RangeMinimumQuery(SegmentTree, qLow, qHigh, low, high, position):
if qLow <= low and qHigh >= high //Total Overlap
Return SegmentTree[position]
else if qLow > high || qHigh < low //No Overlap
Return infinity
else //Partial Overlap
mid := (low+high)/2
Return min(RangeMinimumQuery(SegmentTree, qLow, qHigh, low, mid, 2*position+1),
RangeMinimumQuery(SegmentTree, qLow, qHigh, mid+1, high, 2*position+2))
end if
यहाँ, qLow = The lower range of our query
, qHigh = The upper range of our query
qLow = The lower range of our query
qHigh = The upper range of our query
। low = starting index of Item array
high = Finishing index of Item array
, position = root = 0
। अब हम पहले बनाए गए उदाहरण का उपयोग करके प्रक्रिया को समझने की कोशिश करते हैं:
हमारा सेगमेंट्री सरणी:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+
| -1 | -1 | 0 | -1 | 2 | 4 | 0 |
+-----+-----+-----+-----+-----+-----+-----+
हम न्यूनतम सीमा [1,3] में खोजना चाहते हैं।
चूंकि यह एक पुनरावर्ती प्रक्रिया है, हम एक पुनरावृत्ति तालिका का उपयोग करके RangeMinimumQuery
के संचालन को देखेंगे जो qLow
, qHigh
, low
, high
, position
, mid
और calling line
ट्रैक रखता है। सबसे पहले, हम RangeMinimumQuery (SegmentTree, 1, 3, 0, 3, 0) को कॉल करते हैं । यहां, पहले दो स्थितियां पूरी नहीं होती हैं (आंशिक ओवरलैप)। हमें एक mid
मिलेगा। calling line
इंगित RangeMinimumQuery
है कि इसके बाद RangeMinimumQuery
कहा जाता है। कथन। हम क्रमशः 1 और 2 के रूप में कार्यविधि के अंदर RangeMinimumQuery
कॉल निरूपित करते हैं। हमारी तालिका इस तरह दिखाई देगी:
+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 0 | 3 | 0 | 1 | 1 |
+------+-------+-----+------+----------+-----+--------------+
इसलिए जब हम RangeMinimumQuery-1
, तो हम पास करते हैं: low = 0
, high = mid = 1
, position = 2*position+1 = 1
। एक चीज जिसे आप नोटिस कर सकते हैं, वह है 2*position+1
नोड का बायां बच्चा। इसका मतलब है कि हम रूट के बाएं बच्चे की जाँच कर रहे हैं। चूंकि [1,3] आंशिक रूप से ओवरलैप होता है [0,1] , पहले दो स्थितियां पूरी नहीं होती हैं, हमें एक mid
मिलता है। हमारी मेज:
+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 0 | 3 | 0 | 1 | 1 |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 0 | 1 | 1 | 0 | 1 |
+------+-------+-----+------+----------+-----+--------------+
अगली पुनरावर्ती कॉल में, हम low = 0
, high = mid = 0
, position = 2*position+1 = 3
। हम अपने पेड़ की बाईं पत्ती तक पहुँचते हैं। चूंकि [1,3] [0,0] के साथ ओवरलैप नहीं होता है, हम अपने कॉलिंग फ़ंक्शन के लिए infinity
लौटते हैं। पुनरावर्तन तालिका:
+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 0 | 3 | 0 | 1 | 1 |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 0 | 1 | 1 | 0 | 1 |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 0 | 0 | 3 | | |
+------+-------+-----+------+----------+-----+--------------+
चूंकि यह पुनरावर्ती कॉल पूर्ण है, इसलिए हम अपनी पुनरावर्ती तालिका की पिछली पंक्ति पर वापस जाते हैं। हमें मिला:
+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 0 | 3 | 0 | 1 | 1 |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 0 | 1 | 1 | 0 | 1 |
+------+-------+-----+------+----------+-----+--------------+
हमारी प्रक्रिया में, हम RangeMinimumQuery-2
कॉल को निष्पादित RangeMinimumQuery-2
। इस बार, हम low = mid+1 = 1
, high = 1
और position = 2*position+2 = 4
। हमारी calling line changes to **2**
। हमें मिला:
+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 0 | 3 | 0 | 1 | 1 |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 0 | 1 | 1 | 0 | 2 |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 1 | 1 | 4 | | |
+------+-------+-----+------+----------+-----+--------------+
इसलिए हम पिछले नोड के सही बच्चे के लिए जा रहे हैं। इस बार कुल ओवरलैप है। हम SegmentTree[position] = SegmentTree[4] = 2
का मान SegmentTree[position] = SegmentTree[4] = 2
।
+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 0 | 3 | 0 | 1 | 1 |
+------+-------+-----+------+----------+-----+--------------+
कॉलिंग फ़ंक्शन पर वापस, हम जाँच कर रहे हैं कि दो कॉलिंग फ़ंक्शन के दो लौटाए गए मानों में से न्यूनतम क्या है। स्पष्ट रूप से न्यूनतम 2 है , हम कॉलिंग फ़ंक्शन में 2 वापस करते हैं। हमारी पुनरावर्तन तालिका इस प्रकार है:
+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 0 | 3 | 0 | 1 | 1 |
+------+-------+-----+------+----------+-----+--------------+
हम अपने सेगमेंट के पेड़ के बाएं हिस्से को देख रहे हैं। अब हम यहां से RangeMinimumQuery-2
। हम low = mid+1 = 1+1 =2
, high = 3
और position = 2*position+2 = 2
। हमारी मेज:
+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 0 | 3 | 0 | 1 | 1 |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 2 | 3 | 2 | | |
+------+-------+-----+------+----------+-----+--------------+
कुल ओवरलैप है। इसलिए हम मान SegmentTree[position] = SegmentTree[2] = 0
: SegmentTree[position] = SegmentTree[2] = 0
। हम उस पुनरावर्तन पर वापस आते हैं जहां से इन दो बच्चों को बुलाया गया था और न्यूनतम (4,0) मिलता है , जो कि 0 है और मान लौटाता है।
प्रक्रिया को निष्पादित करने के बाद, हमें 0 मिलता है, जो कि सूचकांक -1 से सूचकांक- 3 तक न्यूनतम है।
इस प्रक्रिया के लिए रनटाइम जटिलता O(logn)
जहां n आइटम सरणी में तत्वों की संख्या है। रेंज अधिकतम क्वेरी करने के लिए, हमें लाइन को बदलने की आवश्यकता है:
Return min(RangeMinimumQuery(SegmentTree, qLow, qHigh, low, mid, 2*position+1),
RangeMinimumQuery(SegmentTree, qLow, qHigh, mid+1, high, 2*position+2))
साथ में:
Return max(RangeMinimumQuery(SegmentTree, qLow, qHigh, low, mid, 2*position+1),
RangeMinimumQuery(SegmentTree, qLow, qHigh, mid+1, high, 2*position+2))
आलसी प्रपंच
मान लीजिए, आपने पहले ही एक सेगमेंट ट्री बना लिया है। आपको ऐरे के मानों को अपडेट करने की आवश्यकता है, इससे न केवल आपके सेगमेंट के पेड़ के पत्ते नोड्स बदल जाएंगे, बल्कि कुछ नोड्स में न्यूनतम / अधिकतम भी होंगे। आइए इसे एक उदाहरण से देखें:
यह हमारा 8 तत्वों का न्यूनतम खंड का पेड़ है। आपको एक त्वरित अनुस्मारक देने के लिए, प्रत्येक नोड उनके बगल में उल्लिखित सीमा के न्यूनतम मूल्य का प्रतिनिधित्व करता है। आइए कहते हैं, हम 3 से हमारे सरणी के पहले आइटम के मूल्य बढ़ाने के लिए चाहते हैं। हम वह कैसे कर सकते है? हम उस तरीके का अनुसरण करेंगे जिसमें हमने RMQ का आयोजन किया था। प्रक्रिया इस तरह दिखाई देगी:
- सबसे पहले, हम रूट को पार करते हैं। [0,0] आंशिक रूप से [0,7] के साथ ओवरलैप होता है, हम दोनों दिशाओं में जाते हैं।
- बाएं सबट्री पर, [0,0] आंशिक रूप से [0,3] के साथ ओवरलैप होता है, हम दोनों दिशाओं में जाते हैं।
- बाएं सबट्री पर, [0,0] आंशिक रूप से [0,1] के साथ ओवरलैप होता है, हम दोनों दिशाओं में जाते हैं।
- बाएं सबट्री पर, [0,0] पूरी तरह से [0,0] के साथ ओवरलैप होता है, और इसकी लीफ नोड के बाद से, हम नोड को 3 के मान से बढ़ाकर अपडेट करते हैं। और मान -1 + 3 = 2 वापस करें ।
- सही सबट्री पर, [1,1] [0,0] के साथ ओवरलैप नहीं होता है, हम नोड ( 2 ) पर मान लौटाते हैं।
इन दो लौटे मूल्यों ( 2 , 2 ) का न्यूनतम 2 है , इसलिए हम वर्तमान नोड के मूल्य को अपडेट करते हैं और इसे वापस करते हैं।
- सही सबट्री पर [2,3] [0,0] के साथ ओवरलैप नहीं होता है, हम नोड का मान लौटाते हैं। ( १ )।
चूँकि इन दो लौटे हुए मानों ( 2 , 1 ) का न्यूनतम 1 है , हम वर्तमान नोड के मान को अद्यतन करते हैं और इसे वापस करते हैं।
- बाएं सबट्री पर, [0,0] आंशिक रूप से [0,1] के साथ ओवरलैप होता है, हम दोनों दिशाओं में जाते हैं।
- दायीं ओर सबट्री [4,7] [0,0] के साथ ओवरलैप नहीं होता है, हम नोड का मान लौटाते हैं। ( १ )।
- बाएं सबट्री पर, [0,0] आंशिक रूप से [0,3] के साथ ओवरलैप होता है, हम दोनों दिशाओं में जाते हैं।
- अंत में रूट नोड का मूल्य दो लौटे मूल्यों (1,1) 1 है की न्यूनतम के बाद से अद्यतन किया जाता है।
हम देख सकते हैं कि, एक नोड को अपडेट करने के लिए O(logn)
समय जटिलता की आवश्यकता होती है, जहां n पत्ती नोड्स की संख्या होती है। इसलिए यदि हमें i से j तक कुछ नोड्स अपडेट करने के लिए कहा जाए, तो हमें O(nlogn)
टाइम जटिलता की आवश्यकता होगी। यह n के एक बड़े मूल्य के लिए बोझिल हो जाता है। आइए आलसी बनें यानी जरूरत पड़ने पर ही काम करें। कैसे? जब हमें एक अंतराल को अपडेट करने की आवश्यकता होती है, तो हम एक नोड को अपडेट करेंगे और उसके बच्चे को चिह्नित करेंगे कि इसे अद्यतन करने की आवश्यकता है और जब आवश्यक हो तो इसे अपडेट करें। इसके लिए हमें एक सेगमेंट के पेड़ के समान आकार के एक आलसी आलसी की आवश्यकता है। प्रारंभ में आलसी सरणी के सभी तत्व 0 का प्रतिनिधित्व करेंगे कि कोई अद्यतन लंबित नहीं है। यदि आलसी [i] में गैर-शून्य तत्व है, तो इस तत्व को किसी भी क्वेरी ऑपरेशन करने से पहले खंड पेड़ में नोड I को अपडेट करने की आवश्यकता है। हम ऐसा कैसे करने जा रहे हैं? आइए एक उदाहरण देखें:
आइए बताते हैं, हमारे उदाहरण के पेड़ के लिए, हम कुछ प्रश्नों को निष्पादित करना चाहते हैं। य़े हैं:
- वेतन वृद्धि [0,3] 3 से ।
- वेतन वृद्धि [0,3] 1 से ।
- वेतन वृद्धि [0,0] 2 से ।
वेतन वृद्धि [0,3] 3 से:
हम रूट नोड से शुरू करते हैं। सबसे पहले, हम जांचते हैं कि क्या यह मान अप-टू-डेट है। इसके लिए हम अपने आलसी सरणी की जाँच करते हैं जो 0 है , इसका मतलब है कि मान अप-टू-डेट है। [0,3] आंशिक रूप से ओवरलैप [0,7] । तो हम दोनों दिशाओं में जाते हैं।
- बाएं सबट्री पर, कोई लंबित अपडेट नहीं है। [0,3] पूरी तरह से ओवरलैप [0,3] । इसलिए हम नोड का मान 3 से अपडेट करते हैं। तो मान -1 + 3 = 2 हो जाता है। इस बार, हम पूरे रास्ते नहीं जा रहे हैं। नीचे जाने के बजाय, हम अपने वर्तमान नोड के आलसी पेड़ में संबंधित बच्चे को अपडेट करते हैं और उन्हें 3 से बढ़ाते हैं। हम वर्तमान नोड का मान भी लौटाते हैं।
- सही सबट्री पर, कोई अद्यतन लंबित नहीं है। [0,3] ओवरलैप नहीं करता है [4,7] । इसलिए हम वर्तमान नोड (1) का मान लौटाते हैं।
दो लौटे मूल्यों ( 2 , 1 ) का न्यूनतम 1 है । हम रूट नोड को 1 में अपडेट करते हैं।
हमारे सेगमेंट ट्री और आलसी ट्री की तरह दिखेगा:
हमारे आलसी ट्री के नोड्स में गैर-शून्य मान प्रतिनिधित्व करता है, उन नोड्स और नीचे में अपडेट लंबित हैं। आवश्यकता पड़ने पर हम उन्हें अपडेट करेंगे। अगर हमसे पूछा जाए कि सीमा [0,3] में न्यूनतम क्या है, तो हम रूट नोड के बाईं ओर आएंगे और चूंकि कोई लंबित अपडेट नहीं है, हम 2 को वापस करेंगे, जो सही है। इसलिए यह प्रक्रिया हमारे सेगमेंट ट्री एल्गोरिदम की शुद्धता को प्रभावित नहीं करती है।
वेतन वृद्धि [0,3] 1 से:
- हम रूट नोड से शुरू करते हैं। कोई अद्यतन लंबित नहीं है। [0,3] आंशिक रूप से ओवरलैप [0,7] । इसलिए हम दोनों दिशाओं में जाते हैं।
- बाएं सबट्री में, कोई लंबित अपडेट नहीं है। [0,3] पूरी तरह से ओवरलैप [0,3] । हम वर्तमान नोड को अपडेट करते हैं: 2 + 1 = 3 । चूंकि यह एक आंतरिक नोड है, इसलिए हम आलसी ट्री में अपने बच्चों को 1 से बढ़ने के लिए अपडेट करते हैं। हम वर्तमान नोड ( 3 ) का मान भी लौटाएंगे।
- सही सबट्री में, कोई अद्यतन लंबित नहीं है। [0,3] ओवरलैप नहीं करता है [4,7] । हम वर्तमान नोड ( 1 ) का मान लौटाते हैं।
- हम दो लौटे मान ( 3 , 1 ) की न्यूनतम राशि लेकर रूट नोड को अपडेट करते हैं।
हमारे सेगमेंट ट्री और आलसी ट्री की तरह दिखेगा:
जैसा कि आप देख सकते हैं, हम आलसी ट्री में अपडेट जमा कर रहे हैं लेकिन इसे नीचे नहीं धकेल रहे हैं। यह आलसी प्रचार का मतलब है। यदि हमने इसका उपयोग नहीं किया है, तो हमें मूल्यों को पत्तियों तक नीचे धकेलना होगा, जिससे हमें अधिक अनावश्यक समय की जटिलता का सामना करना पड़ेगा।
2 से वेतन वृद्धि [0,0]:
- हम रूट नोड से शुरू करते हैं। चूंकि रूट अप-टू-डेट है और [0,0] आंशिक रूप से ओवरलैप करता है [0,7] , हम दोनों दिशाओं में जाते हैं।
- बाएं सबट्री पर, वर्तमान नोड अप-टू-डेट है और [0,0] आंशिक रूप से ओवरलैप करता है [0,3] , हम दोनों दिशाओं में जाते हैं।
- बाएं सबट्री पर, लेज़ी ट्री में वर्तमान नोड में एक गैर-शून्य मान है। इसलिए एक अद्यतन है जो इस नोड के लिए अभी तक प्रचारित नहीं किया गया है। हम अपने सेगमेंट ट्री में सबसे पहले इस नोड को अपडेट करने जा रहे हैं। तो यह -1 + 4 = 3 हो जाता है। फिर हम आलसी ट्री में अपने बच्चों को यह 4 प्रचारित करने जा रहे हैं। जैसा कि हमने पहले ही वर्तमान नोड को अपडेट कर दिया है, हम आलसी ट्री में वर्तमान नोड के मान को 0 में बदल देंगे। फिर [0,0] आंशिक रूप से ओवरलैप [0,1] , इसलिए हम दोनों दिशाओं में जाते हैं।
- बाएँ नोड पर, मान को अद्यतन करने की आवश्यकता है क्योंकि Lazy ट्री के वर्तमान नोड में एक गैर-शून्य मान है। इसलिए हम मान को -1 + 4 = 3 में अपडेट करते हैं। अब, के बाद से [0,0] पूरी तरह से overlaps [0,0], हम 3 + 2 = 5 करने के लिए वर्तमान नोड का मान अपडेट। यह एक पत्ती नोड है, इसलिए हमें अब मूल्य का प्रचार करने की आवश्यकता नहीं है। हम आलसी ट्री में 0 से संबंधित नोड को अपडेट करते हैं क्योंकि सभी नोड इस नोड तक प्रचारित किए गए हैं। हम वर्तमान नोड ( 5 ) का मान लौटाते हैं।
- सही नोड पर, मान को अद्यतन करने की आवश्यकता है। तो मान बन जाता है: 4 + 2 = 6 । चूंकि [0,0] ओवरलैप नहीं करता है [1,1] , हम वर्तमान नोड ( 6 ) का मान लौटाते हैं। हम आलसी ट्री में मूल्य को 0 पर भी अपडेट करते हैं। यह एक पत्ती नोड है क्योंकि कोई प्रसार की आवश्यकता है।
हम दो लौटे मानों ( 5 , 6 ) का उपयोग करके वर्तमान नोड को अपडेट करते हैं। हम वर्तमान नोड ( 5 ) का मान लौटाते हैं।
- सही सबट्री पर, एक लंबित अपडेट है। हम नोड के मूल्य को 1 + 4 = 5 पर अपडेट करते हैं। चूंकि यह एक पत्ती नोड नहीं है, हम अपने आलसी ट्री में इसके बच्चों के लिए मूल्य का प्रचार करते हैं और वर्तमान नोड को 0 पर अपडेट करते हैं। चूंकि [0,0] [2,3] के साथ ओवरलैप नहीं होता है, हम अपने वर्तमान नोड ( 5 ) का मान लौटाते हैं।
हम दिए गए मानों ( 5 , 5 ) का न्यूनतम उपयोग करके वर्तमान नोड को अपडेट करते हैं और मान ( 5 ) लौटाते हैं।
- बाएं सबट्री पर, लेज़ी ट्री में वर्तमान नोड में एक गैर-शून्य मान है। इसलिए एक अद्यतन है जो इस नोड के लिए अभी तक प्रचारित नहीं किया गया है। हम अपने सेगमेंट ट्री में सबसे पहले इस नोड को अपडेट करने जा रहे हैं। तो यह -1 + 4 = 3 हो जाता है। फिर हम आलसी ट्री में अपने बच्चों को यह 4 प्रचारित करने जा रहे हैं। जैसा कि हमने पहले ही वर्तमान नोड को अपडेट कर दिया है, हम आलसी ट्री में वर्तमान नोड के मान को 0 में बदल देंगे। फिर [0,0] आंशिक रूप से ओवरलैप [0,1] , इसलिए हम दोनों दिशाओं में जाते हैं।
- सही उपशीर्षक में, कोई लंबित अपडेट नहीं है और चूंकि [0,0] ओवरलैप नहीं करता है [4,7] , हम वर्तमान नोड ( 1 ) का मान लौटाते हैं।
- बाएं सबट्री पर, वर्तमान नोड अप-टू-डेट है और [0,0] आंशिक रूप से ओवरलैप करता है [0,3] , हम दोनों दिशाओं में जाते हैं।
- हम दो लौटे मान ( 5 , 1 ) के न्यूनतम का उपयोग करके रूट नोड को अपडेट करते हैं।
हमारे सेगमेंट ट्री और आलसी ट्री की तरह दिखेगा:
हम नोटिस कर सकते हैं कि, [0,0] पर मूल्य, जब जरूरत हो, सभी वेतन वृद्धि मिली।
अब अगर आपको न्यूनतम सीमा [3,5] खोजने के लिए कहा जाता है, यदि आप इस बिंदु को समझ गए हैं, तो आप आसानी से यह पता लगा सकते हैं कि क्वेरी कैसे जाएगी और लौटाया गया मान 1 होगा। हमारा सेगमेंट ट्री और लेजी ट्री जैसा दिखेगा:
हमने लंबित अद्यतनों के लिए लेजी ट्री की जाँच में अतिरिक्त बाधाओं के साथ आरएमक्यू को खोजने में हमने उसी प्रक्रिया का अनुसरण किया है।
एक और चीज जो हम कर सकते हैं, वह प्रत्येक नोड से मान लौटाने के बजाय, क्योंकि हम जानते हैं कि हमारे वर्तमान नोड का बच्चा नोड क्या होगा, हम केवल इन दोनों का न्यूनतम पता लगाने के लिए उन्हें जांच सकते हैं।
आलसी प्रचार में अद्यतन के लिए छद्म कोड होगा:
Procedure UpdateSegmentTreeLazy(segmentTree, LazyTree, startRange,
endRange, delta, low, high, position):
if low > high //out of bounds
Return
end if
if LazyTree[position] is not equal to 0 //update needed
segmentTree[position] := segmentTree[position] + LazyTree[position]
if low is not equal to high //non-leaf node
LazyTree[2 * position + 1] := LazyTree[2 * position + 1] + delta
LazyTree[2 * position + 2] := LazyTree[2 * position + 2] + delta
end if
LazyTree[position] := 0
end if
if startRange > low or endRange < high //doesn't overlap
Return
end if
if startRange <= low && endRange >= high //total overlap
segmentTree[position] := segmentTree[position] + delta
if low is not equal to high
LazyTree[2 * position + 1] := LazyTree[2 * position + 1] + delta
LazyTree[2 * position + 2] := LazyTree[2 * position + 2] + delta
end if
Return
end if
//if we reach this portion, this means there's a partial overlap
mid := (low + high) / 2
UpdateSegmentTreeLazy(segmentTree, LazyTree, startRange,
endRange, delta, low, mid, 2 * position + 1)
UpdateSegmentTreeLazy(segmentTree, LazyTree, startRange,
endRange, delta, mid + 1, high, 2 * position + 2)
segmentTree[position] := min(segmentTree[2 * position + 1],
segmentTree[2 * position + 2])
और आलसी प्रचार में RMQ के लिए छद्म कोड होगा:
Procedure RangeMinimumQueryLazy(segmentTree, LazyTree, qLow, qHigh, low, high, position):
if low > high
Return infinity
end if
if LazyTree[position] is not equal to 0 //update needed
segmentTree[position] := segmentTree[position] + LazyTree[position]
if low is not equal to high
segmentTree[position] := segmentTree[position] + LazyTree[position]
if low is not equal to high //non-leaf node
LazyTree[2 * position + 1] := LazyTree[2 * position + 1] + LazyTree[position]
LazyTree[2 * position + 2] := LazyTree[2 * position + 2] + LazyTree[position]
end if
LazyTree[position] := 0
end if
if qLow > high and qHigh < low //no overlap
Return infinity
end if
if qLow <= low and qHigh >= high //total overlap
Return segmentTree[position]
end if
//if we reach this portion, this means there's a partial overlap
mid := (low + high) / 2
Return min(RangeMinimumQueryLazy(segmentTree, LazyTree, qLow, qHigh,
low, mid, 2 * position + 1),
RangeMinimumQueryLazy(segmentTree, LazyTree, qLow, qHigh,
mid + 1, high, 2 * position + 1)