TreesData structureaka binary indexed tree, BIT

Fenwick Tree

A compact array-based tree that supports prefix-sum queries and point updates in O(log n) using the binary representation of indices.

▶ VisualizePattern: Prefix SumPractice (3)
Progress

Definition

A Fenwick tree (binary indexed tree) stores partial sums in an array tree[1..n] where tree[i] holds the sum of the lowbit(i) elements ending at i — lowbit(i) = i & -i is the value of the lowest set bit. With that layout a prefix sum sum(1..i) is obtained by repeatedly stripping the lowest set bit from i, and a point update a[i] += d is done by repeatedly adding the lowest set bit. Both loops run at most log₂ n + 1 times.

It solves the same problem as a Segment Tree restricted to invertible operations (sum, xor, counting) with one-third of the memory and a fraction of the code. Range sums come from prefix(r) - prefix(l - 1). With two Fenwick trees it also supports range add + range sum; with a tree over value-indices it counts "elements ≤ x seen so far" for inversion counting and order statistics.

prefix sumpoint updatelowbitO(log n)compact

Intuition

A mental model before the formal terms.

Picture the numbers 1 to 16 and imagine that each index i is responsible for a block of lowbit(i) cells ending at i: index 12 (1100₂) covers 4 cells (9–12), index 8 (1000₂) covers 8 cells (1–8), index 13 (1101₂) covers 1 cell. To get the sum of cells 1–13, read block 13 (cell 13), then block 12 (cells 9–12), then block 8 (cells 1–8): three reads, and 13 → 12 → 8 → 0 is exactly "remove the lowest set bit" each step.

Updating cell 5 (0101₂) must touch every block that contains it: 5, 6 (0110₂, cells 5–6), 8 (1000₂, cells 1–8), 16. Each is the previous one plus its lowest set bit.

How it works

  1. Use 1-based indexing. tree has size n + 1, initialized to zero.
  2. update(i, delta): while i <= n: tree[i] += delta; i += i & -i.
  3. prefix(i): s = 0; while i > 0: s += tree[i]; i -= i & -i; return s.
  4. rangeSum(l, r) = prefix(r) - prefix(l - 1).
  5. build in O(n): copy a into tree (1-based), then for each i, let j = i + lowbit(i); if j <= n add tree[i] to tree[j].
  6. Find the smallest index with prefix ≥ k (order statistic): walk from the highest power of two downward, taking a step when the accumulated sum stays below k. O(log n).

Why it works

Define tree[i] = sum(a[i - lowbit(i) + 1 .. i]). The ranges covered by i, i - lowbit(i), i - 2·lowbit(...)… are disjoint and tile [1, i] exactly, so summing them gives the prefix. Each subtraction clears one set bit, so at most log₂ n + 1 terms.

Cell i lies in the block of index j iff j - lowbit(j) < i ≤ j. The sequence i, i + lowbit(i), … enumerates exactly these j, and each step at least doubles the lowest set bit, so the update loop is also logarithmic.

Operations

OperationDescriptionCost
update(i, delta)Add delta to a[i] by climbing i += lowbit(i).O(log n)
prefix(i)Sum of a[1..i] by descending i -= lowbit(i).O(log n)
rangeSum(l, r)prefix(r) - prefix(l - 1).O(log n)
build(a)Linear-time construction by pushing each tree[i] into its parent.O(n)
findByPrefix(k)Smallest i with prefix(i) ≥ k using a binary-lifting walk.O(log n)

Recognition

How to tell a problem wants this.

  • Prefix sums or range sums with point updates, n, q up to 10^5–10^6.
  • "Count how many previous elements are smaller" — inversion counts, "count of smaller numbers after self".
  • Kth smallest in a multiset under insertions/deletions using a BIT over values.
  • Any Segment Tree problem where the operation is invertible and memory or code size matters.
“sum of subarray” → Prefix Sum“parity/odd occurrences” → Bit Manipulation“range query” → Segment / Fenwick Tree

Interactive demo

