कोडिंग इंटरव्यू: रेंज ऐड (Range Add) और रेंज सम (Range Sum) के लिए लेज़ी सेगमेंट ट्री (Lazy Segment Tree) कैसे बनाएं?

प्रश्न और दायरा

लंबाई n का एक पूर्णांक ऐरे दिए जाने पर, दो ऑनलाइन ऑपरेशन्स को प्रोसेस करें: क्लोज्ड इंटरवल [l, r] में प्रत्येक मान में delta जोड़ें, और [l, r] का योग लौटाएं। लक्ष्य O(n) निर्माण, प्रति ऑपरेशन O(log n), और O(n) अतिरिक्त स्पेस है। बताएं कि इंटरवल क्लोज्ड हैं, delta नेगेटिव हो सकता है, और जब तक अनुरोध न किया जाए तब तक पर्सिस्टेंस दायरे से बाहर है।

इंटरव्यूअर क्या जांच रहा है

पहले इनवेरिएंट लिखें: tree[p] हमेशा नोड इंटरवल के लिए वास्तविक योग होता है, जबकि lazy[p] एक समान वृद्धि (increment) है जो पहले से ही उस योग में शामिल है लेकिन अभी तक चिल्ड्रेन पर लागू नहीं की गई है। एक मजबूत उत्तर केवल पूरी तरह से कवर किए गए नोड को अपडेट करता है, आंशिक ट्रैवर्सल से पहले पुश करता है, और कवर की गई लंबाई से वृद्धि को गुणा करता है।

कोडिंग से पहले स्पष्टीकरण

1. क्या अपडेट जोड़ना (add), असाइनमेंट, या रेंज न्यूनतम (minimum) है? उनके लेज़ी-टैग कंपोजिशन नियम भिन्न होते हैं।
2. क्या एग्रीगेट एक योग (sum), न्यूनतम (minimum), या अधिकतम (maximum) है? नोड मर्ज और टैग फॉर्मूला बदल जाता है।
3. क्या इंटरवल क्लोज्ड हैं? यह उत्तर क्लोज्ड [l, r] का उपयोग करता है; हाफ-ओपन इंटरवल्स के लिए सुसंगत विभाजन और लंबाइयों की आवश्यकता होती है।
4. मान कितने बड़े हो सकते हैं? tree[p] + delta * length 32-बिट पूर्णांकों को ओवरफ्लो कर सकता है, इसलिए एक व्यापक प्रकार (wider type) चुनें।

अनुशंसित समाधान और व्युत्पत्ति

ऐरे में एक इम्प्लिसिट बाइनरी ट्री स्टोर करें। एक नोड [lo, hi], mid पर [lo, mid] और [mid+1, hi] में विभाजित होता है। पूरी तरह से कवर किए गए अपडेट के लिए, tree[p] में delta * (hi-lo+1) जोड़ें और lazy[p] में delta संचित करें; चाइल्ड मान आवश्यकता पड़ने तक अछूते रह सकते हैं।

class LazySumTree:
    def __init__(self, values):
        self.n = len(values)
        self.tree = [0] * (4 * max(1, self.n))
        self.lazy = [0] * len(self.tree)
        if self.n:
            self._build(1, 0, self.n - 1, values)

    def _apply(self, p, lo, hi, delta):
        self.tree[p] += delta * (hi - lo + 1)
        self.lazy[p] += delta

    def _push(self, p, lo, hi):
        if self.lazy[p] == 0 or lo == hi:
            return
        mid = (lo + hi) // 2
        d = self.lazy[p]
        self._apply(p * 2, lo, mid, d)
        self._apply(p * 2 + 1, mid + 1, hi, d)
        self.lazy[p] = 0

समान इनवेरिएंट के साथ पुनरावर्ती (recursively) रूप से add और sum को पूरा करें: पूर्ण कवरेज पर _apply को कॉल करें; आंशिक कवरेज से पहले _push को कॉल करें; लौटने के बाद अपने चिल्ड्रेन से पैरेंट की पुनर्गणना करें। प्रत्येक स्तर केवल स्थिर संख्या में बाउंड्री नोड्स पर जाता है, इसलिए अपडेट और क्वेरी O(log n) हैं और स्टोरेज O(n) है।

विकल्प और ट्रेड-ऑफ़

