Fenwick Tree (Binary Indexed Tree): Complete Guide

A Fenwick tree stores partial sums at power-of-two boundaries. Each index i owns exactly i & -i elements ending at i.

Why it matters:

~15 lines of code gives you O(log n) point updates and prefix queries — half the code of a segment tree.

The one bit-manipulation trick to memorize:

i & -i isolates the lowest set bit = the size of block tree[i]. Update climbs i += i & -i. Query descends i -= i & -i.

Core Template

class FenwickTree {
    int[] tree;

    public FenwickTree(int n) {
        tree = new int[n + 1];   // 1-based!
    }

    public void add(int i, int d) {          // point update
        for (; i < tree.length; i += i & -i)
            tree[i] += d;
    }

    public int prefix(int i) {               // sum of [1..i]
        int s = 0;
        for (; i > 0; i -= i & -i)
            s += tree[i];
        return s;
    }

    public int range(int l, int r) {         // sum of [l..r]
        return prefix(r) - prefix(l - 1);
    }
}

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

    def add(self, i, d):            # point update
        while i < len(self.tree):
            self.tree[i] += d
            i += i & -i

    def prefix(self, i):            # sum of [1..i]
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def range(self, l, r):          # sum of [l..r]
        return self.prefix(r) - self.prefix(l - 1)

class FenwickTree {
    vector<int> tree;

public:
    explicit FenwickTree(int n) : tree(n + 1) {}   // 1-based!

    void add(int i, int d) {                       // point update
        for (; i < (int)tree.size(); i += i & -i)
            tree[i] += d;
    }

    int prefix(int i) const {                      // sum of [1..i]
        int s = 0;
        for (; i > 0; i -= i & -i)
            s += tree[i];
        return s;
    }

    int range(int l, int r) const {                // sum of [l..r]
        return prefix(r) - prefix(l - 1);
    }
};

class FenwickTree {
  constructor(n) {
    this.tree = Array(n + 1).fill(0); // 1-based!
  }

  add(i, d) { // point update
    for (; i < this.tree.length; i += i & -i) this.tree[i] += d;
  }

  prefix(i) { // sum of [1..i]
    let s = 0;
    for (; i > 0; i -= i & -i) s += this.tree[i];
    return s;
  }

  range(l, r) { // sum of [l..r]
    return this.prefix(r) - this.prefix(l - 1);
  }
}

Everything else in Fenwick problems is this template plus bookkeeping.

Pattern: Count Inversions / Rank Queries

Watch update(3, +5) climb 3 → 4 → 8, then query(5) descend 5 → 4 → 0 on [3, 2, −1, 6, 5, 4, −3, 3]. Press ▶ to animate.

Fenwick Tree (Binary Indexed Tree)

Point updates and prefix sums in O(log n) using lowbit hops.

tree[i] owns the 2^lowbit(i) elements ending at i. An update adds the delta and jumps i += i & -i; a prefix query sums tree[i] and jumps i -= i & -i. Each operation climbs O(log n) ancestors, touching only the nodes responsible for the changed/queried range.

SEGMENT TREE VISUALIZER

Steps –

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        update(i, d): while i <= n:  tree[i] += d;   i += i & -i
                      
                        2
                        query(i):     s = 0; while i > 0:  s += tree[i];  i -= i & -i
                      
                        3
                        tree[i] owns exactly the 2^(lowbit) elements ending at i

Store a BIT over value ranges instead of positions. “How many seen values are less than x” = prefix(x - 1):

for each element v (left to right):
    inversions += countSeen - prefix(v)   # bigger ones already seen
    add(v, 1)

Same template — only what you index changes.

BIT = index over values or positions + two loops built on i & -i.

Common Mistakes

Using 0-based indices.

i & -i of 0 is 0 → infinite loop. Index 0 must stay unused; shift everything by 1.

Off-by-one in range().

range(l, r) = prefix(r) − prefix(l − 1) — forgetting the - 1 includes element l-1.

Assuming min/max works out of the box.

The subtract-trick (prefix(r) − prefix(l−1)) only works for invertible ops like sum. Min/max need a different BIT design (store values in a segment-tree-like layout) — just use a segment tree instead.

Complexity

Operation	Time
add	O(log n)
prefix	O(log n)
Space	O(n)

⚠️ Animation & Content Notice

Fenwick Tree

Core Template

Pattern: Count Inversions / Rank Queries

⚠️ Animation & Content Notice

Fenwick Tree (Binary Indexed Tree)

Common Mistakes

Complexity

Premium Content

My Private Notes

Earn Premium with Referrals

Core Template

Pattern: Count Inversions / Rank Queries

Fenwick Tree (Binary Indexed Tree)

Common Mistakes

Complexity

Premium Content

My Private Notes