↩ back to Array-Backed Trees

Fenwick Tree (Binary Indexed Tree)

Say you're tracking a running array of values and need two operations to both stay fast: change one value, and ask for the sum of everything up to some index. A plain array makes updates instant (O(1)) but every prefix-sum query means walking from the start (O(n)). Precompute a running-total array instead — the exact trick counting sort's prefix-sum pass uses — and queries become instant (O(1)), but now a single changed value means recomputing every total after it (O(n) again). A Fenwick tree (also called a Binary Indexed Tree) refuses that trade: both operations run in O(log n), by storing not the raw values and not the full running totals, but a small set of partial sums chosen so that any update touches only O(log n) of them, and any prefix query only needs to add up O(log n) of them back together.

Try it

The array below has 8 values, indexed 1 through 8 (Fenwick trees are conventionally 1-indexed — see Pitfalls for why). Below it is the tree's actual stored array, which does not hold the same numbers — each stored slot covers a range of the values above it. Pick an index and a delta and press Update, or pick an index and press Query for the prefix sum through it, then step through to watch exactly which stored slots get touched and why.

Why it works

Every index i (1-indexed) "owns" a range of the values array: the lowbit(i) values ending at i, where lowbit(i) = i & -i is the value of i's lowest set bit in binary. Stored slot tree[6] (binary 110, lowbit 2) holds the sum of values 5 and 6. Stored slot tree[4] (binary 100, lowbit 4) holds the sum of values 1 through 4. Those two ranges, back to back, exactly cover values 1 through 6 — which is why querying the prefix sum through index 6 only ever needs to add tree[6] + tree[4]: start at i, add tree[i], then strip off the lowest set bit (i -= i & -i) to jump to the next range down, until i reaches 0. Every index's binary representation decomposes into at most log₂(n) set bits, so a query is never more than log₂(n) additions.

Updating runs the same idea in reverse: to change value i, every stored slot whose range contains i needs the same delta applied. Those are exactly the slots reached by repeatedly adding the lowest set bit (i += i & -i) starting from i — updating index 3 touches tree[3] (covers value 3 alone), then tree[4] (covers 1 through 4, which includes 3), then tree[8] (covers 1 through 8, which also includes 3), then stops once it would step past the end of the array. That climb is at most log₂(n) steps for the same reason the query descent is.

Reference implementation

Building from an existing array of values doesn't need n separate updates — each slot can push its own total onto its immediate parent once, in a single O(n) pass, which is what the demo above actually does:

class FenwickTree {
  constructor(values) {
    this.n = values.length;
    this.tree = new Array(this.n + 1).fill(0);
    for (let i = 1; i <= this.n; i++) {
      this.tree[i] += values[i - 1];
      const parent = i + (i & -i);
      if (parent <= this.n) this.tree[parent] += this.tree[i];
    }
  }

  update(i, delta) {
    for (; i <= this.n; i += i & -i) this.tree[i] += delta;
  }

  query(i) {                    // prefix sum of values[1..i]
    let sum = 0;
    for (; i > 0; i -= i & -i) sum += this.tree[i];
    return sum;
  }

  rangeSum(l, r) {               // sum of values[l..r], both inclusive
    return this.query(r) - this.query(l - 1);
  }
}

Pitfalls

It's 1-indexed for a reason, not by convention. The whole mechanism runs on i & -i, the lowest set bit of i — and 0 & -0 is 0, which would make both the update loop's i += i & -i and the query loop's i -= i & -i spin forever at index 0 instead of terminating. Treating index 0 as "the empty prefix, sum zero, stop immediately" — exactly what query(0) does above — sidesteps that, but only because indexing starts at 1. Reusing 0-indexed array conventions from everywhere else on this site here is the single most common way to break a Fenwick tree implementation.

It only works for operations with an inverse. Sum works because rangeSum(l, r) = query(r) - query(l-1) — subtraction undoes addition. Range minimum or maximum has no such inverse (you can't recover the min of [l, r] from the min of [1, r] and the min of [1, l-1] — knowing "the smallest value up to r" and "the smallest value up to l-1" tells you nothing about whether the true minimum of [l, r] was in the earlier or later part), so this exact structure can't be repurposed for range-min/max queries the way it's tempting to try after seeing how cleanly it handles sums. A segment tree — a different structure entirely — supports arbitrary range queries (min, max, sum, and more) at the cost of roughly double the memory and a small constant-factor slowdown versus a Fenwick tree's tight, single-array layout.

Complexity

Time: O(log n) for both update and query — each walks at most log₂(n) stored slots, one per set bit in the index's binary form. Building from an existing array is O(n), not O(n log n), since the constructor above pushes each slot's total onto its parent exactly once rather than re-running n independent O(log n) updates. Space: O(n) — one stored array the same size as the input, no per-node pointers or overhead the way binary search trees or tries need, closer in spirit to the binary heap's plain-array-as-implicit-tree approach than to any node-linked structure on this site. Binary lifting over this same stored array can also answer k-th-smallest and rank queries in O(log n), the identical pair of questions Order Statistics Tree answers a node-linked way — but only over a value universe that's known and compressed to a fixed range ahead of time, unlike that page's open-ended value range.

This site's guide, Choosing a Range Query Structure, compares this entry against the other five Array-Backed Trees structures that answer the same kind of question side by side.