Fenwick & Segment Trees

We have an array $A[1\dots n]$ and two operations we want to interleave freely: update a single entry, and ask for the sum of a contiguous range $A[l\dots r]$. The two obvious data structures each ace one operation and fail the other. Keep $A$ as is and an update is a single write in $O(1)$, but a range sum scans the range in $\Theta (n)$. Precompute a prefix-sum array $P[i]=A[1]+\cdots +A[i]$ and a range sum collapses to $P[r]-P[l-1]$ in $O(1)$, but now a single update to $A[k]$ disturbs every $P[i]$ with $i\ge k$, an $\Theta (n)$ repair. We want a structure that splits the difference and does both in $O(\log n)$.

The idea, in the spirit of the previous lessons on augmenting trees with subtree summaries,¹ is to store partial sums over blocks so that any prefix is the sum of a few blocks and any single element lives in only a few blocks. Two classic structures realize this: the Fenwick tree, which is remarkably compact and exploits the binary representation of the index, and the segment tree, which is more general and handles any associative aggregate plus range updates.

Fenwick trees: indexing by the low bit

A Fenwick tree (or binary indexed tree) is a 1-indexed array $F[1\dots n]$ where $F[i]$ stores the sum of a contiguous block of $A$ ending at index $i$. The length of that block is $\mathrm{lowbit}(i)$, the value of the lowest set bit of $i$:

That is, $F[i]$ covers the half-open range $(i-\mathrm{lowbit}(i),i]$. The trick rides on two's-complement arithmetic: $-i$ flips every bit of $i$ and adds one, so $i\&(-i)$ isolates exactly the lowest set bit. If $i=6=(110{)}_2$ then $\mathrm{lowbit}(6)=2$, so $F[6]$ covers indices $5\dots 6$; if $i=8=(1000{)}_2$ then $\mathrm{lowbit}(8)=8$, so $F[8]$ covers the whole prefix $1\dots 8$.

Prefix sum. To compute $P[i]=A[1]+\cdots +A[i]$ we peel off blocks from the right. $F[i]$ accounts for the topmost block ending at $i$; the rest of the prefix ends at $i-\mathrm{lowbit}(i)$, so we jump there and repeat, clearing one set bit each step until we reach $0$.

Point update. When $A[k]$ changes by $\delta$, every $F[i]$ whose block contains $k$ must change by $\delta$. Those are exactly the indices reached by repeatedly adding the low bit: starting at $k$, each step $i\leftarrow i+\mathrm{lowbit}(i)$ moves to the next larger block that covers $k$, until we run past $n$.

The two walks are mirror images on the same number line. $\text{Update}$ climbs to larger indices by adding the low bit, visiting every block that owns the changed element; $\text{PrefixSum}$ descends to smaller indices by subtracting it, peeling off the blocks that tile the prefix. The same $\mathrm{lowbit}$ hop drives both, in opposite directions.

A range sum is then two prefix queries:

so both update and range sum cost $O(\log n)$, with $F$ occupying a single array of $n$ words and no pointers.² Building $F$ takes $O(n)$ by a linear in-place pass (add each $F[i]$ into its parent $F[i+\mathrm{lowbit}(i)]$) rather than $n$ separate updates.

The one catch: this works because sums are invertible — we recover $A[l\dots r]$ by subtracting two prefixes. For non-invertible aggregates like $\min$ or $\max$, $P[r]-P[l-1]$ is meaningless, and we need a structure that queries an arbitrary range directly. That is the segment tree.

Segment trees: a balanced tree of canonical ranges

A segment tree over $A[0\dots n-1]$ is a balanced binary tree whose leaves are the array entries and whose every internal node stores the aggregate of the contiguous range its subtree spans. The root covers $[0,n-1]$; a node covering $[lo,hi]$ with $lo<hi$ splits at $mid=\lfloor (lo+hi)/2\rfloor$ into children covering $[lo,mid]$ and $[mid+1,hi]$. The stored aggregate can be sum, $\min$, $\max$, or $\gcd$: any associative operation (formally, any monoid), since a node's value is its two children's values combined.

