Fenwick Trees (Binary Indexed Trees)

Analogy categoryAnalogies

Introduction

A Fenwick tree, also called a Binary Indexed Tree (BIT), is a compact structure that maintains prefix sums (or other invertible aggregates) over an array while supporting point updates, both in O(log n) time, using far less memory and code than a full segment tree. It works by cleverly assigning each index responsibility for a range of elements determined by the position of its lowest set bit — the 'lowbit' trick. BITs are a favorite in competitive programming for problems like counting inversions, frequency tables, and cumulative frequency queries because of their small constant factor and simple implementation.

🏏

Cricket analogy: Like a compact running-total board that updates a single over's score and instantly recomputes the innings total, using far less chalk and effort than redrawing the whole scoreboard from scratch each time.

Structure/Syntax

python

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

    @staticmethod
    def _lowbit(x):
        return x & (-x)

    def update(self, i, delta):
        # add 'delta' to the element at 1-indexed position i
        while i <= self.n:
            self.tree[i] += delta
            i += self._lowbit(i)

Explanation

The BIT is stored as a 1-indexed array where tree[i] holds the sum of a range of original elements ending at index i, whose length is determined by lowbit(i) = i & (-i), the value of the lowest set bit of i. To update index i, we add the delta to tree[i] and then move to i + lowbit(i), repeating until we exceed n — this walks up through all ranges that include index i. To compute a prefix sum up to index i, we add tree[i] and move to i - lowbit(i), repeating until i reaches 0 — this walks down through the ranges that exactly partition [1, i]. Both operations take O(log n) steps because each jump changes at least one bit in the binary representation of i, and there are only O(log n) bits.

🏏

Cricket analogy: Updating a score means climbing to progressively larger over-groupings by adding the lowest active "bit" of the over number, touching only O(log n) groupings; reading a cumulative total means descending by removing that same bit, touching the same small number of steps.

Example

python

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

    @staticmethod
    def _lowbit(x):
        return x & (-x)

    def update(self, i, delta):
        while i <= self.n:
            self.tree[i] += delta
            i += self._lowbit(i)

    def prefix_sum(self, i):
        total = 0
        while i > 0:
            total += self.tree[i]
            i -= self._lowbit(i)
        return total

    def range_sum(self, l, r):
        # inclusive 1-indexed range [l, r]
        return self.prefix_sum(r) - self.prefix_sum(l - 1)


# Build a BIT over arr = [3, 2, -1, 6, 5, 4, -3, 3] (0-indexed source)
arr = [3, 2, -1, 6, 5, 4, -3, 3]
bit = FenwickTree(len(arr))
for idx, val in enumerate(arr, start=1):   # convert to 1-indexed updates
    bit.update(idx, val)

print(bit.prefix_sum(4))     # 3+2-1+6 = 10
print(bit.range_sum(3, 6))   # -1+6+5+4 = 14

bit.update(3, 10)            # add 10 to arr[2] (0-indexed) => now -1 becomes 9
print(bit.prefix_sum(4))     # 3+2+9+6 = 20

Complexity

Both update and prefix_sum run in O(log n) time because each step strips or adds a single bit in the binary representation of the index, and an integer up to n has O(log n) bits. Building a BIT from scratch by repeated updates costs O(n log n), though it can be done in O(n) with a specialized linear-time construction. Space usage is O(n), just one array of size n+1 — substantially leaner than a segment tree's ~4n array and simpler pointer-free logic, which is why BITs are preferred when only prefix-sum-style aggregates (not arbitrary min/max range queries) are needed.

🏏

Cricket analogy: Updating and reading a compact running total both take O(log n) steps because each step touches one bit of the over number; building the whole board from scratch by repeated updates costs O(n log n), though a faster linear build exists, and it uses far less chalkboard space than a full detailed segment-by-segment scoreboard.

Key Takeaways

A Fenwick tree (BIT) supports point updates and prefix-sum queries in O(log n) time using a single array of size n+1.
The core trick is lowbit(i) = i & (-i), which isolates the lowest set bit and determines the range each index is responsible for.
update(i, delta) walks upward via i += lowbit(i); prefix_sum(i) walks downward via i -= lowbit(i).
Range sums are computed as prefix_sum(r) - prefix_sum(l - 1).
BITs are simpler and use less memory than segment trees but are best suited to invertible aggregates like sum, not min/max.

Practice what you learned

1. What does the lowbit(i) = i & (-i) operation compute?

2. In the update() method, why does the loop use 'i += lowbit(i)'?

3. What is the time complexity of both update() and prefix_sum() in a Fenwick tree over n elements?

4. How do you compute the sum of a range [l, r] (1-indexed, inclusive) using a Fenwick tree?

5. Compared to a segment tree, what is a key limitation of a standard Fenwick tree?

Was this page helpful?

Segment Trees

Topics covered

#Python#DataStructuresStudyNotes#DataStructures#FenwickTreesBinaryIndexedTrees#Fenwick#Trees#Binary#Indexed#StudyNotes#SkillVeris