इस खंड में हम देखेंगे कि खंड वृक्ष क्या है। उस पर चर्चा करने से पहले, आइए एक समस्या देखें।
मान लीजिए कि हमारे पास एक सरणी है [0,…,n-1], हम निम्नलिखित ऑपरेशन कर सकते हैं -
-
सूचकांक l से r तक के तत्वों का योग ज्ञात कीजिए, जहाँ 0 ≤ l ≤ r ≤ n-1
-
सरणी के निर्दिष्ट तत्व के मान को नए मान x में बदलें। हमें गिरफ्तारी [i] =x करने की ज़रूरत है। मैं 0 से n - 1. की सीमा में हूं।
हम सेगमेंट ट्री का उपयोग करके इस समस्या को हल कर सकते हैं। सेगमेंट ट्री हमें ओ (लॉग एन) समय में योग और क्वेरी प्राप्त करने में मदद कर सकता है। तो आइए देखें कि इसका प्रतिनिधित्व कैसे किया जाता है -
-
लीफ नोड्स दिए गए सरणी के तत्व हैं
-
प्रत्येक आंतरिक नोड पत्ती नोड्स के कुछ विलय का प्रतिनिधित्व कर रहे हैं। अलग-अलग मामलों में विलय अलग-अलग हो सकता है। यहाँ विलय एक नोड के नीचे पत्तियों का योग है।
मान लीजिए कि हमारे पास [1, 3, 5, 7, 9, 11] जैसी एक सरणी है। तो सेगमेंट ट्री होगा
