Chapter 8 · Data Structures on Trees
Fenwick Tree (Binary Indexed Tree)
Prefix sums in one loop, with the two-line tricks for range updates and "find smallest index with prefix ≥ x".
t[i] stores the sum over the half-open range (i - lowbit(i), i], where lowbit(i) = i & -i. That single choice of ranges makes both update and query a "walk the set bits" loop.
struct BIT {
int n; vector<ll> t;
BIT(int n) : n(n), t(n + 1) {}
void add(int i, ll v) { for (; i <= n; i += i & -i) t[i] += v; }
ll sum(int i) { ll s = 0; for (; i > 0; i -= i & -i) s += t[i]; return s; }
ll range(int l, int r) { return sum(r) - sum(l - 1); } // 1-indexed, inclusive
};Why it beats a segment tree when it applies
- ~half the memory and ~3× better constants (one array, no recursion),
kthsearch in O(log n) with a bit-lifting loop (below) — segment trees need the same trick, so no loss,- it supports any invertible monoid (sum, xor, count). Not min/max-with-decrease: there is no inverse, which is the whole "when do I need a segment tree instead" answer.
// smallest i with sum(i) >= target, assuming all values >= 0
int kth(ll target) {
int idx = 0;
for (int pw = 1 << __lg(n); pw; pw >>= 1)
if (idx + pw <= n && t[idx + pw] < target) { target -= t[idx + pw]; idx += pw; }
return idx + 1;
}#Range add + range sum: two trees
// add x on [l, r]: B1: +x at l, -x at r+1 ; B2: +x*(l-1) at l, -x*r at r+1
// prefix(p) = p * B1.sum(p) - B2.sum(p)
void range_add(int l, int r, ll x) { b1.add(l, x); b1.add(r + 1, -x); b2.add(l, x * (l - 1)); b2.add(r + 1, -x * r); }
ll prefix(int p) { return p * b1.sum(p) - b2.sum(p); }
ll range_sum(int l, int r) { return prefix(r) - prefix(l - 1); }The formula comes from writing ∑i ≤ p ai after the difference-array substitution and collecting terms: ∑i ≤ p prei = ∑j ≤ i xj ⇒ (p - j + 1) xj, so you need ∑ xj and ∑ j · xj — two Fenwicks, one for each. (Same algebra as lazy segment tree, but with zero lines of push code.)
// count pairs i < j with a[i] > a[j], values compressed to [1, n]
BIT bit(n);
ll inv = 0;
for (int i = n - 1; i >= 0; i--) {
inv += bit.sum(a[i] - 1); // elements to the right that are smaller
bit.add(a[i], 1);
}Read it as a sweep: bit holds the suffix multiset, and sum(k) answers "how many seen values are ≤ k". Coordinate compression (sort + unique + lower_bound) is the standard preprocessing when values reach 109.
The four offline patterns
- count pairs with condition on both coordinates: sort by one, BIT over the other (inversions, "smaller elements to the left", dominance counting),
- k-th smallest in a static range: BIT over value-sorted positions + binary search, or a persistent segment tree for queries online,
- "number of distinct values in [l,r]": sort queries by right end, keep 1 only at the last occurrence of each value, answer with a range sum — a two-line reduction,
- subtree queries on a tree (Entry/Exit Times and the Euler Tour): the flat array is a Fenwick's job description.
2D point update / rectangle sum is a BIT over x whose nodes hold a BIT over y — O(log2 n) per operation with O(n log n) memory (offline: collect each node's y-values first). It is genuinely useful for n ≤ 2 × 105, but if the second dimension is also dynamic, a segment tree of treaps or plain divide-and-conquer is usually the shorter path.