Search tools and guides ⌘K
II · Trees, with shape

Fenwick tree (BIT)

Prefix sums, with constant tweaks.

1994 · Peter Fenwick · University of Auckland
The story

Fenwick noticed that the binary representation of an index encodes a clean partition of [1..n]. The result: a one-array structure that handles point updates and prefix-sum queries in O(log n) using a single bit-twiddle (i &= -i) at each step. Smaller and faster than a segment tree, simpler to implement.

How it works

A flat array of n + 1 entries. Each slot covers a range determined by the lowest set bit of its index. Update walks "up" by adding the lowest-bit index; prefix-query walks "down" by subtracting it. Twelve lines of code total.

Where it lives

Online analytics, leaderboards, count-of-events-in-window. Anywhere prefix-sum-with-updates is needed. Notably absent from min/max workloads. Those need a segment tree.

The key insight

Only invertible aggregates work (the range-sum identity sum(l..r) = prefix(r) − prefix(l-1) requires subtraction). For sum, count, XOR: Fenwick wins on speed, memory, and code length.

More in Trees, with shape
Binary search tree Sorted, but with shortcuts. AVL tree Always height-balanced, to within one. Red-black tree Almost balanced, much faster to maintain. B-tree / B+ tree The shape of a database index. Heap (binary heap) A priority queue you can grep. Skip list Probabilistic balance, beautifully. Trie (prefix tree) A tree you walk one character at a time. Segment tree Range queries in logarithmic time. Treap BST and heap, secretly the same tree. Splay tree No metadata — and surprising amortised guarantees.
Across the cabinet
IV MinHash Set similarity, in a few hashes. IV t-digest Quantiles, fairly accurate, fully streaming. V Suffix array All suffixes, sorted. V Suffix tree Every substring, in linear space. V Rope A tree of small strings. V Piece table Edit a file without copying it. V Gap buffer A buffer with a hole at the cursor. VI Adjacency list Each node, its neighbours.
← All data structures