Fenwick Tree / Binary Indexed Tree from Scratch (2026)

Published: March 31, 2026 | Category: Dsa | Reading time: ~15 min

A Fenwick Tree (Binary Indexed Tree, BIT) is a clever array-based data structure that efficiently computes prefix sums and supports point updates in O(log n) time. It uses the binary representation of indices to define a tree structure over the array, where each index stores the sum of a range of elements.

BITs are simpler and more memory-efficient than Segment Trees, using only O(n) space (one array of size n+1). They are ideal for problems involving prefix sums, frequency counts, and inversion count calculations. However, they do not natively support range updates without additional techniques.

📖 Table of Contents

Operations: Update and Query
Applications of Fenwick Tree

Operations: Update and Query

The key operation is finding the least significant set bit (LSB) using i & -i. To add a value at position i, propagate upward by adding LSB to i. To get prefix sum up to i, propagate downward by subtracting LSB from i. Both run in O(log n).

class Fenwick {
  vector bit;
public:
  Fenwick(int n) { bit.assign(n + 1, 0); }
  void update(int idx, int delta) {
    while (idx < bit.size()) {
      bit[idx] += delta;
      idx += idx & -idx;
    }
  }
  int query(int idx) {
    int sum = 0;
    while (idx > 0) {
      sum += bit[idx];
      idx -= idx & -idx;
    }
    return sum;
  }
  int rangeSum(int l, int r) {
    return query(r) - query(l - 1);
  }
};

Applications of Fenwick Tree

BITs are used for counting inversions (iterate from right to left, query how many smaller elements have been seen), implementing order statistics trees, and handling dynamic frequency tables. Range updates can be achieved with two BITs using difference arrays.

# Python: BIT with range update and point query
class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 2)
    def add(self, idx, val):
        while idx <= self.n:
            self.bit[idx] += val
            idx += idx & -idx
    def range_add(self, l, r, val):
        self.add(l, val)
        self.add(r + 1, -val)
    def point_query(self, idx):
        res = 0
        while idx > 0:
            res += self.bit[idx]
            idx -= idx & -idx
        return res

Frequently Asked Questions

Why use Fenwick Tree over Segment Tree?

Fenwick trees use less memory (n+1 vs 4n), are easier to implement, and have smaller constant factors. However, they only handle prefix queries and lack native range update support without extensions.

Can BIT handle non-invertible operations like min or max?

BIT relies on the invertibility of addition for range sum queries. For non-invertible operations like min or max, a Segment Tree is required. BIT only works with invertible associative operations (like XOR or sum).

Originally published on Ayodhyyya. Last updated June 1, 2026.