Fenwick Tree

Binary Indexed Tree for logarithmic updates and prefix queries

Balance updates with queries

A plain array updates quickly but needs a linear prefix scan. A prefix-sum array answers quickly but needs a linear rebuild after an update. A Fenwick Tree makes both operations O(log n) by storing carefully chosen partial sums.

Lowbit defines every covered range

lowbit(i) = i & -i isolates the least significant set bit. Entry tree[i] stores a range of that length ending at i. A prefix query jumps backward with i -= lowbit(i); a point update jumps forward with i += lowbit(i) to notify every range that contains the changed position.

Each bar is tree[1..8]. Prefix queries jump backward with i -= lowbit(i), while point updates jump forward with i += lowbit(i).

When to use it

Fenwick Trees are excellent for cumulative frequencies, inversion counting, dynamic ranks, and range sums via query(r) - query(l-1). A segment tree supports more general range operations, but a Fenwick Tree is smaller and often much simpler.

The visualization queries the prefix ending at 6, adds 2 at position 3, then repeats the same query. Compare the two identical lowbit chains to see exactly where the update becomes visible.