Introduction to Fenwick Trees

March 2026 · 15 min read

A Fenwick Tree (also called a Binary Indexed Tree, or BIT) is an elegant data structure that supports prefix queries and point updates in O(log n) time, using only a flat array of size n + 1. It was invented by Peter Fenwick in 1994.

If segment trees are the Swiss army knife of range queries, Fenwick trees are the scalpel, smaller, simpler, and faster in practice for the problems they can solve. This post builds the motivation and big picture before we dive into the mechanics.

The Problem: Prefix Sums with Updates

Consider an array:

arr = [3, 2, -1, 6, 5, 4, -3, 3, 7, 2, 3, 1]

We want two operations:

1. Prefix sum query: compute arr[0] + arr[1] + ... + arr[i]
2. Point update: set arr[i] += delta

We've seen this dilemma before:

The Fenwick tree hits the sweet spot: same O(log n) time as a segment tree for prefix-sum/point-update scenarios, but with half the memory, a smaller constant factor, and an implementation that fits in ~10 lines of code.

Why Not Just Use Segment Trees?

Segment trees are more general, they handle arbitrary range queries (min, max, GCD, etc.) and range updates. Fenwick trees trade generality for simplicity:

Rule of thumb: if the problem can be reduced to prefix sums with point updates (which covers more problems than you think), reach for a Fenwick tree first.

The Key Insight: Responsible Ranges

The entire magic of a Fenwick tree comes from one observation about binary representations of indices.

Every positive integer can be written in binary. The lowest set bit (also called lowbit) of a number determines the size of the range that index is "responsible" for in the Fenwick tree:

The function lowbit(i) is computed with a single bit operation:

lowbit(i) = i & (-i)

This isolates the lowest set bit. For example, 12 = 11002, so lowbit(12) = 01002 = 4, meaning index 12 is responsible for 4 elements: arr[9..12].

Every positive integer i has a unique binary expansion i = 2^{a₁} + … + 2^{aₖ}, and the prefix [1..i] partitions naturally into k contiguous chunks of those exact power-of-two sizes, ending at i. The rightmost chunk has length lowbit(i) — that's exactly what BIT[i] stores. A full derivation lives in Part 2.

Why does i & (-i) work?

In two's complement representation, -i is formed by flipping all bits of i and adding 1. This means all bits below the lowest set bit get flipped to 0, the lowest set bit stays as 1, and all bits above it get flipped. When you AND i with -i, only the lowest set bit survives.

  i   = ...1 0 0 0     (some bit pattern, lowest set bit at position k)
 ~i   = ...0 1 1 1     (flipped)
 -i   = ...0 1 1 1 + 1
       = ...1 0 0 0     (carry propagates, restoring the lowest set bit)
i&(-i)= ...1 0 0 0     (only the lowest set bit remains)

Visual Overview

Here's how a Fenwick tree looks for an 8-element array. Each bar represents an index and spans the elements it's responsible for. Click on any bar to see its range.

How Queries Work (Preview)

To compute prefix_sum(7), we don't scan all 7 elements. Instead we hop through indices by stripping the lowest bit each time:

prefix_sum(7):
  7  = 0111  →  BIT[7] covers [7, 7]       → +arr[7]
  6  = 0110  →  BIT[6] covers [5, 6]       → +arr[5]+arr[6]
  4  = 0100  →  BIT[4] covers [1, 4]       → +arr[1]+arr[2]+arr[3]+arr[4]
  0  = 0000  →  stop

Total: 3 additions instead of 7 — always O(log n)

Each step removes the lowest set bit: i -= lowbit(i). Since a number has at most log n bits, we visit at most log n indices.

How Updates Work (Preview)

To update arr[3] += 5, we need to update every Fenwick index whose range covers position 3. We walk upward by adding the lowest bit:

update(3, +5):
  3  = 0011  →  BIT[3] covers [3, 3]     → add 5
  4  = 0100  →  BIT[4] covers [1, 4]     → add 5
  8  = 1000  →  BIT[8] covers [1, 8]     → add 5
  16 → out of range, stop

Only 3 updates instead of rebuilding everything — O(log n)

Queries walk down (strip lowest bit), updates walk up (add lowest bit). This symmetry is the heartbeat of the Fenwick tree.

When to Use a Fenwick Tree

Reach for a Fenwick tree when:

• Prefix sums + point updates: The textbook use case.
• Range sum queries: sum(l, r) = prefix(r) - prefix(l-1).
• Counting inversions: A classic application — count how many earlier elements are greater than the current one.
• Coordinate compression + frequency counting: BITs shine in problems involving order statistics.
• 2D prefix sums with updates: Fenwick trees extend naturally to 2D.
• Competitive programming: When speed and simplicity matter.

Don't use a Fenwick tree when:

• You need range min/max queries (use a segment tree).
• You need lazy propagation for complex range updates (use a segment tree).
• The operation isn't invertible (the query trick sum(l,r) = prefix(r) - prefix(l-1) needs subtraction).

Series Roadmap

This series covers Fenwick trees from the ground up:

1. Introduction (this post), motivation, comparison, key insight
2. Structure & lowbit, binary representation, tree shape, how indices form a hierarchy
3. Point Updates & Prefix Queries, implementation, step-by-step animations, C++ code
4. Range Operations, range updates with point queries, range update + range query
5. Patterns & Practice, inversions, order statistics, 2D BIT, competition tricks