Fenwick tree
Update one element and query a prefix sum, both in , with one array and two loops.
When
When prefix sums are not enough because the array changes between queries. For sums (or anything with an inverse, such as xor) it is shorter and faster than a segment tree.
The idea
With 1-based indexing, node holds the sum of the last elements up to and including . is the lowest set bit of . For example, node holds .
- Prefix up to : add and clear the lowest bit, , until 0.
- Update at : update and climb, , until .
Each loop takes at most steps.
Range update, point query. Range Update Queries asks for "add to " and "what is ?". Keep the difference array inside the Fenwick tree: add(l, v), add(r + 1, -v), and is prefix(k).
The -th element. With non-negative values, lowerBound(k) walks down the bits from the highest and finds the smallest whose prefix is , in . With occurrence counts, this is the -th smallest element of a multiset.
Pitfalls
- Indexing starts at 1. With
add(0, v)the loop never ends, because . - In
Salary Queriesthe values go up to . Compress the coordinates first, reading all queries offline.
Code
No main: it goes below the #include lines, using namespace std and using ll = long long.
// Fenwick tree (binary indexed tree), 1-indexed.
// add(i, v): a[i] += v. prefix(i): a[1] + ... + a[i]. Both O(log n).
// i & -i is the lowest set bit of i: node i stores the sum of the last (i & -i) elements up to i.
struct Fenwick {
int n;
vector<ll> tree;
Fenwick(int size) : n(size), tree(size + 1, 0) {}
void add(int i, ll v) {
while (i <= n) {
tree[i] += v;
i += i & -i;
}
}
ll prefix(int i) {
ll s = 0;
while (i > 0) {
s += tree[i];
i -= i & -i;
}
return s;
}
ll rangeSum(int l, int r) {
return prefix(r) - prefix(l - 1);
}
// Smallest i with prefix(i) >= k, assuming all values are non-negative. Returns n + 1 if none.
int lowerBound(ll k) {
int pos = 0;
int step = 1;
while (step * 2 <= n) {
step *= 2;
}
while (step > 0) {
if (pos + step <= n && tree[pos + step] < k) {
pos += step;
k -= tree[pos];
}
step /= 2;
}
return pos + 1;
}
};
Tested on 500 random cases against a slow, obviously correct solution, with AddressSanitizer and UndefinedBehaviorSanitizer (g++ (Ubuntu 13.3.0-6ubuntu2~24.04.1) 13.3.0, 2026-11-18 23:27 UTC).
Practice on CSES
In order: the first is the plain application, the rest need a twist.
- Dynamic Range Sum Queries · Range Queries
- Range Update Queries · Range Queries
- Salary Queries · Range Queries
More in the USACO Guide
- Point Update Range Sum · usaco.guide/gold/PURS
In English, with more problems per level.