Lazy Propagation — அடிப்படை

Lazy Propagation — இடைவெளி கேள்விகள்/புதுப்பிப்புகளுக்கான மரக் கட்டமைப்பு.

உண்மை உலகில் இது ஏன் முக்கியம்?

காலத் தொடர், விளையாட்டு தரவு, நேர்காணல் — வேகமான இடைவெளி கேள்விகள்.

மையக் கருத்து (மாணவர்களுக்கான விளக்கம்)

இடைவெளி [l,r] கேள்வி/புதுப்பிப்பு O(log n); மர உயரம் ≈ log n; 1-அடுக்கு குறியீட்டில் 4n அளவு.

Pythonில் முயற்சி செய்வோம்

class LazyRangeAdd:
    def __init__(self, n: int) -> None:
        self.n = n
        self.size = 1
        while self.size < n:
            self.size *= 2
        self.sum = [0] * (2 * self.size)
        self.lazy = [0] * (2 * self.size)

    def _push(self, i: int, seg_l: int, seg_r: int) -> None:
        if self.lazy[i] == 0:
            return
        mid = (seg_l + seg_r) // 2
        length = mid - seg_l + 1
        self.lazy[2 * i] += self.lazy[i]
        self.lazy[2 * i + 1] += self.lazy[i]
        self.sum[2 * i] += self.lazy[i] * length
        self.sum[2 * i + 1] += self.lazy[i] * (seg_r - mid)
        self.lazy[i] = 0

    def range_add(self, ql: int, qr: int, val: int) -> None:
        self._add(1, 0, self.size - 1, ql, qr, val)

    def _add(self, i: int, l: int, r: int, ql: int, qr: int, val: int) -> None:
        if qr < l or r < ql:
            return
        if ql <= l and r <= qr:
            self.lazy[i] += val
            self.sum[i] += val * (r - l + 1)
            return
        self._push(i, l, r)
        mid = (l + r) // 2
        self._add(2 * i, l, mid, ql, qr, val)
        self._add(2 * i + 1, mid + 1, r, ql, qr, val)
        self.sum[i] = self.sum[2 * i] + self.sum[2 * i + 1]

    def range_sum(self, ql: int, qr: int) -> int:
        return self._query(1, 0, self.size - 1, ql, qr)

    def _query(self, i: int, l: int, r: int, ql: int, qr: int) -> int:
        if qr < l or r < ql:
            return 0
        if ql <= l and r <= qr:
            return self.sum[i]
        self._push(i, l, r)
        mid = (l + r) // 2
        return self._query(2 * i, l, mid, ql, qr) + self._query(2 * i + 1, mid + 1, r, ql, qr)


lz = LazyRangeAdd(6)
lz.range_add(1, 3, 5)
print(lz.range_sum(0, 5))

பொதுவான தவறுகள்

• 0-அடுக்கு/1-அடுக்கு குழப்பம்.
• மர அளவு n மட்டுமல்ல 4n.

முக்கிய பாடங்கள்

• கையெழுது சிறு உதாரணம் வரை.
• புள்ளி புதுப்பிப்பு முதல், பின் வரம்பு.