Fenwick Tree (BIT)
O(log n) per operationPrefix sums with point updates in logarithmic time, in a quarter of the code of a segment tree. Only works for invertible operations (sums, XOR), but when it applies it's shorter and harder to get wrong. Also the standard tool for counting inversions.
// use it on
CSES: Dynamic Range Sum Queries ↗
Point updates plus range sums: answer [l, r] as sum(r) − sum(l−1).
// the code
struct Fenwick { // 1-indexed
int n;
vector<long long> bit;
Fenwick(int n) : n(n), bit(n + 1, 0) {}
void add(int i, long long d) { // a[i] += d
for (; i <= n; i += i & -i) bit[i] += d;
}
long long sum(int i) { // a[1] + ... + a[i]
long long s = 0;
for (; i > 0; i -= i & -i) s += bit[i];
return s;
}
long long sum(int l, int r) { return sum(r) - sum(l - 1); }
};// more range queries