Understanding Fenwick Tree: A Step‑by‑Step Guide

Background

Given an array A = [2, 1, 1, 3, 2, 3, 4, 5], naïvely summing the first k elements requires k traversals, which is inefficient for large data sets.

A lightweight alternative to a segment tree is the Fenwick Tree (also called a Binary Indexed Tree), which excels at prefix‑sum queries and point updates.

Building the tree

To compute sum(A[1:7]) the tree stores:

tree[7] ← a[7]

tree[6] ← a[5] + a[6]

tree[4] ← a[1] + a[2] + a[3] + a[4]

The sum is obtained by adding the stored values: tree[7] + tree[6] + tree[4].

Similarly, for sum(A[1:5]) we use tree[5] + tree[4], and for sum(A[1:6]) we use tree[6] + tree[4].

Binary insight

Assuming 1‑based indexing, the binary forms of indices 1‑8 are:

1  → 0001
2  → 0010
3  → 0011
4  → 0100
5  → 0101
6  → 0110
7  → 0111
8  → 1000

The least significant bit (LSB) of an index indicates the size of the interval that tree[i] covers. For example, index 6 (0110) has LSB = 2, so tree[6] covers two elements (a[5] and a[6]).

Formally, tree[i] stores the sum of 2^k elements ending at position i, where k is the position of the LSB.

Jump rule

To move from one tree entry to the next during a query, repeatedly clear the rightmost 1 in the binary representation:

Index 6 (0110) → clear LSB → 0100 (index 4)

Index 7 (0111) → clear LSB → 0110 (index 6) → clear LSB → 0100 (index 4)

This operation is equivalent to i = i - (i & -i), i.e., subtract the LSB value.

General formulas

• LSB calculation : i & (-i) extracts the lowest set bit.

• Update (add value at position idx):

while idx <= size:
    tree[idx] += value
    idx += idx & -idx

• Query prefix sum up to idx:

result = 0
while idx > 0:
    result += tree[idx]
    idx -= idx & -idx
return result

Python implementation

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

    def update(self, idx, value):
        while idx <= self.size:
            self.tree[idx] += value
            idx += idx & -idx

    def query(self, idx):
        result = 0
        while idx > 0:
            result += self.tree[idx]
            idx -= idx & -idx
        return result

    def range_query(self, left, right):
        return self.query(right) - self.query(left - 1)

fenwick_tree = FenwickTree(5)
data = [1, 2, 3, 4, 5]
for i, val in enumerate(data, 1):
    fenwick_tree.update(i, val)
print(fenwick_tree.tree)          # [0, 1, 3, 3, 10, 5]
print(fenwick_tree.query(3))      # 6
print(fenwick_tree.range_query(2, 4))  # 9
fenwick_tree.update(3, 2)        # add 2 to element 3
print(fenwick_tree.tree)          # [0, 1, 3, 5, 12, 5]
print(fenwick_tree.query(3))      # 8

Summary

The Fenwick Tree combines a tree‑like structure with binary arithmetic, using the LSB as both the interval size and the jump step for queries and updates. This yields an O(log n) solution for prefix sums and point updates, demonstrated with concrete examples and a concise Python class.