---
title: "Fenwick Tree (Binary Indexed Tree)"
summary: Prefix sums in one loop, with the two-line tricks for range updates and "find smallest index with prefix ≥ x".
difficulty: core
tags: [prefix-sum, inversion, offline]
time: log n
space: n
prereq: [structures/segment-tree]
see: [trees/euler-tour, structures/segment-tree]
---

:::definition label="The object"
`t[i]` stores the sum over the half-open range $(i - \operatorname{lowbit}(i), i]$, where $\operatorname{lowbit}(i) = i \& -i$. That single choice of ranges makes both update and query a "walk the set bits" loop.
:::

```cpp fenwick.cpp
struct BIT {
    int n; vector<ll> t;
    BIT(int n) : n(n), t(n + 1) {}
    void add(int i, ll v) { for (; i <= n; i += i & -i) t[i] += v; }
    ll sum(int i) { ll s = 0; for (; i > 0; i -= i & -i) s += t[i]; return s; }
    ll range(int l, int r) { return sum(r) - sum(l - 1); }     // 1-indexed, inclusive
};
```

:::props title="Why it beats a segment tree when it applies"
- ~half the memory and ~3× better constants (one array, no recursion),
- `kth` search in $O(\log n)$ with a *bit-lifting* loop (below) — segment trees need the same trick, so no loss,
- it supports any **invertible** monoid (sum, xor, count). Not min/max-with-decrease: there is no inverse, which is the whole "when do I need a segment tree instead" answer.
:::

```cpp bit-lifting-kth.cpp
// smallest i with sum(i) >= target, assuming all values >= 0
int kth(ll target) {
    int idx = 0;
    for (int pw = 1 << __lg(n); pw; pw >>= 1)
        if (idx + pw <= n && t[idx + pw] < target) { target -= t[idx + pw]; idx += pw; }
    return idx + 1;
}
```

## Range add + range sum: two trees
```cpp two-bits.cpp
// add x on [l, r]:   B1: +x at l, -x at r+1 ;  B2: +x*(l-1) at l, -x*r at r+1
// prefix(p) = p * B1.sum(p) - B2.sum(p)
void range_add(int l, int r, ll x) { b1.add(l, x); b1.add(r + 1, -x); b2.add(l, x * (l - 1)); b2.add(r + 1, -x * r); }
ll prefix(int p) { return p * b1.sum(p) - b2.sum(p); }
ll range_sum(int l, int r) { return prefix(r) - prefix(l - 1); }
```
The formula comes from writing $\sum_{i \le p} a_i$ after the difference-array substitution and collecting terms: $\sum_{i \le p} \operatorname{pre}_i = \sum_{j \le i} x_j \implies (p - j + 1) x_j$, so you need $\sum x_j$ and $\sum j \cdot x_j$ — two Fenwicks, one for each. (Same algebra as lazy segment tree, but with zero lines of push code.)

:::example title="Inversions in 8 lines — the canonical BIT problem"
```cpp
// count pairs i < j with a[i] > a[j], values compressed to [1, n]
BIT bit(n);
ll inv = 0;
for (int i = n - 1; i >= 0; i--) {
    inv += bit.sum(a[i] - 1);          // elements to the right that are smaller
    bit.add(a[i], 1);
}
```
Read it as a sweep: `bit` holds the suffix multiset, and `sum(k)` answers "how many seen values are $\le k$". Coordinate compression (`sort` + `unique` + `lower_bound`) is the standard preprocessing when values reach $10^9$.
:::

:::props title="The four offline patterns"
- **count pairs with condition on both coordinates**: sort by one, BIT over the other (inversions, "smaller elements to the left", dominance counting),
- **$k$-th smallest in a static range**: BIT over value-sorted positions + binary search, or a persistent segment tree for queries online,
- **"number of distinct values in $[l,r]$"**: sort queries by right end, keep 1 only at the *last* occurrence of each value, answer with a range sum — a two-line reduction,
- **subtree queries on a tree** (@trees/euler-tour): the flat array *is* a Fenwick's job description.
:::

:::note title="Fenwick of Fenwicks, and when to stop"
2D point update / rectangle sum is a BIT over $x$ whose nodes hold a BIT over $y$ — $O(\log^2 n)$ per operation with $O(n \log n)$ memory (offline: collect each node's $y$-values first). It is genuinely useful for $n \le 2 \times 10^5$, but if the second dimension is also dynamic, a segment tree of treaps or plain divide-and-conquer is usually the shorter path.
:::

:::problems
- [[CSES 1734]] Distinct Values Queries | https://cses.fi/problemset/task/1734 | core | offline + last occurrence
- [[CSES 2169]] Nested Ranges Count | https://cses.fi/problemset/task/2169 | hard | sort + BIT
- [[CSES 1188]] Bit Inversions | https://cses.fi/problemset/task/1188 | hard | two BITs, careful algebra
:::