Fenwick Tree / Binary Indexed Tree (C)
Topics: data structures, prefix sums, bit manipulation
Problem
Implement a Fenwick tree (binary indexed tree) over caller-provided storage (no
allocation): update a single position and query any prefix sum, each in O(log n).
typedef struct { long *tree; int n; } Fenwick;
void fen_init(Fenwick *f, long *storage, int n); // storage holds n+1 longs
void fen_add(Fenwick *f, int i, long delta); // 1-based point update
long fen_sum(const Fenwick *f, int i); // prefix sum of 1..i
long fen_range(const Fenwick *f, int lo, int hi); // sum of lo..hi
Indices are 1-based, and storage must hold n+1 longs (index 0 is unused).
Key concepts
- The lowest set bit is the whole trick.
i & -i isolates the lowest set bit
of i. Index i in the tree is responsible for the range of that length ending
at i. So the tree partitions 1..i into O(log n) such ranges, one per set bit.
- Update walks up by adding the bit. To add at
i, update i, then
i += i & -i, repeating until you pass n. Each step jumps to the next range
that includes i.
- Query walks down by stripping the bit. To sum
1..i, accumulate tree[i],
then i -= i & -i, repeating until i hits 0. Each step removes the range you
just counted.
- Range sums by subtraction:
sum(lo..hi) = prefix(hi) - prefix(lo-1).
A whole array of prefix-sum bookkeeping, expressed in two-line loops driven by one
bit operation.
Run
cc -std=c11 -O2 -Wall tests.c -o /tmp/fenwick && /tmp/fenwick
Sign in to submit your solution.