Ordered structures and balanced-tree concepts

Understand the idea

Ordered structures support predecessor, successor, insertion, deletion, and ranges. Balanced search trees guarantee logarithmic height; subtree counts add rank/select. Sorted arrays have fast search but linear insertion shifts.

Work through an example

Coordinate-compressed Fenwick counts can answer ranks when all possible coordinates are known in advance. Truly online unseen keys need a different ordered structure or rebuilding.

Time and space complexity

Balanced ordered operations O(log n); sorted-list insertion O(n); offline compression O(n log n).

Why it works

Every operation preserves key ordering and any augmented subtree/block summaries.

Common mistakes

• Python bisect is not a balanced tree.
• Compression ranks preserve order but not coordinate gaps.

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