Play, step, change the input. ← → and space work too.

a
·
0
0
1
0
2
0
3
0
4
0
5
0
6
0
7
0
8
a (1-based)
·
0
3
1
2
2
-1
3
6
4
5
5
4
6
-3
7
3
8
1/32Build a Fenwick tree over 8 values (1-based). tree[i] will cover the `i & -i` elements ending at i — the lowest set bit of i decides the range length.
Current index iVisited on this walkUpdatedSummed into the answer
PseudocodeLearn Fenwick Tree →
1build: tree[i] += a[i]; j = i + (i & -i); if j <= n: tree[j] += tree[i]
2update(i, delta): while i <= n: tree[i] += delta; i += i & -i
3prefix(i): s = 0; while i > 0: s += tree[i]; i -= i & -i; return s
4range(l, r) = prefix(r) - prefix(l-1)
Variables
n8
Complexity
access O(log n)
search O(log n)
insert —
delete —
Speed

Pseudocode

1update(i, delta):
2  while i <= n: tree[i] += delta; i += i & -i
3prefix(i):
4  s = 0
5  while i > 0: s += tree[i]; i -= i & -i
6  return s
7rangeSum(l, r): return prefix(r) - prefix(l - 1)

Implementation

11 · 1-based tree array; lowbit(i) = i & -i
2class FenwickTree:
3    """tree[i] holds the sum of the lowbit(i) elements ending at index i."""
4 
5    def __init__(self, n_or_array: int | list[int]):
6        if isinstance(n_or_array, int):
7            self.n = n_or_array
8            self.tree = [0] * (self.n + 1)
9        else:
10            # O(n) build: push each tree[i] into its parent.
11            a = list(n_or_array)
12            self.n = len(a)
13            self.tree = [0] + a
14            for i in range(1, self.n + 1):
15                j = i + (i & -i)
16                if j <= self.n:
17                    self.tree[j] += self.tree[i]
18 
192 · Point update: climb i += i & -i
20    def update(self, i: int, delta: int) -> None:
21        """a[i] += delta (1-based i)."""
22        while i <= self.n:
23            self.tree[i] += delta
24            i += i & -i
25 
263 · Prefix sum: strip i -= i & -i
27    def prefix(self, i: int) -> int:
28        """Sum of a[1..i]."""
29        s = 0
30        while i > 0:
31            s += self.tree[i]
32            i -= i & -i
33        return s
34 
354 · Range sum from two prefixes
36    def range_sum(self, l: int, r: int) -> int:
37        """Sum of a[l..r], 1-based inclusive."""
38        return self.prefix(r) - self.prefix(l - 1)
39 
405 · Smallest index with prefix >= k (binary lifting)
41    def find_by_prefix(self, k: int) -> int:
42        """Requires all values non-negative. Returns n + 1 if no such index."""
43        pos = 0
44        step = 1 << self.n.bit_length()
45        while step:
46            nxt = pos + step
47            if nxt <= self.n and self.tree[nxt] < k:
48                pos = nxt
49                k -= self.tree[nxt]
50            step >>= 1
51        return pos + 1
Walkthrough
  1. __init__ accepts int | list[int]; isinstance narrows it — a size allocates zeros, a list is copied behind a leading 0 and built in O(n) by pushing each slot into its parent.
  2. update climbs i += i & -i; Python's arbitrary-precision ints compute i & -i correctly for any positive i.
  3. prefix strips the lowest set bit per iteration, summing the disjoint blocks tiling [1, i].
  4. range_sum subtracts two prefixes (invertible operations only).
  5. find_by_prefix starts the step at 1 << n.bit_length() and halves it each round, walking right while the running sum stays below k.
Complexity (this implementation)
time O(log n) update/prefix; O(n) build · space O(n)

All loops are iterative — no recursion-limit concerns. Pure-Python loop overhead dominates; the same code with a C extension mindset would use numpy only for bulk builds, not per-op.

