Fenwick Tree

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

[Range Queries]|

Jul 9, 2026

|explanatory_notes.md|

#fenwick#bit#binary-indexed-tree#prefix-sum#point-update

$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 $i$ stores a partial sum covering $\text{lowbit}(i)$ elements, where $\text{lowbit}(i) = i \mathbin{\&} (-i)$ .

How It Works

add(i, v) — update index

i

by adding

v

, propagate via

i \mathrel{+}= i \mathbin{\&} (-i)

prefix(i) — compute prefix sum up to

i

via

i \mathrel{-}= i \mathbin{\&} (-i)

query(l, r) — range sum via

\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)

using the propagation trick (faster than

n

individual updates)

Complexity

Build —

O(n)

Update / Query —

O(\log n)

Space —

O(n)