Compact structure for prefix sums with O(log n) point updates and queries.
Store partial sums indexed by least-significant-one-bit; add(i, Δ) updates O(log n) nodes and prefixSum(i) aggregates O(log n) nodes.
Use for dynamic prefix sums/frequencies or coordinate-compressed indices; great for inversion counts, order statistics, and 1D offline queries.
Represent partial sums in an array where index i is responsible for the range (i - lsb(i) + 1 .. i). Updating index i adds Δ to i and then jumps by lsb(i); querying prefix(i) accumulates values while subtracting lsb(i). This exploits binary decomposition of indices.
Use this pattern when use for dynamic prefix sums/frequencies or coordinate-compressed indices; great for inversion counts, order statistics, and 1d offline queries.
class Fenwick:
def __init__(self, n): self.n=n; self.bit=[0]*(n+1)
def add(self, i, delta):
i+=1
while i<=self.n: self.bit[i]+=delta; i+=i&-i
def sum(self, i):
i+=1; s=0
while i>0: s+=self.bit[i]; i-=i&-i
return s
def range_sum(self, l, r): return self.sum(r)-self.sum(l-1)Standard BIT for sum/frequency with O(log n) per op.
class Fenwick:
def __init__(self, n): self.n=n; self.bit=[0]*(n+1)
def add(self, i, delta):
i+=1
while i<=self.n: self.bit[i]+=delta; i+=i&-i
def sum(self, i):
i+=1; s=0
while i>0: s+=self.bit[i]; i-=i&-i
return s
def range_sum(self, l, r): return self.sum(r)-self.sum(l-1)Use BIT on differences or two BITs to simulate range updates and queries.
# Fenwick/BIT Range Add + Prefix/Range Sum (two BITs)
class BIT:
def __init__(self,n): self.n=n; self.bit=[0]*(n+1)
def add(self,i,delta):
i+=1
while i<=self.n:
self.bit[i]+=delta; i+= i & -i
def sum(self,i):
i+=1; s=0
while i>0:
s+=self.bit[i]; i-= i & -i
return s
class RangeBIT:
def __init__(self,n): self.n=n; self.b1=BIT(n); self.b2=BIT(n)
def _add(self,bit,i,delta): bit.add(i,delta)
def range_add(self,l,r,delta):
# add delta to [l,r]
self._add(self.b1,l,delta); self._add(self.b1,r+1,-delta)
self._add(self.b2,l,delta*(l)); self._add(self.b2,r+1,-delta*(r+1))
def _prefix(self,x):
# sum[0..x]
return (x+1)*self.b1.sum(x) - self.b2.sum(x)
def range_sum(self,l,r):
return self._prefix(r) - (self._prefix(l-1) if l>0 else 0)Trade-offs: memory and simplicity vs generality and lazy range updates
class Fenwick:
def __init__(self, n): self.n=n; self.bit=[0]*(n+1)
def add(self, i, delta):
i+=1
while i<=self.n: self.bit[i]+=delta; i+=i&-i
def sum(self, i):
i+=1; s=0
while i>0: s+=self.bit[i]; i-=i&-i
return s
def range_sum(self, l, r): return self.sum(r)-self.sum(l-1)