Language notes
  • i & -i works on Python's big ints because negative numbers behave as infinite two's complement.
  • int.bit_length() replaces the manual "largest power of two ≤ n" loop used in other languages.
  • Type hints use the modern int | list[int] union syntax (Python 3.10+).
Common mistakes in this language
  • Calling update(0, d) — index 0 makes the climb loop a no-op; shift application indices to 1-based.
  • Passing the new value rather than the delta; compute delta = new - old yourself.
  • Using find_by_prefix with negative values, breaking prefix monotonicity.
Language differences that matter here
  • i & -i (lowbit) relies on two's complement: native in C++ and in JS/TS via 32-bit coercion; Python emulates infinite two's complement on big ints, so it also just works.
  • JS/TS bitwise coercion caps usable n below 2^31 and exact sums at 2^53; C++ uses long long; Python has no limits on either.
  • Constructor overloading: real overloads in C++, a number | number[] union narrowed by typeof in TS, isinstance in Python.
  • Highest power of two ≤ n: a doubling loop in C++/JS/TS versus Python's 1 << n.bit_length() shifted down.

Complexity

OperationAverageWorstNote
AccessO(log n)O(log n)a[i] = prefix(i) - prefix(i-1); keep the raw array for O(1).
SearchO(log n)O(log n)findByPrefix for monotone (non-negative) data.
Insert——Fixed size.
Delete——Update with -a[i].
UpdateO(log n)O(log n)
BuildO(n)O(n)
Prefix queryO(log n)O(log n)
Range queryO(log n)O(log n)
Point updateO(log n)O(log n)
SpaceO(n)Exactly n + 1 integers. 2D variant is O(n·m) space and O(log n · log m) per operation.

Advantages & disadvantages

Advantages
  • Ten lines of code and n + 1 integers of memory.
  • Excellent constant factors; cache-friendly array layout.
  • Extends easily to 2D (O(log² n)) and to range-update/range-query with two trees.
Disadvantages
  • Only invertible operations (sum, xor); no min/max range queries without tricks.
  • No native range updates or lazy propagation — needs the two-tree transformation.
  • The bit-manipulation layout is unintuitive; off-by-one errors with 0-based data are common.

Use cases

  • Range Sum Query – Mutable and frequency counting under updates.
  • Counting inversions and "smaller elements after self" with coordinate compression.
  • Order statistics on a dynamic multiset (kth smallest via prefix walk).
  • Arithmetic coding and cumulative frequency tables — Fenwick's original application.
Use it when
  • Prefix/range sums (or xor, counts) with point updates and tight memory or time limits.
  • Inversion counting and "smaller to the right" after coordinate compression.
  • Dynamic order statistics (kth smallest) via the prefix walk.
Avoid it when
  • Range min/max or other non-invertible aggregates — Segment Tree.
  • Range updates with range queries of a non-sum kind — Segment Tree with lazy propagation.
  • No updates — plain Prefix Sum.

Alternatives

Segment TreePrefix SumSparse TableDifference Array
Compare: Segment Tree vs Fenwick Tree

Common mistakes

  • Using index 0: 0 & -0 == 0 makes the update loop never advance. Always shift to 1-based.
  • Passing the new value instead of the delta to update.
  • Building with n calls to update (O(n log n)) when the linear build is available — fine for correctness, but avoid in tight limits.
  • Using findByPrefix with negative values, which breaks the monotonicity it relies on.
  • Overflow in sums — use 64-bit accumulators.

Interview patterns

  • Range Sum Query – Mutable in ten lines.
  • Count of smaller numbers after self: compress values, scan right-to-left, prefix(v - 1) then update(v, 1).
  • Number of longest increasing subsequences / LIS in O(n log n) with a max-Fenwick over compressed values.
  • Two BITs for range add + range sum: derive sum = (i+1)·B1(i) - B2(i).
  • 2D BIT for submatrix sums with updates.
Interview questions on this
Mock interviews

Interview problems

Longest Increasing SubsequencemediumRange Sum Query — MutablemediumRange XOR Queries with Updatesmedium