What is a Fenwick tree?

A Fenwick tree, or binary indexed tree (BIT), is a compact array structure that supports prefix-sum queries and single-element updates on an array, each in O(log n) time. Every index i in the tree stores the sum of a contiguous block of the original array whose length is the lowest set bit of i, which lets both operations hop across only a logarithmic number of cells.

What is the lowbit trick i AND minus i?

The expression i AND minus i isolates the lowest set bit of i using two-complement arithmetic. In a Fenwick tree that value is exactly the length of the range that tree cell i is responsible for, and it is the step size for moving between cells: a prefix query subtracts it to walk down, and an update adds it to walk up.

How does a Fenwick tree answer a prefix-sum query?

To sum the first i elements, start at index i, add tree[i], then move to i minus lowbit(i), repeating until you reach 0. Each cell contributes a disjoint block, and together they tile the range 1..i, so only about log n cells are touched.

Fenwick tree vs segment tree?

A Fenwick tree is smaller, simpler and faster for prefix or range sums with point updates, using just one array and a couple of lines. A segment tree is more general: it handles min, max, gcd and range updates with lazy propagation, at the cost of more code and memory. Use a Fenwick tree when sums with point updates are all you need.

Algorithm · Data Structures

Bits Do the Walking.

Don't memorize the Fenwick tree — watch the bits do the walking. A binary indexed tree stores clever partial sums so a prefix-sum query and a single-element update both finish in O(log n). The whole thing runs on one arithmetic trick: i & -i, the lowest set bit, tells each cell exactly which range it owns and how far to hop next.

binary indexed tree · i & -i · query down · update up

LOWBIT

i & -i — the lowest set bit of i; the size of the block cell i owns.

TREE CELL

tree[i] holds the sum of a block of length lowbit(i) ending at i.

QUERY

Prefix sum: add tree[i], then i −= i & -i, until 0.

UPDATE

Bump a point: add delta, then i += i & -i, until past n.

fenwick.sim — array [3,2,-1,6,5,4,-3,3] (1-indexed)

Ready

Top is the array A (1-indexed); below is the tree[], where each cell owns a block whose length is its lowest set bit. Press Step to see a prefix query walk down, then a point update walk up.

lowbit(i) = i & -i

Overview

Phase

—

Running sum

One array, both operations fast

A prefix-sum array answers range sums in O(1) but an update costs O(n). A Fenwick tree keeps updates fast too — O(log n) — by storing overlapping partial sums instead of full prefixes. The magic index scheme is what makes it tiny: cell i covers the block of length lowbit(i) ending at i. Cell 6 (binary 110, lowbit 2) covers positions 5–6; cell 4 (100, lowbit 4) covers 1–4; cell 8 (1000) covers everything. To sum a prefix, you hop across a handful of these blocks that tile it exactly.

Each cell owns a block

tree[i] = sum of A over [i − lowbit(i) + 1 .. i]. Different cells cover different power-of-two ranges.

Query walks down

Prefix sum of 1..i: add tree[i], then i −= i & -i, repeat to 0. About log n cells, all disjoint.

Update walks up

Change A[i] by delta: add delta to tree[i], then i += i & -i, repeat past n. Only the cells that include i change.

Range sum

Sum of [l..r] = prefix(r) − prefix(l − 1). Two queries, still O(log n).

Prefix query

O(log n)

Point update

O(log n)

Build

O(n)

Space

O(n)

The Fenwick tree is a favorite because it is so small — a single array and two three-line loops — and cache-friendly. It handles prefix and range sums with point updates beautifully. When you need min, max, gcd, or range updates, reach for a segment tree instead; when the data never changes, a plain prefix-sum array is simpler still.

Check yourself

1 · What does i & -i compute?

The lowbit is both the range length for cell i and the hop size for moving between cells.

2 · How does a prefix-sum query move through the tree?

Start at i, add tree[i], then i −= i & -i until 0 — the disjoint blocks tile 1..i.

3 · When is a Fenwick tree preferred over a segment tree?

Fenwick shines for sums with point updates; segment trees handle min/max/gcd and range updates.

Questions

Why is it 1-indexed?

The lowbit walk relies on index 0 being the terminator for queries (you stop when i reaches 0) and the powers-of-two block structure lining up from 1. A 0-indexed array is shifted by one internally.

Can a Fenwick tree do range updates?

Yes, with a second BIT (or a difference-array trick), you can support range updates and range queries, still in O(log n). It is a common competitive-programming extension.

How do you build it in O(n)?

Instead of n separate updates (O(n log n)), copy the values in and push each cell contribution to its immediate parent (i + lowbit(i)) once, which fills the whole tree in linear time.

Prefix sums that update — in log time.

One array, one bit trick. Query walks down, update walks up, both O(log n).

← All algorithms Segment Tree → Prefix Sums → Big-O Cheatsheet →

Finished this one? 0 / 47 Algorithms done

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

Algorithms & DSA

Bits Do the Walking.

One array, both operations fast

Each cell owns a block

Query walks down

Update walks up

Range sum

Check yourself

Questions

Prefix sums that update — in log time.

Explore the topic

More Algorithms

Explore more from Vibe Engines

One array, both operations fast

Each cell owns a block

Query walks down

Update walks up

Range sum

Check yourself

Questions

Prefix sums that update — in log time.

Explore the topic

More Algorithms

Explore more from Vibe Engines

Get the next one in your inbox.