Fenwick Tree (Binary Indexed Tree)

Intuition

A prefix-sum array answers "sum of a[l..r]" in O(1), but a single update forces you to rebuild O(n) prefixes. A plain array updates in O(1) but sums in O(n). A Fenwick tree (also called a binary indexed tree, BIT) sits in between: both operations take O(log n), with a tiny array and about ten lines of code.

The trick is to pre-store sums of cleverly chosen blocks so that any prefix splits into at most log2(n) of them. Use 1-based positions and define lowbit(i) = i & -i, the value of the lowest set bit of i (for example, lowbit(12) = 4 because 12 = 1100 in binary). Slot tree[i] stores the sum of the block a[i - lowbit(i) + 1 .. i], a block of length lowbit(i) that ends at i.

• Prefix query: to sum a[1..i], add tree[i], then jump to i - lowbit(i) (strip the lowest set bit) and repeat until 0. For i = 7 (binary 111) you visit 7, 6 (110) and 4 (100): blocks [7,7], [5,6] and [1,4]. At most one step per set bit, so O(log n).
• Point update: to add delta to a[i], update every block that contains i: tree[i], then i + lowbit(i), and so on while i <= n. Each jump moves to a block at least twice as long, so again O(log n).

Range sums come from two prefixes: sum(a[l..r]) = prefix(r) - prefix(l - 1). That subtraction is the main limitation: a plain Fenwick tree needs an invertible operation (sum, XOR, product modulo a prime). Range minimum or maximum with arbitrary updates is segment tree territory.

The real power in interviews comes from building the tree over values instead of positions: keep count[v] = how many times value v has appeared. Then prefix(v) answers "how many elements seen so far are at most v?", which turns many counting problems into a left-to-right (or right-to-left) scan.

When to use it in interviews / OAs

• Point updates mixed with range sums: a mutable range sum query, running totals under edits.
• Counting pairs by order: inversion count, "count of smaller numbers after self", reverse pairs (a[i] > 2 * a[j]), "count of range sum" in a window of values. Scan the array and query a BIT over (compressed) values.
• Dynamic order statistics: a multiset of bounded integers supporting insert, delete, rank and k-th smallest. In Python this is a light replacement for a balanced BST.
• Range add: range add + point query uses one BIT on the difference array; range add + range sum uses two BITs.
• Offline sweeps: sort queries by one coordinate and keep a BIT over the other, for example counting points inside rectangles, or distinct values in subarrays (sort queries by right end, keep only the last occurrence of each value).
• 2D grids with updates: a 2D BIT (a BIT of BITs) answers submatrix sums in O(log R * log C) per operation.

Template

The core structure with an O(n) build. Public indices are 0-based and ranges are half-open like Python slices; the internal array is 1-based because lowbit(0) = 0 would loop forever.

class Fenwick:
    # Point add + prefix sums. Public indices are 0-based; tree slots are 1-based.
    def __init__(self, values: list[int]) -> None:
        self.n = len(values)
        self.tree = [0] + list(values)
        for i in range(1, self.n + 1):  # O(n) build: push each slot into its parent once.
            j = i + (i & -i)
            if j <= self.n:
                self.tree[j] += self.tree[i]

    def add(self, i: int, delta: int) -> None:
        i += 1
        while i <= self.n:
            self.tree[i] += delta
            i += i & -i  # Climb to the next block that also covers position i.

    def prefix_sum(self, r: int) -> int:
        # Sum of values[0:r].
        s = 0
        while r > 0:
            s += self.tree[r]
            r -= r & -r  # Drop the lowest set bit: jump to the previous block.
        return s

    def range_sum(self, l: int, r: int) -> int:
        # Sum of values[l:r].
        return self.prefix_sum(r) - self.prefix_sum(l)


fw = Fenwick([5, 1, 4, 2, 3])
assert fw.range_sum(1, 4) == 7
fw.add(2, 10)  # values[2] becomes 14.
assert fw.range_sum(0, 5) == 25 and fw.prefix_sum(3) == 20

Building by n separate add calls costs O(n log n). The loop in __init__ is O(n): after slot i is complete, add it into its parent i + lowbit(i).

BIT over values. Count, for every element, how many smaller elements appear to its right. Scan from the right; before inserting nums[i], ask how many of the already inserted values have a smaller rank. Large or negative values are first mapped to ranks 1..m (coordinate compression).

def count_smaller_after(nums: list[int]) -> list[int]:
    # For each i, how many j > i have nums[j] < nums[i].
    ranks = {v: r for r, v in enumerate(sorted(set(nums)), start=1)}  # Coordinate compression to 1..m.
    m = len(ranks)
    tree = [0] * (m + 1)  # tree counts how many of each rank we have seen.
    out = [0] * len(nums)
    for i in range(len(nums) - 1, -1, -1):  # Scan right to left: the BIT holds elements to the right.
        r = ranks[nums[i]]
        j, s = r - 1, 0  # Count ranks 1..r-1, i.e. strictly smaller values.
        while j > 0:
            s += tree[j]
            j -= j & -j
        out[i] = s
        while r <= m:
            tree[r] += 1
            r += r & -r
    return out


assert count_smaller_after([5, 2, 6, 1]) == [2, 1, 1, 0]
assert sum(count_smaller_after([3, 1, 2])) == 2  # Total = number of inversions.

