guest@itl:~/home/data-structures$
templates/fenwick-tree.cpp
compilable
$cat templates/fenwick-tree

Fenwick Tree

Binary Indexed Tree for prefix sum queries and point updates in O(log n).

[Data Structures]|
Jul 9, 2026
|explanatory_notes.md|
#fenwick#bit#binary-indexed-tree#prefix-sum#point-update
Log in to track progress, save custom versions, and organize into collections.Log In
$cat source_code/
cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int MAXN = 2e5 + 5;
ll bit[MAXN];
int n;

void build(ll a[]) {
    for (int i = 1; i <= n; i++) {
        bit[i] += a[i];
        int j = i + (i & -i);
        if (j <= n) bit[j] += bit[i];
    }
}

void add(int i, ll v) {
    for (; i <= n; i += i & -i)
        bit[i] += v;
}

ll prefix(int i) {
    ll s = 0;
    for (; i > 0; i -= i & -i)
        s += bit[i];
    return s;
}

ll query(int l, int r) {
    return prefix(r) - prefix(l - 1);
}
31 linesutf-8
$cat explanation_notes.md
notes_viewer --renderedmarkdown (math enabled)

Fenwick Tree (BIT)

Lightweight structure for prefix sums with point updates. Each index ii stores a partial sum covering lowbit(i)\text{lowbit}(i) elements, where lowbit(i)=i&(−i)\text{lowbit}(i) = i \mathbin{\&} (-i).

How It Works

  • add(i, v) — update index ii by adding vv, propagate via i+=i&(−i)i \mathrel{+}= i \mathbin{\&} (-i)

  • prefix(i) — compute prefix sum up to ii via i−=i&(−i)i \mathrel{-}= i \mathbin{\&} (-i)

  • query(l, r) — range sum via prefix(r)−prefix(l−1)\text{prefix}(r) - \text{prefix}(l-1)

    • When to Use

  • Point update + prefix/range sum queries

  • Simpler and faster constant than segment tree when you only need sums

  • Inversion counting, coordinate compression queries

    • Notes

  • 1-indexed internally

  • build() runs in O(n)O(n) using the propagation trick (faster than nn individual updates)

    • Complexity

  • Build — O(n)O(n)

  • Update / Query — O(log⁡n)O(\log n)

  • Space — O(n)O(n)