Fenwick Trees and Segment Trees

Why static prefixes stop working

A prefix array answers a range sum in O(1), but one changed value can invalidate every later prefix. Fenwick and segment trees trade slightly slower O(log n) queries for O(log n) updates.

Fenwick tree

A Fenwick cell at one-based index i stores a block whose length is i & -i. An update moves upward with i += i & -i; a prefix query moves toward zero with i -= i & -i.

Fenwick trees are compact and excellent for sums, counts and XOR. They need an operation whose prefix results can be combined or inverted to form a range.

Segment tree

A segment tree stores a summary for every interval. Leaves hold elements; each parent combines two children. It supports sums, minimums, maximums, GCD and richer nodes such as maximum-subarray information.

Lazy propagation delays a range update by recording a tag on a covered node. Push the tag to children only before descending. This supports range updates and range queries in O(log n).

Fenwick example

a=[1,2,3,4]; tree=[0]*5
for j,x in enumerate(a,1):
    i=j
    while i<5: tree[i]+=x; i+=i&-i
s=0;i=3
while i: s+=tree[i];i-=i&-i
print(s)

6

Choosing between them

Use a prefix array for immutable data, Fenwick for compact point-update/prefix-query problems, a segment tree for arbitrary associative range summaries, and a sparse table for immutable idempotent queries such as minimum.

Practice Dynamic Range Sums with a Fenwick Tree, Range Minimum with a Segment Tree, and Lowest Common Ancestor Queries.