इस अनुभाग में हम देखेंगे कि सेगमेंट ट्री (Segment Tree) क्या है। उस पर चर्चा करने से पहले, आइए एक समस्या देखें।
मान लीजिए हमारे पास एक सरणी arr[0,…,n-1] है। हम निम्न संक्रियाएँ कर सकते हैं:
इंडेक्स l से r तक के तत्वों का योग ढूंढें, जहां 0 ≤ l ≤ r ≤ n-1
सरणी के एक निर्दिष्ट तत्व के मान को नए मान x में बदलें। हमें arr[i] = x करना होगा। i रेंज 0 से n-1 में है।
हम इस समस्या को सेगमेंट ट्री का उपयोग करके हल कर सकते हैं। सेगमेंट ट्री हमें योग और क्वेरी प्राप्त करने में O(log n) समय में मदद कर सकता है। आइए देखें कि इसे कैसे प्रस्तुत किया जाए:
पत्ती नोड्स दी गई सरणी के तत्व हैं
प्रत्येक आंतरिक नोड पत्ती नोड्स के कुछ विलय (merging) को दर्शाते हैं। विलय विभिन्न मामलों में अलग हो सकता है। यहाँ विलय एक नोड के तहत पत्तियों का योग है।
मान लीजिए हमारे पास [1, 3, 5, 7, 9, 11] जैसी सरणी है। तो सेगमेंट ट्री होगा:
