Segment Tree (सेगमेंट ट्री)
TODO: सेगमेंट ट्री का और अधिक विस्तृत विवरण
सेगमेंट ट्री (Segment Tree) एक द्विआधारी ट्री-आधारित डेटा संरचना है, जो किसी दिए गए ऐरे या एलिमेंट्स की सूची का प्रतिनिधित्व करती है। ट्री का प्रत्येक नोड, मूल ऐरे के किसी खंड (segment) या सबऐरे का प्रतिनिधित्व करता है।
सेगमेंट ट्री में, रूट नोड पूरे ऐरे को दर्शाता है, जबकि लीफ नोड्स ऐरे के व्यक्तिगत एलिमेंट्स का प्रतिनिधित्व करते हैं। ट्री के आंतरिक नोड्स वे सबऐरे दर्शाते हैं, जो मूल ऐरे को छोटे-छोटे खंडों में विभाजित करके बनाए जाते हैं।
आमतौर पर, यदि कोई नोड सबऐरे [l, r] को दर्शा रहा है, तो उसका बायां बच्चा [l, (l+r)/2] सबऐरे को और दायां बच्चा [(l+r)/2 + 1, r] सबऐरे को दर्शाता है। यह प्रक्रिया तब तक चलती रहती है जब तक कि प्रत्येक लीफ नोड मूल ऐरे के एक ही एलिमेंट से जुड़ा ना हो जाए।
सेगमेंट ट्री के प्रत्येक नोड में संग्रहीत मान (value) निर्भर करता है कि हम किस समस्या या क्वेरी का समाधान कर रहे हैं। अक्सर, सेगमेंट ट्री का उपयोग सबऐरे में योग (sum), न्यूनतम (minimum), अधिकतम (maximum), या अन्य ऑपरेशनों को जल्दी से निकालने के लिए किया जाता है। प्रत्येक नोड का मान उसके चाइल्ड नोड्स के मानों के आधार पर गणना किया जाता है।
सेगमेंट ट्री विशेष रूप से तब उपयोगी होता है जब हमें किसी ऐरे पर रेंज-क्वेरी या अपडेट (जैसे किसी उपखंड का योग जानना या मान बदलना) जैसी समस्याएं हल करनी हों। एक बार सेगमेंट ट्री तैयार हो जाए, तो इन ऑपरेशनों को O(log N) समय जटिलता में पूरा किया जा सकता है, जहाँ N मूल ऐरे का आकार है।
कुल मिलाकर, सेगमेंट ट्री ऐरे पर रेंज आधारित ऑपरेशनों को संभालने के लिए एक शक्तिशाली डेटा संरचना है, जो सबखंडों पर तेज़ी से क्वेरी करने और अपडेट करने की सुविधा देता है। इसका उपयोग विभिन्न एल्गोरिदम और समस्याओं में, जैसे इंटरवल आधारित क्वेरीज़, रेंज अपडेट्स इत्यादि में किया जाता है।
Challenge: Iterative Segment Tree Node Calculation
आपको
n एलिमेंट्स वाला एक ऐरे दिया गया है। आपका कार्य एक सेगमेंट ट्री को क्रमिक (iterative) तरीके से बनाना और प्रत्येक नोड का मान निकालना है। ट्री के हर नोड का मान उस नोड द्वारा दर्शाए गए सबऐरे के योग का प्रतिनिधित्व करता है।इनपुट
इनपुट की पहली पंक्ति में एक पूर्णांक
n (1 ≤ n ≤ 100 000) दिया गया है, जो ऐरे में एलिमेंट्स की संख्या दर्शाता है।दूसरी पंक्ति में
n स्पेस से अलग किए गए पूर्णांक () दिए गए हैं, जो ऐरे के एलिमेंट्स को दर्शाते हैं।आउटपुट
सेगमेंट ट्री के सभी नोड्स के मानों को प्रिंट करें। ट्री के हर लेवल को अलग पंक्ति में स्पेस से अलग करके दिखाएँ।
उदाहरण
इनपुट | आउटपुट |
4
1 2 3 4 | 10
3 7
1 2 3 4 |
8
3 7 9 6 2 1 5 4 | 37
25 12
10 15 3 9
3 7 9 6 2 1 5 4 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 10 MB