Fenwick (binary indexed) trees

Prefix sums + point updates, both O(log n). A segment tree's job for sums — in one array, two loops.

The tree lives in the indices

• Index i covers i & -i positions ending at i (lowest set bit)
• Those ranges tile the array
• Prefix query: walk DOWN, i -= i & -i
• Update: walk UP, i += i & -i
• ≤ log n bits per index → O(log n)

Watch the index jumps

prefix_sum(6): 6 → 4 → 0 (subtract lowbit). update(3): 3 → 4 → 8 (add lowbit). No tree drawn — there is no tree.

Lean specialist beats the segment tree

46× faster than raw array, 403× than prefix sums — and 4× faster than a segment tree (6ms vs 25ms).

The catch: invertible only

• Range sum = prefix(hi) − prefix(lo−1) → needs subtraction
• Sums, xors, counts — yes. Min / max / gcd — no (use a segment tree)
• 1-indexed (index 0 unused) — the classic bug

Takeaway

Same Big-O, tiny constant → match the tool to the exact problem. Next: B-trees — the balanced tree, reimagined for disk.