Fenwick Tree (BIT)

Overview

What this concept solves

A Fenwick tree (Binary Indexed Tree, BIT) is a 1-indexed array that lets you answer prefix-sum queries and apply point updates in O(log n) time using O(n) space. Every cell t[i] stores the aggregate of a range of the underlying array that ends at index i and has length equal to lowbit(i) — the value of the lowest set bit of i, computed as i & -i. That single bit trick is what makes the whole structure tick: it partitions the index space into non-overlapping ranges whose sizes are powers of two, mirroring the binary representation of any index.

The asymmetry between query and update is the structure's most striking property. *A prefix-sum query hops down**: start at index `k`, accumulate `t[k]`, then subtract `lowbit(k)` from `k` to jump to the next relevant cell. Each hop peels off the lowest set bit, so the chain terminates in at most O(log n) steps — exactly as many steps as there are set bits in k. A point update hops up**: start at the changed index, add the delta to `t[i]`, then add `lowbit(i)` to i to reach the next cell whose range includes position i*. Again O(log n) steps, now climbing toward n. Same bit trick, opposite direction.

Compared with a segment tree, a Fenwick tree is strictly narrower in scope — it only handles prefix sums and point updates natively — but it wins on every practical metric when that scope is sufficient. The implementation is a single flat array with no tree-node structs, no left/right child pointers, and a constant factor roughly 2–3× smaller. It fits in a single cache line far longer into the traversal. For competitive programming and production systems that need fast frequency counting, order-statistic queries, or inversion counting, the BIT is the default first choice. The segment tree earns its keep the moment you need range-minimum, range-GCD, or lazy range updates.

Mechanics

How it works

Building the tree

Initialise t[1..n] = 0. For each position i in the input array, call update(i, a[i]). The tree is built in O(n log n). (An O(n) construction exists: copy the array, then for each i propagate to the parent i + lowbit(i).)
After construction, t[i] holds the sum of a[i - lowbit(i) + 1 .. i] — a range of lowbit(i) consecutive elements ending at i.

Prefix-sum query — hop down by subtracting lowbit

Set sum = 0, i = k.
While i > 0: add t[i] to sum; set i -= lowbit(i).
Return sum. This accumulates disjoint ranges that together cover a[1..k] exactly.

Point update — hop up by adding lowbit

Set i = pos.
While i <= n: add delta to t[i]; set i += lowbit(i).
Every cell whose coverage range includes pos gets updated — no more, no less.

Range sum

To sum a[l..r], compute query(r) - query(l - 1).
The two prefix queries each cost O(log n), so range sums are also O(log n).

lowbit(i) = i & −i

In two's-complement arithmetic, -i flips all bits of i and adds 1. The result of i & -i is a number with exactly one bit set — the position of the lowest set bit of i. For i = 6 (binary 110), lowbit(6) = 2 (binary 010), meaning t[6] covers 2 elements. For i = 8 (binary 1000), lowbit(8) = 8, meaning t[8] covers 8 elements — the whole prefix.

Range sum = query(r) − query(l − 1)

Because query(k) returns the exact prefix sum a[1] + … + a[k], subtracting two prefix queries gives any contiguous range sum. This is the standard identity: a[l..r] = prefix[r] - prefix[l-1]. The BIT encodes this identity into its structure, so both halves cost only O(log n).

Interactive prototype

Run it. Break it. Tune it.

Sandboxed simulation embedded right in the page. No setup, no install.

simulation › Fenwick Tree (BIT)

About this simulation

An array a[1..8] (default [3,2,5,1,4,6,2,7]) paired with the BIT cells t[1..8], drawn as bars that span each cell's coverage range. Enter a prefix length k and press Query to watch the hop-down path; enter an index and delta then press Update to watch the ripple-up path. Reset restores the defaults. The speed slider controls animation pace. Three demo buttons automate the key ideas: "Query full prefix [1..8]" traces the full down-hop chain, "Update a[5] += 10 (ripple)" shows the upward cascade in slow motion, and "Range sum [3..6]" fires query(6) then query(2) and subtracts — watch two separate hop paths light up in sequence. Stats panel tracks n, the current result, hops taken, and lowbit(k).

