सेगमेंट ट्री: त्वरित और आसान

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

---

वेबिनार एक अनुभवी प्रोग्रामर और शिक्षक द्वारा संचालित किया गया था, साथ ही पाठ्यक्रम "डेवलपर्स के लिए एल्गोरिदम" एवगेनी वोलोसैटोव के प्रमुख थे ।

कहावत है

खंडों का एक पेड़ एक डेटा संरचना है जो किसी दिए गए खंड पर सरणी के तत्वों के योग का एल्गोरिदमिक सरल और लघुगणक त्वरित खोज की अनुमति देता है।

उदाहरण के लिए, कल्पना करें कि आपको निम्नलिखित संख्याओं का योग खोजने की आवश्यकता है:



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



इसका क्या मतलब है उपवास? इसका मतलब है कि अगर हम केवल संख्याओं को जोड़ दें तो इससे भी तेज । आखिरकार, लाखों और अरबों की संख्या हो सकती है ...

यह लगातार उन तत्वों का योग खोजने की इच्छा थी जो हमारे वेबिनार के लिए प्रेरणा बन गए। इसके अलावा, हम न केवल योग के बारे में बात कर रहे हैं, बल्कि अन्य कार्यों के बारे में भी, उदाहरण के लिए, किसी भी साहचर्य समारोह की गणना। इस प्रकार, हम उन ऑपरेशनों के बारे में बात कर रहे हैं जिनका निष्पादन गणना क्रम पर निर्भर नहीं करता है।

आइए अपनी पंक्ति में लौटते हैं:



जाहिर है, अगर हम जल्दी से परिणाम ढूंढना चाहते हैं, तो हमें अग्रिम में कुछ मात्राओं की गणना करने की आवश्यकता है। पहली बात जो दिमाग में आती है वह है जोड़ियों में तह:



अब, यदि आपको संख्याओं का योग खोजने की आवश्यकता है, तो हम इसे लगभग तुरंत कर सकते हैं। उदाहरण के लिए, ऊपर उल्लिखित खंड का योग खोजने के लिए, यह 13 से 9 को जोड़ने के लिए पर्याप्त होगा। सब कुछ प्राथमिक है: चार संख्याओं का योग खोजने के लिए , हमने केवल दो को जोड़ा।

हम कार्य को जटिल करते हैं:



इस सेगमेंट का योग खोजने के लिए, हमें उन तत्वों को जोड़ना होगा, जो एक या दूसरे तरीके से हमारे सेगमेंट को कवर करते हैं:



बेशक, 3 + 13 + 19 = 35. ध्यान दें कि सात संख्याओं का योग खोजने के लिए, हमने केवल तीन जोड़े। यदि खंड में एक हजार तत्व शामिल हैं, तो यह औसतन 10 तत्वों को जोड़ने के लिए पर्याप्त होगा, क्योंकि हमारे पास आधार -2 लॉगरिदम के साथ एक लघुगणकीय जटिलता है। और यह तेज़ है!

पूर्ण बाइनरी ट्री

एक पूर्ण बाइनरी ट्री एक पेड़ है, जिसके प्रत्येक तत्व में ठीक दो बच्चे हैं।

पूर्ण बाइनरी ट्री के साथ काम करने के लिए, आपको एक सरणी जैसी डेटा संरचना का उपयोग करना चाहिए और करना चाहिए। इस सरणी को क्रमबद्ध करना एक से सुविधाजनक है । हम बाइनरी ट्री के प्रत्येक तत्व को प्राकृतिक संख्या के साथ 1 से 2 ^एन -1 तक रखते हैं:



दृष्टिकोण की पूरी सुंदरता यह है कि बच्चों और माता-पिता की संख्या की गणना करना बहुत आसान है।
"बाएं बच्चे": i * 2 , "सही": i * 2 + 1 की गणना करने का सूत्र।



उदाहरण के लिए, हम पांचवें तत्व में बच्चों की संख्या की गणना करते हैं:

1. 5 x 2 = 10 ;
2. 5 x 2 + 1 = 11 ।

और "बच्चे" से "माता-पिता" तक कैसे बढ़ें? हम पूर्णांक विभाजन i / 2 का उपयोग करते हैं

ठीक है, और कैसे निर्धारित करें कि बच्चा बाएं या दाएं है? इसका उत्तर निम्नलिखित है: बाएं बच्चों के पास भी संख्याएँ हैं, दाएं बच्चों के पास विषम संख्याएँ हैं ।

इन बिंदुओं को याद रखें।

एक द्विआधारी पेड़ के हमारे उदाहरण पर लौटते हुए, हम खुद से पूछते हैं, हम इसे कैसे बना सकते हैं? देखिए, हमारे पास पहले एक संख्या है:



इसके लिए आपको एक बाइनरी ट्री बनाने की आवश्यकता है। बाइनरी ट्री को स्टोर करने के लिए कितनी मेमोरी की आवश्यकता होती है, जिसके तल पर ये तत्व होते हैं?

इस प्रश्न का उत्तर 2n है यदि n दो की शक्ति है।

हम और आगे बढ़ते हैं, क्योंकि हमारे सामने दो और सवाल उठते हैं:

1. पूर्ण द्विआधारी वृक्ष की एक सरणी में स्रोत संख्याओं को रखने के लिए आपको किस तत्व की आवश्यकता है?
2. किस तत्व से और किस दिशा में हम अपने पेड़ को पूर्व-गणना की गई मात्राओं से भरना शुरू करेंगे?

