Segment trees

Understand the idea

A segment tree stores aggregates for disjoint subranges. Combine child summaries with an associative operation and identity. Unlike prefix subtraction, it can support minimum or other noninvertible aggregates.

Work through an example

The lab's iterative sum tree places values at indices n..2n-1 and sums parents. Query [l,r) collects disjoint covered nodes, avoiding double counting.

Time and space complexity

O(n) build/storage, O(log n) point update/query. Noncommutative operations need separate left/right accumulators.

Why it works

Every selected query node belongs wholly to the requested interval, and selected regions partition that interval.

Common mistakes

• Associativity is required.
• One unordered accumulator only works here because sum is commutative.

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