Query. To aggregate $A[l\dots r]$ we descend from the root. At a node covering $[lo,hi]$: if $[lo,hi]$ lies entirely inside $[l,r]$ we return its stored value without recursing (a canonical node); if it is disjoint from $[l,r]$ we return the monoid identity; otherwise we recurse into both children and combine. The query range $[l,r]$ decomposes into $O(\log n)$ canonical nodes, at most two per level of the tree, so a range query costs $O(\log n)$. In the figure, $[1,5]$ is covered by the four shaded nodes $[1,1]$, $[2,3]$, $[4,5]$, and their union is exactly $\{1,2,3,4,5\}$.

Point update. To change $A[k]$, update the corresponding leaf and walk back up to the root, recomputing each ancestor as the combination of its (now-updated) children — one node per level, $O(\log n)$ work. Building the tree bottom-up visits each of the $\Theta (n)$ nodes once, so construction is $O(n)$, and the tree needs at most $2n$ (commonly allocated as $4n$) nodes, roughly $2$ to $4\times$ a Fenwick tree's memory.

Lazy propagation: range updates in $O(\log n)$

A point-update segment tree still pays $\Theta (n\log n)$ to add a value to a whole range element by element. Lazy propagation fixes this. When an update applies to a range that exactly covers a node's interval, we apply it to that node's aggregate and stash a pending tag on the node instead of recursing into its children. The tag is pushed down to the children only later, lazily, when a subsequent query or update actually needs to enter that subtree.

With lazy tags both range update and range query run in $O(\log n)$. This is the segment tree's decisive advantage over the Fenwick tree: it supports non-invertible aggregates ($\min$, $\max$) and whole-range modifications, at the cost of more memory and a more involved implementation.³

Choosing between them

Both give $O(\log n)$ point-update and $O(\log n)$ range-query; the choice is about generality versus footprint.

• Fenwick tree. Pick it when the aggregate is an invertible group operation (sum, xor) and you only need point updates. It is a single array, cache-friendly, a dozen lines of code, and the constant factors are tiny. Range sum is $\text{prefix}(r)-\text{prefix}(l-1)$.
• Segment tree. Pick it when you need $\min /\max /\gcd$ or any non-invertible aggregate, or range updates via lazy propagation. It is strictly more general, and you pay for it with $\sim 2$ to $4\times$ the memory and a more involved implementation.⁴

A useful slogan: Fenwick is the specialist, the segment tree is the generalist. When you reach for range-sum-query-mutable, a Fenwick tree is the crisp answer; when the skyline or a range-assign problem demands $\max$ over a mutable range, the segment tree with lazy propagation is the tool.

Takeaways

• A static prefix-sum array answers range sums in $O(1)$ but updates in $O(n)$; a plain array updates in $O(1)$ but sums in $O(n)$. Fenwick and segment trees achieve both in $O(\log n)$.
• A Fenwick tree is a 1-indexed array where $F[i]$ holds the sum of the block $(i-\mathrm{lowbit}(i),i]$, with $\mathrm{lowbit}(i)=i\&(-i)$. Prefix sum walks down clearing low bits; update walks up adding low bits, each $O(\log n)$.
• Fenwick range sum relies on invertibility: $\text{prefix}(r)-\text{prefix}(l-1)$. It fails for $\min /\max$.
• A segment tree stores each node's range aggregate (any associative op). Build $O(n)$, point update $O(\log n)$, and range query $O(\log n)$ by decomposing $[l,r]$ into $O(\log n)$ canonical nodes.
• Lazy propagation defers a range update by tagging canonical nodes and pushing tags down only when needed, giving $O(\log n)$ range update + range query.
• Fenwick = tiny, fast, sum-like invertible aggregates; segment tree = general $\min /\max$ and lazy range ops, at $\sim 2$ to $4\times$ the memory.