पहले प्रश्न का उत्तर काफी सरल है: हमारे पास 8 तत्व हैं, कुल मिलाकर सरणी में 16 तत्व होंगे, जिसका अर्थ है कि पहले तत्व की संख्या 16 - 8 = 8. होगी और हम तत्व 7 से शुरू होकर बाएं से दाएं और नीचे से ऊपर तक निर्माण शुरू करेंगे। बच्चों में इस तरह से मूल्यों को जोड़ना:



अगला, आपको यह निर्धारित करने की आवश्यकता है कि वांछित खंड का योग कैसे खोजना है। हम अपने पहले उदाहरण पर लौटते हैं, तत्वों की गणना करते हैं और एक खंड को परिभाषित करते हैं, और खंड के पहले तत्व को अक्षर L से जोड़ा जाता है, और अंतिम R:



अब एक और अवधारणा शुरू करना आवश्यक है ताकि कार्यों का एल्गोरिदम स्पष्ट हो। हम मौलिक तत्वों की अवधारणा और उनके संबंधित मूलभूत खंडों के बारे में बात कर रहे हैं। मौलिक तत्व पूरे सरणी से कोई भी तत्व है, और मौलिक खंड इसके अनुरूप है, अर्थात प्रारंभिक सरणी से वे तत्व जो इसके तत्काल बच्चे / पोते हैं। संख्या 4 "5" के साथ मूल तत्व के लिए, मौलिक खंड 8 से 9 तत्व तक होगा: ["2"; "3"]:



संख्या 10 - "7" (हमने इसे एल नामित किया है) के साथ मूल तत्व के लिए, यह अपने मूल सेगमेंट के साथ मेल खाता है। क्या LR से परे जाए बिना इस मूलभूत खंड का विस्तार संभव है? हमारे मामले में, आप कर सकते हैं। बाईं सीमा के लिए नियम यह है: यदि यह एक वामपंथी बच्चा है, तो मौलिक खंड का विस्तार किया जा सकता है, नया मौलिक तत्व वर्तमान का जनक होगा। अर्थात्, हम कार्यक्रम में निम्नलिखित लिख सकते हैं:



अब चलो सही तत्व आर पर आगे बढ़ते हैं। यह एक मौलिक तत्व और एक बाएं बच्चा है, इसलिए हम अब क्षेत्र का विस्तार नहीं कर सकते हैं (हम खंड से परे जाएंगे)। इसलिए, हम इस तत्व को उत्तर में जोड़ सकते हैं:



अगला, आपको बाईं ओर दाईं ओर जाने के लिए बाएं तत्व की आवश्यकता है, और बाईं ओर दाईं ओर। इंडेक्स एल = 10 के साथ बाएं तत्व के लिए, अगला इंडेक्स 5 है, क्योंकि यह अभिभावक के पास जाएगा। लेकिन यह पहले दाईं ओर जाएगा, और फिर ऊपर:



तो, L का मान उच्च स्तर पर चला गया और दाएं से थोड़ा। कैसे घटेगा आर? सूत्र का उपयोग करना (R - 1) / 2।



यहाँ इस तरह के एक एल्गोरिथ्म है। चर L और R के निम्न मानों के लिए, फिर उन्हें निम्न प्रकार से ले जाया जाएगा:



यदि पेड़ में 8 तत्व नहीं हैं, लेकिन एक असुविधाजनक संख्या है, तो 12 कहें, हमें पेड़ को जोड़ना होगा (बाइनरी पेड़ पूरा होना चाहिए) 16।
तत्वों की संख्या की गणना करने का सूत्र (लघुगणक के पूरे भाग को लिया गया है):



अब हम न्यूनतम खोजने के साहचर्य कार्य की गणना करते हैं। यहाँ हमारे पेड़ और कट है:



आपको लगता है कि कितनी बार तत्व 5 हमारे कार्य में शामिल होगा - एक या दो? बेशक, एक, लेकिन यह एल्गोरिथ्म में कैसे जांचा जाता है? वास्तव में, यह तत्व या तो एक बाएं या दाएं बेटा है, जिसका अर्थ है कि कार्रवाई एल या आर के लिए की जाएगी।


+

अब परिवर्तन ऑपरेशन पर विचार करें। मान लीजिए कि कुछ तत्व बदल गए हैं, उदाहरण के लिए, 7 के बजाय, 0 आया। हमारे खंड के पेड़ के काम करने की स्थिति में रहने के लिए, हमें सभी माता-पिता को अपडेट करने की आवश्यकता है, और हमें बहुत ऊपर जाने की आवश्यकता है।

ओलंपियाड समस्या का समाधान

ऐसे कार्यों के लिए आवश्यकताओं में से एक यह है कि सब कुछ जल्दी से काम करना चाहिए। तो, हमारे पास निम्नलिखित शर्त है:



हम इसे सेगमेंट के पेड़ के बारे में ज्ञान का उपयोग करके हल करेंगे। परिणामस्वरूप, हमें निम्नलिखित C # कोड मिलता है:



हम इसे सत्यापन के लिए भेजते हैं, हम देखते हैं कि निर्णय किया गया है और पूर्ण है , जिसका अर्थ है कि हमारा एल्गोरिथ्म काम करता है।



यदि आप अधिक विवरण चाहते हैं, तो संपूर्ण वीडियो देखें । आप हमारे शिक्षक एवगेनी वोलोसातोव द्वारा हैबे पर निम्नलिखित लेखक के लेखों को भी पढ़ सकते हैं:

- लाल-काले पेड़ों को संतुलित करना - तीन मामले ;
- घोड़ा बिटों पर चलता है। शतरंज की बिसात ।