Hands-on

Try these on your own

Open the prototype above, run each experiment, predict the answer, then verify.

try 01

Watch the prefix query hop down

Click "Query full prefix [1..8]". The prototype fires query(8) and animates the down-hop chain: it starts at index 8 (lowbit(8)=8, covers the whole array), accumulates t[8], then subtracts 8 — reaching 0 and stopping in a single hop. Now manually enter k = 7 and press Query. Because 7 is 0b111, lowbit(7)=1, so the chain hops 7→6→4→0, touching three cells. Watch the dashed arrows trace each subtraction. The hop count in the stats panel equals the number of set bits in k.

try 02

Watch the update ripple up

Click "Update a[5] += 10 (ripple)". Index 5 is 0b101, so lowbit(5)=1; the chain climbs 5→6→8, updating three cells before exceeding n=8. The bars for t[5], t[6], and t[8] all grow — those are exactly the BIT cells whose coverage ranges include position 5. Slow the speed slider to minimum and step through: each bar animates independently, making the upward cascade tangible. Then run Query full prefix [1..8] again and confirm the result increased by exactly 10.

try 03

Range sum [3..6] = query(6) − query(2)

Click "Range sum [3..6]". The prototype fires query(6) first — hop path 6→4→0, two hops — then fires query(2) — hop path 2→0, one hop — and subtracts. Two separate dashed-arrow paths light up in sequence, coloured differently so you can tell them apart. The stats panel shows both intermediate results and the final difference. Verify by hand: with default a=[3,2,5,1,4,6,2,7], the range a[3..6] = 5+1+4+6 = 16. Confirm the prototype agrees.

try 04

Free play — break it yourself

Press Reset to restore defaults, then try these stress tests: (1) Set the speed slider to maximum and rapidly alternate Query and Update — confirm the result stays consistent after each round-trip. (2) Enter idx = 1, delta = -3 and update — then query the full prefix; the BIT handles negative deltas without any special case. (3) Enter k = 8 and query, note the result, then update every index by +1 (eight separate updates) and query again — the new result should be exactly 8 higher. If anything looks off, step through slowly with the speed slider at minimum to find which hop goes wrong.

In practice

When to use it — and what you give up

Reach for a Fenwick tree when

You need dynamic prefix sums — frequencies that change over time (streaming data, online algorithms, competitive programming standard problems like counting inversions).
Your queries are strictly prefix sums or range sums and updates are point updates — no range-min, range-max, or lazy propagation needed.
Cache performance matters — the BIT's single flat array fits in L1/L2 cache far better than a pointer-linked segment tree on large n.
You want minimal code — the entire structure is ~10 lines; a mistake-prone segment tree is 40–80 lines.
Order-statistic queries (k-th smallest element) over a frequency array — BIT binary search runs in O(log n) with a simple bit-descent.

Reach for something else when

Static data — if the array never changes, compute a plain prefix-sum array once in O(n) and answer every query in O(1). The BIT adds complexity for no gain.
Range updates — updating a[l..r] += delta requires a more complex BIT variant (difference-array trick) or is cleaner with a segment tree with lazy propagation.
Non-sum aggregates — range-minimum, range-GCD, range-XOR with range updates all belong to the segment tree. The Fenwick tree's hop structure only works for invertible aggregates (sum, XOR) in the prefix direction.
Persistent queries — if you need to query a historical version of the array, use a persistent segment tree. BITs don't compose persistently without significant extra machinery.

Pros