Ordered multiset with k-th smallest. Binary search over prefix sums would take O(log^2 n). Binary lifting does it in O(log n): build the answer position bit by bit from the highest power of two. Because pos only contains larger powers of two so far, tree[pos + step] is exactly the count of the slots pos + 1 .. pos + step, so each step is one array read.

class BITMultiset:
    # Multiset of integers in [0, size) with rank and k-th smallest in O(log size).
    def __init__(self, size: int) -> None:
        self.n = size
        self.tree = [0] * (size + 1)
        self.total = 0

    def add(self, x: int, cnt: int = 1) -> None:  # Use cnt = -1 to remove one copy.
        self.total += cnt
        i = x + 1
        while i <= self.n:
            self.tree[i] += cnt
            i += i & -i

    def count_less(self, x: int) -> int:
        s, i = 0, x
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def kth(self, k: int) -> int:
        # k-th smallest (1-based) by binary lifting; assumes 1 <= k <= total.
        pos = 0
        step = 1 << self.n.bit_length()
        while step:
            nxt = pos + step
            if nxt <= self.n and self.tree[nxt] < k:  # tree[nxt] is exactly the count of slots pos+1..nxt.
                pos = nxt
                k -= self.tree[nxt]
            step >>= 1
        return pos  # Slot pos + 1 holds the answer, i.e. value pos.


ms = BITMultiset(10)
for x in (7, 3, 3, 9):
    ms.add(x)
assert ms.kth(1) == 3 and ms.kth(2) == 3 and ms.kth(3) == 7 and ms.count_less(7) == 2
ms.add(3, -1)
assert ms.kth(2) == 7 and ms.total == 3

Range add, range sum. Write a as prefix sums of a difference array d. Adding v to a range changes only two entries of d, and the sum of a[1..p] expands to (p + 1) * sum(d[1..p]) - sum(i * d[i] for i in 1..p), so two BITs (one over d[i], one over i * d[i]) give both operations in O(log n).

class RangeAddRangeSum:
    # Two BITs over the difference array d: a[1..p] sums to (p + 1) * sum(d) - sum(i * d[i]).
    def __init__(self, n: int) -> None:
        self.n = n
        self.t1 = [0] * (n + 1)  # Sums of d[i].
        self.t2 = [0] * (n + 1)  # Sums of d[i] * i.

    def _add(self, i: int, v: int) -> None:  # 1-based point add on d.
        w = v * i
        while i <= self.n:
            self.t1[i] += v
            self.t2[i] += w
            i += i & -i

    def _prefix(self, p: int) -> int:  # Sum of a[1..p], 1-based.
        s1 = s2 = 0
        i = p
        while i > 0:
            s1 += self.t1[i]
            s2 += self.t2[i]
            i -= i & -i
        return (p + 1) * s1 - s2

    def range_add(self, l: int, r: int, v: int) -> None:  # a[l:r] += v (0-based, half-open).
        self._add(l + 1, v)
        self._add(r + 1, -v)

    def range_sum(self, l: int, r: int) -> int:  # Sum of a[l:r].
        return self._prefix(r) - self._prefix(l)


ra = RangeAddRangeSum(5)
ra.range_add(1, 4, 2)  # a = [0, 2, 2, 2, 0]
ra.range_add(0, 2, 5)  # a = [5, 7, 2, 2, 0]
assert ra.range_sum(0, 5) == 16 and ra.range_sum(1, 3) == 9

Complexity

Operation	Time	Notes
build	O(n)	O(n log n) if you call add n times
point add, prefix/range sum	O(log n)
k-th smallest (binary lifting)	O(log n)	needs a counts BIT
range add + range sum	O(log n)	two BITs
2D query/update	O(log R * log C)

Space is O(n) (or O(number of distinct values) for a BIT over compressed values).

Common pitfalls

• Index 0. i & -i is 0 when i is 0, so a 0-based loop never ends. Shift every index by one inside the structure.
• Assignments vs increments. The tree stores sums of deltas. To set a[i] = x, keep a copy of a and call add(i, x - a[i]).
• Non-invertible operations. Range min/max cannot be computed as a difference of prefixes. (A BIT can keep prefix maxima if values only ever increase, which is enough for LIS-style DPs, but not for general updates.)
• Compression mistakes. Compress every value that can be queried or inserted, including values that appear only in queries, and decide whether you need rank - 1 (strictly smaller) or rank (smaller or equal).
• k-th out of range. Binary lifting assumes 1 <= k <= total; check the total count first.
• Overflow in Java/C++. Pair counts can reach about n^2 / 2; use 64-bit integers.

Interview variations

• Range sum query, mutable (1D and 2D).
• Count of smaller numbers after self, global inversions, reverse pairs, count of range sum (BIT over compressed prefix sums).
• Create sorted array through instructions: the cost of each insert is min(count less, count greater).
• Sliding window median or any "k-th smallest in a changing window" with values compressed in advance: add and remove counts, then ask kth.
• Longest increasing subsequence variants with a BIT that stores prefix maxima (and counts, for "number of LIS") over compressed values.
• Offline distinct-count queries sorted by right endpoint, keeping only the latest occurrence of each value in the BIT.