Tree over array ranges for fast range queries and updates (sum/min/max).
Build a complete binary tree over index intervals; each node stores an aggregate (e.g., sum). Point updates and range queries run in O(log n). With lazy propagation, support range updates/queries.
Use when you need many range queries and updates (sum/min/max) on an array, or when Fenwick/BIT is too limited (non-commutative ops, range updates & queries together).
Recursively split the array into halves to form a tree. Each node covers [l,r] and stores a combined value from its children via an associative operator (sum/min/max). For a query, descend into only the nodes intersecting the query range; for an update, update the leaf and recompute along the path. Use lazy propagation to defer range updates by storing pending tags that are pushed to children only when needed.
Use this pattern when use when you need many range queries and updates (sum/min/max) on an array, or when fenwick/bit is too limited (non-commutative ops, range updates & queries together).
class SegTree:
def __init__(self, arr):
n=len(arr); self.n=1
while self.n<n: self.n<<=1
self.t=[0]*(2*self.n)
for i,v in enumerate(arr): self.t[self.n+i]=v
for i in range(self.n-1,0,-1): self.t[i]=self.t[i<<1]+self.t[i<<1|1]
def update(self, idx, val):
i=self.n+idx; self.t[i]=val
i>>=1
while i: self.t[i]=self.t[i<<1]+self.t[i<<1|1]; i>>=1
def query(self, l, r):
l+=self.n; r+=self.n+1; res=0
while l<r:
if l&1: res+=self.t[l]; l+=1
if r&1: r-=1; res+=self.t[r]
l>>=1; r>>=1
return resClassic segment tree supporting single-index updates and sum/min/max over ranges.
class SegTree:
def __init__(self, arr):
n=len(arr); self.n=1
while self.n<n: self.n<<=1
self.t=[0]*(2*self.n)
for i,v in enumerate(arr): self.t[self.n+i]=v
for i in range(self.n-1,0,-1): self.t[i]=self.t[i<<1]+self.t[i<<1|1]
def update(self, idx, val):
i=self.n+idx; self.t[i]=val
i>>=1
while i: self.t[i]=self.t[i<<1]+self.t[i<<1|1]; i>>=1
def query(self, l, r):
l+=self.n; r+=self.n+1; res=0
while l<r:
if l&1: res+=self.t[l]; l+=1
if r&1: r-=1; res+=self.t[r]
l>>=1; r>>=1
return resPropagate deferred updates to children only when needed to support range updates efficiently.
# Segment Tree with Lazy Propagation (Range Add, Range Sum)
class SegTree:
def __init__(self, arr):
n = len(arr)
self.n = n
self.seg = [0]*(4*n)
self.lazy = [0]*(4*n)
def build(i,l,r):
if l==r: self.seg[i]=arr[l]; return
m=(l+r)//2
build(i*2,l,m); build(i*2+1,m+1,r)
self.seg[i]=self.seg[i*2]+self.seg[i*2+1]
build(1,0,n-1)
def _push(self,i,l,r):
if self.lazy[i]!=0:
self.seg[i]+= (r-l+1)*self.lazy[i]
if l!=r:
self.lazy[i*2]+=self.lazy[i]
self.lazy[i*2+1]+=self.lazy[i]
self.lazy[i]=0
def _add(self,i,l,r,ql,qr,val):
self._push(i,l,r)
if qr<l or r<ql: return
if ql<=l and r<=qr:
self.lazy[i]+=val; self._push(i,l,r); return
m=(l+r)//2
self._add(i*2,l,m,ql,qr,val); self._add(i*2+1,m+1,r,ql,qr,val)
self.seg[i]=self.seg[i*2]+self.seg[i*2+1]
def add(self,l,r,val): self._add(1,0,self.n-1,l,r,val)
def _sum(self,i,l,r,ql,qr):
self._push(i,l,r)
if qr<l or r<ql: return 0
if ql<=l and r<=qr: return self.seg[i]
m=(l+r)//2
return self._sum(i*2,l,m,ql,qr)+self._sum(i*2+1,m+1,r,ql,qr)
def sum(self,l,r): return self._sum(1,0,self.n-1,l,r)Swap the aggregator from sum to min/max; structure and complexity remain the same
class SegTree:
def __init__(self, arr):
n=len(arr); self.n=1
while self.n<n: self.n<<=1
self.t=[0]*(2*self.n)
for i,v in enumerate(arr): self.t[self.n+i]=v
for i in range(self.n-1,0,-1): self.t[i]=self.t[i<<1]+self.t[i<<1|1]
def update(self, idx, val):
i=self.n+idx; self.t[i]=val
i>>=1
while i: self.t[i]=self.t[i<<1]+self.t[i<<1|1]; i>>=1
def query(self, l, r):
l+=self.n; r+=self.n+1; res=0
while l<r:
if l&1: res+=self.t[l]; l+=1
if r&1: r-=1; res+=self.t[r]
l>>=1; r>>=1
return resTree height is log n; updates/queries visit O(log n) nodes.
Segment tree typically uses ~4n nodes.