Fenwick trees

Understand the idea

A Fenwick tree stores prefix aggregates in overlapping power-of-two blocks. Internal indices are one-based: tree[i] covers the last lowbit(i)=i&-i entries ending at i. Updates climb; prefix queries descend.

Work through an example

For [2,1,3,4], tree slots 1..4 are [2,3,3,10]. prefix(3) reads slot 3 then 2, totaling 6. External index 2 becomes internal 3.

Time and space complexity

O(log n) add/prefix/range query, O(n) storage; lab initialization by repeated add O(n log n).

Why it works

Each slot equals the sum of its covered block after every point delta update.

Common mistakes

• Internal zero cannot advance with lowbit(0).
• To assign a value, add its difference from the previous value.

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