Lazy propagation

Understand the idea

Lazy propagation delays a range update while keeping the node aggregate immediately correct. A pending range-add tag composes by addition; push it to children before partial traversal. Range assignment would need different tag composition.

Work through an example

Adding 3 to [1,4) in five zeros gives [0,3,3,3,0]. Then adding -1 to [2,5) gives [0,3,2,2,-1], total 6.

Time and space complexity

O(log n) range-add/range-sum operations, O(n) storage for this model.

Why it works

tree[node] includes its pending tag's effect; children may lag until push, after which tag is cleared.

Common mistakes

• Sum updates multiply delta by segment length.
• Assignment and addition tags cannot be composed as simple addition.

Chapter lab · Python implementation

Range structures trade preprocessing and memory for repeated queries and updates. The lab implements a Fenwick sum tree, an iterative segment sum tree, and a lazy range-add/range-sum tree. Their external ranges are half-open. Coordinate compression preserves order for sparse coordinates but does not preserve physical distances.

This shared lab connects the chapter's topics. Follow the current lesson's worked example first, then trace the complete implementation. Additional algorithms described in topic exercises are variations you can implement independently.

class Fenwick:
    def __init__(self,n):
        if n<0: raise ValueError('nonnegative size required')
        self.n=n; self.tree=[0]*(n+1)
    def add(self,index,delta):
        if not 0<=index<self.n: raise IndexError(index)
        i=index+1
        while i<=self.n:
            self.tree[i]+=delta; i+=i&-i
    def prefix(self,end):
        if not 0<=end<=self.n: raise IndexError(end)
        result=0; i=end
        while i:
            result+=self.tree[i]; i-=i&-i
        return result
    def query(self,left,right):
        if not 0<=left<=right<=self.n: raise IndexError('range')
        return self.prefix(right)-self.prefix(left)

class Segment:
    def __init__(self,values):
        self.n=len(values); self.tree=[0]*self.n+list(values)
        for i in range(self.n-1,0,-1):
            self.tree[i]=self.tree[2*i]+self.tree[2*i+1]
    def set(self,i,value):
        if not 0<=i<self.n: raise IndexError(i)
        i+=self.n; self.tree[i]=value
        while i>1:
            i//=2; self.tree[i]=self.tree[2*i]+self.tree[2*i+1]
    def query(self,left,right):
        if not 0<=left<=right<=self.n: raise IndexError('range')
        left+=self.n; right+=self.n; answer=0
        while left<right:
            if left&1: answer+=self.tree[left]; left+=1
            if right&1: right-=1; answer+=self.tree[right]
            left//=2; right//=2
        return answer

class LazySum:
    def __init__(self,n):
        if n<1: raise ValueError('positive n required')
        self.n=n; self.tree=[0]*(4*n); self.lazy=[0]*(4*n)
    def apply(self,node,lo,hi,delta):
        self.tree[node]+=delta*(hi-lo); self.lazy[node]+=delta
    def push(self,node,lo,hi):
        if self.lazy[node] and hi-lo>1:
            mid=(lo+hi)//2
            self.apply(2*node,lo,mid,self.lazy[node])
            self.apply(2*node+1,mid,hi,self.lazy[node])
            self.lazy[node]=0
    def update(self,left,right,delta):
        if not 0<=left<=right<=self.n: raise IndexError('range')
        def visit(node,lo,hi):
            if right<=lo or hi<=left: return
            if left<=lo and hi<=right:
                self.apply(node,lo,hi,delta); return
            self.push(node,lo,hi); mid=(lo+hi)//2
            visit(2*node,lo,mid); visit(2*node+1,mid,hi)
            self.tree[node]=self.tree[2*node]+self.tree[2*node+1]
        visit(1,0,self.n)
    def query(self,left,right):
        if not 0<=left<=right<=self.n: raise IndexError('range')
        def visit(node,lo,hi):
            if right<=lo or hi<=left: return 0
            if left<=lo and hi<=right: return self.tree[node]
            self.push(node,lo,hi); mid=(lo+hi)//2
            return visit(2*node,lo,mid)+visit(2*node+1,mid,hi)
        return visit(1,0,self.n)

Run and test the lab

Copy the implementation and these assertions into a Python 3 file and run it. An assertion failure means the actual result differs from the expectation. Add the current topic's exercise and boundary tests to deepen your understanding.

f=Fenwick(4)
for i,x in enumerate([2,1,3,4]): f.add(i,x)
assert f.query(1,4)==8
f.add(2,5); assert f.query(0,4)==15
s=Segment([2,1,3,4]); assert s.query(1,4)==8
s.set(2,8); assert s.query(0,4)==15
l=LazySum(5); l.update(1,4,3); l.update(2,5,-1)
assert l.query(0,5)==6 and l.query(2,4)==4
assert l.query(0,0)==0