O(log n) query and update — both operations touch at most ⌊log₂ n⌋ + 1 cells, making the BIT fast in practice even for n = 10⁷.
Minimal memory — a single array of length n + 1; no node structs, no child pointers, no auxiliary arrays. Memory footprint is the same as the input.
Cache-friendly — contiguous array layout means the hop chain almost always hits warm cache lines, giving a real-world constant factor 2–3× better than a pointer-based segment tree.
Tiny implementation — query and update each fit in five lines. Less code means fewer bugs, easier audits, and fast implementation under contest time pressure.
Composable — BITs naturally extend to 2D (prefix sums over a grid) with the same bit trick applied to both axes, keeping O(log² n) per operation.

Cons

Only invertible prefix aggregates — works natively for sum and XOR, but range-minimum and range-GCD are not invertible, so a BIT cannot answer range-min queries without a second data structure.
Range updates are awkward — incrementing a contiguous range a[l..r] += delta requires either a separate difference-BIT or a two-BIT trick; a segment tree with lazy propagation handles this more cleanly.
1-indexed by convention — most BIT implementations are 1-indexed because lowbit(0) = 0 would loop forever. Off-by-one errors are common when converting between 0-indexed input and 1-indexed BIT.
Harder to reason about — the implicit 'tree' (which cell covers which range) is invisible in the array. Debugging a wrong answer requires mentally simulating the lowbit hops, which is less intuitive than inspecting a segment tree's explicit nodes.
No persistence or lazy propagation — advanced segment tree techniques (persistent trees, beats/kinetic heaps) have no clean BIT analogue; switching structures mid-project is expensive.

Reference

Code & further reading

A minimal reference implementation and pointers worth bookmarking.

fenwick-tree.ts

// Fenwick Tree (Binary Indexed Tree) — 1-indexed, point update, prefix sum.
class FenwickTree {
  private t: number[];
  private n: number;

  constructor(n: number) {
    this.n = n;
    this.t = new Array(n + 1).fill(0);
  }

  // Build from an existing array a[0..n-1] in O(n log n).
  static from(a: number[]): FenwickTree {
    const ft = new FenwickTree(a.length);
    for (let i = 0; i < a.length; i++) ft.update(i + 1, a[i]);
    return ft;
  }

  // The bit trick: lowest set bit of i.
  private lowbit(i: number): number {
    return i & -i;
  }

  // Point update: add delta to position pos (1-indexed).
  // Hops UP: i += lowbit(i) until i > n.  O(log n).
  update(pos: number, delta: number): void {
    for (let i = pos; i <= this.n; i += this.lowbit(i)) {
      this.t[i] += delta;
    }
  }

  // Prefix sum: sum of a[1..k].
  // Hops DOWN: i -= lowbit(i) until i <= 0.  O(log n).
  query(k: number): number {
    let sum = 0;
    for (let i = k; i > 0; i -= this.lowbit(i)) {
      sum += this.t[i];
    }
    return sum;
  }

  // Range sum: sum of a[l..r] (both 1-indexed).
  rangeQuery(l: number, r: number): number {
    return this.query(r) - this.query(l - 1);
  }
}

// Usage
const ft = FenwickTree.from([3, 2, 5, 1, 4, 6, 2, 7]);
console.log(ft.query(8));        // 30  — full prefix
console.log(ft.rangeQuery(3, 6)); // 16  — a[3]+a[4]+a[5]+a[6]
ft.update(5, 10);                // a[5] becomes 14
console.log(ft.query(8));        // 40  — updated prefix

References & further reading

7 sources

Knowledge check

Did the prototype land?

Quick questions, answers revealed on submit. No scoring saved.

question 01 / 03

Cell `t[6]` in a Fenwick tree stores the sum of which elements of the underlying array?

question 02 / 03

A point update at index 5 in a Fenwick tree of size 8 modifies which cells?

question 03 / 03

Why does a Fenwick tree generally outperform a segment tree in practice for prefix-sum / point-update workloads, even though both are O(log n)?

0/3 answered