पॉइंट अपडेट्स और प्रीफिक्स सम्स के लिए, एक Fenwick tree छोटा होता है और इसमें छोटे स्थिरांक (constants) होते हैं। ऑफलाइन रेंज जोड़ के बाद एक अंतिम रीड के लिए, एक डिफ़रेंस ऐरे सरल है। एक लेज़ी सेगमेंट ट्री अपनी जटिलता को तब सार्थक बनाता है जब ऑनलाइन रेंज अपडेट और रेंज एग्रीगेट्स सह-अस्तित्व में हों। रेंज असाइनमेंट के लिए एक अतिरिक्त "has assignment" टैग और एक स्पष्ट प्राथमिकता नियम की आवश्यकता होती है: असाइनमेंट पुराने असाइनमेंट और ऐड टैग को प्रतिस्थापित करता है, जबकि बाद का ऐड इसके बाद संचित होता है।

विफलता मोड, सीमाएं और प्रति-उदाहरण

• इंटरवल की लंबाई को भूल जाने से [2, 5] में 3 जोड़ने पर योग 12 के बजाय केवल 3 बढ़ता है।
• पूर्ण कवरेज के बाद रिकर्स करने से लेज़ी प्रोपेगेशन खो जाता है और अपडेट बार-बार लागू हो सकता है।
• पुश के बाद टैग को साफ़ करने में विफल होने पर अगली विजिट पर वही वृद्धि फिर से लागू हो जाती है।
• आंशिक अपडेट के बाद पैरेंट की पुनर्गणना न करने से बाद की पूर्ण-कवर क्वेरी पुरानी (stale) रह जाती हैं।
• क्लोज्ड और हाफ-ओपन इंटरवल्स को मिलाने से एक-एलिमेंट या mid+1 त्रुटियां होती हैं; सीमा पर एक खाली ऐरे, l > r, और n=0 को मान्य करें।

टेस्ट और सत्यापन चेकलिस्ट

एक ऑरेकल के रूप में एक बुनियादी ऐरे का उपयोग करें, यादृच्छिक (random) अपडेट और क्वेरी उत्पन्न करें, और प्रत्येक ऑपरेशन के बाद तुलना करें। एक-तत्व रेंज, पूर्ण रेंज, दोनों सीमाएं, नकारात्मक डेल्टा, बार-बार ओवरलैप, और सभी-समान मान शामिल करें। जांचें कि पुनरावर्ती कॉल के बाद पैरेंट अपने चिल्ड्रेन के योग के बराबर है, और जांचें कि चुना गया पूर्णांक प्रकार बड़े इनपुट पर ओवरफ्लो नहीं होता है। यदि इटरेटिव लेआउट लागू कर रहे हैं तो एक समतुल्यता परीक्षण (equivalence test) जोड़ें।

फॉलो-अप प्रश्न

रेंज असाइनमेंट और रेंज ऐड एक साथ कैसे काम कर सकते हैं?

प्रति नोड एक वैकल्पिक असाइनमेंट टैग और एक ऐड टैग रखें। एक नया असाइनमेंट पुराने असाइनमेंट और ऐड दोनों को बदल देता है; एक नया ऐड असाइनमेंट के बाद संचित होता है। असाइनमेंट को पहले और ऐड को बाद में पुश करें। यह क्रम ही शुद्धता का नियम है।

आप रेंज न्यूनतम (minimum) का समर्थन कैसे करते हैं?

योग के बजाय इंटरवल न्यूनतम स्टोर करें; एक रेंज ऐड अभी भी उस न्यूनतम में delta जोड़ता है, इसलिए लेज़ी टैग सरल रहता है। रेंज chmin या chmax के लिए segment-tree beats जैसे अधिक समृद्ध इनवेरिएंट्स की आवश्यकता होती है।

आप ऐतिहासिक संस्करणों (historical versions) को कैसे प्रस्तुत करते हैं?

एक पर्सिस्टेंट सेगमेंट ट्री का उपयोग करें: अपडेट पाथ के साथ नोड्स को कॉपी करें और अछूते सब-ट्री को साझा करें। प्रत्येक अपडेट लगभग O(log n) नोड्स को कॉपी करता है, और एक रूट पॉइंटर एक संस्करण की पहचान करता है, इसलिए स्पेस अपडेट की संख्या के साथ बढ़ता है।