Trees6 min read

Fenwick Tree (BIT)

Prefix sums in \(O(\log n)\) with elegant bit manipulation — simpler than a segment tree

build: \(O(n \log n)\)prefix query: \(O(\log n)\)point update: \(O(\log n)\)space: \(O(n)\)

A Fenwick tree (also called a Binary Indexed Tree or BIT) is a data structure that supports prefix sum queries and point updates in \(O(\log n)\) time using a single flat array — no pointers, no explicit tree structure.

Invented by Peter Fenwick in 1994, it achieves the same asymptotic complexity as a segment tree for prefix queries with simpler code and a smaller constant factor. The secret is a clever use of the least significant bit (LSB) of array indices.

The problem it solves

Given an array, you want to:

Query the prefix sum from index 1 to i: sum(1, i)
Update a single element: arr[i] += delta

A plain array gives \(O(n)\) query, \(O(1)\) update. Prefix sums give \(O(1)\) query, \(O(n)\) update. A Fenwick tree gives \(O(\log n)\) for both.

◈ Explore Fenwick tree

← → arrow keys to step · click elements to interact

Fenwick Tree: Update & Prefix Sum

class FenwickTree:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)  # 1-indexed

    def update(self, i, delta):
        while i <= self.n:
            self.tree[i] += delta
            i += i & (-i)  # move to parent

    def prefix_sum(self, i):
        total = 0
        while i > 0:
            total += self.tree[i]
            i -= i & (-i)  # move to responsible ancestor
        return total

    def range_sum(self, l, r):
        return self.prefix_sum(r) - self.prefix_sum(l - 1)

arr = [1, 3, 5, 7, 9, 11]
ft = FenwickTree(len(arr))
for i, v in enumerate(arr):
    ft.update(i + 1, v)

print(ft.prefix_sum(4))   # 1+3+5+7 = 16
print(ft.range_sum(2, 5)) # 3+5+7+9 = 24
ft.update(3, 5)           # arr[2] += 5 (was 5, now 10)
print(ft.range_sum(2, 5)) # 3+10+7+9 = 29

Output

16
24
29

Note: The magic of Fenwick trees: BIT[i] stores the sum of exactly lowbit(i) elements ending at index i, where lowbit(i) = i & (-i) is the least significant set bit. Navigation through the tree is just repeated addition or subtraction of the LSB.

How it works: the lowbit trick

The key operation is lowbit(i) = i & (-i), which extracts the lowest set bit of i. For example: lowbit(6) = 6 & (-6) = 6 & ...11111010 = 000000010 = 2.

Each index i in the BIT array stores the sum of elements in the range [i - lowbit(i) + 1, i]:

BIT[1] = arr[1] (lowbit(1)=1, covers 1 element)
BIT[2] = arr[1]+arr[2] (lowbit(2)=2, covers 2 elements)
BIT[4] = arr[1]+arr[2]+arr[3]+arr[4] (lowbit(4)=4, covers 4 elements)
BIT[6] = arr[5]+arr[6] (lowbit(6)=2, covers 2 elements)

Prefix sum query

To compute sum(1, i): start at i, add BIT[i], then jump to i - lowbit(i), repeat until i becomes 0.

pseudocode

def prefix_sum(i):
  total = 0
  while i > 0:
    total += BIT[i]
    i -= i & (-i)  # remove LSB
  return total

This touches at most \(\log_2(n)\) indices (each step removes a bit).

Point update

To update arr[i] += delta: start at i, add delta to BIT[i], then jump to i + lowbit(i), repeat until i > n.

pseudocode

def update(i, delta):
  while i <= n:
    BIT[i] += delta
    i += i & (-i)  # add LSB

Range query

Range sum from l to r: sum(1, r) - sum(1, l-1). Two prefix queries = still \(O(\log n)\).

Fenwick vs. Segment Tree

Fenwick tree: simpler code, smaller constant, only handles prefix queries and point updates natively
Segment tree: more flexible (range updates, range min/max), but more code and memory

If you only need prefix sums with point updates, always prefer a Fenwick tree — it's faster in practice and trivial to implement correctly.

Complexity

Build (n point updates)Can also build in \(O(n)\) with a smarter algorithm

Near-linear\(O(n \log n)\)

Prefix sum queryAt most \(\log_2(n)\) steps — removes one bit per step

Fast\(O(\log n)\)

Point updateAt most \(\log_2(n)\) steps — adds one bit per step

Fast\(O(\log n)\)

Range sum queryTwo prefix queries: sum(r) - sum(l-1)

Fast\(O(\log n)\)

SpaceSingle flat array of size n+1 (1-indexed)

Linear\(O(n)\)

Count Inversions Using Fenwick Tree

def count_inversions(arr):
    """Count pairs (i, j) where i < j but arr[i] > arr[j]."""
    # Coordinate compress
    sorted_unique = sorted(set(arr))
    rank = {v: i+1 for i, v in enumerate(sorted_unique)}
    n = len(sorted_unique)
    tree = [0] * (n + 1)

    def update(i):
        while i <= n: tree[i] += 1; i += i & (-i)

    def query(i):
        s = 0
        while i > 0: s += tree[i]; i -= i & (-i)
        return s

    inv = 0
    for v in arr:
        r = rank[v]
        inv += query(n) - query(r)  # elements already inserted that are > v
        update(r)
    return inv

print(count_inversions([3, 1, 2, 5, 4]))  # 3

Output

Challenge

Quick check

What does lowbit(12) equal? (12 in binary is 1100)

Segment Tree

Answer range queries in \(O(\log n)\) with \(O(\log n)\) point updates

→

Prefix Sums

Pre-calculate a running total so you can sum any subarray in instant \(O(1)\) time

→