Range-query tradeoffs

Understand the idea

Choose the simplest structure that supports the actual workload. Static range sums use prefixes; batched range additions use differences; online point updates/range sums use Fenwick; broader associative queries or lazy range updates use segment trees.

Work through an example

A million queries on unchanged data need no update tree. Interleaving value changes makes static prefixes costly to maintain. Range minimum needs a noninvertible aggregate structure.

Time and space complexity

Prefixes O(n) build/O(1) query; Fenwick O(log n) updates/queries; segment trees add flexibility at larger constants.

Why it works

The chosen representation supports every required operation with its promised bound.

Common mistakes

• Advanced does not automatically mean faster.
• Include preprocessing, memory, update frequency, and coordinate universe.

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