Fenwick Tree (BIT)

#How does it work?

A Fenwick tree (Binary Indexed Tree) computes prefix sums and single-element updates in O(log n), with far less code than a segment tree. The whole structure is one array.

tree[i] holds the sum of the part of a that ends at i and is i & −i long (the lowest set bit of i). For example, for i = 6 (110₂), i & −i = 2, so tree[6] = a[5] + a[6].

For a prefix sum, start at i, add tree[i] and clear the lowest set bit (i -= i & −i) until i is zero. When adding to an element, do the opposite and add the lowest bit (i += i & −i), updating every cell that covers that position. Either way it takes at most log n steps.

#Try it yourself

#Basic operations

prefixSum(i)

Returns the sum of a[1..i] in O(log n).

add(i, Δ)

Adds Δ to a[i] and updates the cells covering it in O(log n).

rangeSum(l, r)

prefixSum(r) − prefixSum(l − 1).

build(a)

Builds in O(n log n) by adding each element, or cleverly in O(n).

#Example code

The same algorithm in 8 languages. Every program is compiled, run and checked to print the same output.

class Fenwick:
    """tree[i] holds the sum of the i & -i elements ending at position i (1-based)."""

    def __init__(self, n: int) -> None:
        self.tree = [0] * (n + 1)

    def add(self, i: int, delta: int) -> None:
        while i < len(self.tree):
            self.tree[i] += delta
            i += i & -i  # the next node that covers i

    def prefix_sum(self, i: int) -> int:
        total = 0
        while i > 0:
            total += self.tree[i]
            i -= i & -i  # drop the lowest set bit
        return total

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


a = [5, 2, 7, 3, 6, 1, 4, 8]
fw = Fenwick(len(a))
for i, v in enumerate(a, start=1):
    fw.add(i, v)

print(fw.prefix_sum(6))   # a[1..6]
fw.add(6, 3)
print(fw.prefix_sum(6))
print(fw.range_sum(3, 6))  # a[3..6]

#Complexity

The binary form of i has at most log n bits, so every operation takes at most log n steps. It has the same complexity as a segment tree with smaller constants and only a few lines of code; in return it doesn't directly support range queries for non-invertible operations such as min or max.

#When to use it?

Frequency and count tables, order statistics (the k-th smallest element), counting inversions, two-dimensional prefix sums and anywhere cumulative sums change often.

#Practice

Log in to answer questions and save your progress.