iii. Fenwick Tree

A Fenwick tree (binary indexed tree) stores partial sums over power-of-two blocks: node $i$ (0-indexed form below) covers $[i\&(i+1),i]$. Point update and prefix query are $O(\log n)$, with the smallest constant and code of any dynamic range structure. It works for any group operation (sum, XOR, modular product of units). Min/max work only for prefixes with monotone updates.

Implementation (0-indexed, half-open)

template<class T> struct Fenwick {
    int n; vector<T> t;
    Fenwick(int n = 0) : n(n), t(n) {}
    Fenwick(const vector<T>& a) : n(sz(a)), t(a) {           // O(n) build
        for (int i = 0; i < n; i++) { int j = i | (i + 1); if (j < n) t[j] += t[i]; }
    }
    void add(int i, T v) { for (; i < n; i |= i + 1) t[i] += v; }
    T sum(int r) const { T s{}; for (; r > 0; r &= r - 1) s += t[r - 1]; return s; }   // [0, r)
    T sum(int l, int r) const { return sum(r) - sum(l); }
    int lowerBound(T k) const {                  // largest p with sum(p) <= k (values >= 0)
        int p = 0;
        for (int pw = n ? 1 << __lg(n) : 0; pw; pw >>= 1)
            if (p + pw <= n && t[p + pw - 1] <= k) p += pw, k -= t[p - 1];
        return p;                                // so the (k+1)-th unit (0-indexed k) is at index p
    }
};

Descent: with counts as values, lowerBound(k) returns the index of the $k$-th element (0-indexed) of a multiset over $[0,n)$ in one $O(\log n)$ walk. That’s the fast order-statistics structure when values are known up front.

Proof: the Fenwick tree is correct

Block structure. For index $i\ge 0$ let $L(i)=\text{lowbit}(i+1)$ (the value of the lowest set bit of $i+1$, a power of two). Node $i$ stores the sum over the block $[i+1-L(i),i]$ — equivalently $i\&(i+1)=i+1-L(i)$. This is an exact partition fact about binary numbers: writing $i+1$ in binary as (some prefix)$10^k$, $L(i)=2^k$, and $i\&(i+1)$ clears exactly those trailing $k$ zero-then-the-flipped-bit positions of $i$ down to $i+1-2^k$.
add(i, v) visits exactly the ancestor chain of $i$. The step i |= i + 1 is algebraically i += lowbit(i+1) (OR-ing $i$ with $i+1$ turns the trailing run of $k$ ones in $i$ followed by a $0$ into exactly $i+2^k$, matching $\text{lowbit}(i+1)=2^k$). Each new $i^{\prime }=i+L(i)$ has block $[i^{\prime }+1-L(i^{\prime }),i^{\prime }]$, and since $i^{\prime }>i\ge i^{\prime }+1-L(i^{\prime })$ trivially as $L(i^{\prime })\ge 1$, and one checks $i^{\prime }+1-L(i^{\prime })\le i+1-L(i)$ follows from $i^{\prime }$‘s trailing-ones run being a strict superset of $i$‘s (the carry from adding $L(i)$ extends it) — so every ancestor’s block contains $i$, and the walk strictly increases $i$ and terminates at $i=n$ (the loop bound). Every node whose block contains the updated position gets $+v$, and (by the block partition, blocks nest or are disjoint, never partially overlapping — a standard binary-indexed-tree fact) no other node does, so sum queries after the update reflect exactly one extra $+v$ in every block covering position $i$.
sum(r) visits a disjoint cover of $[0,r)$. The step r &= r - 1 clears the lowest set bit of $r$, i.e. subtracts $\text{lowbit}(r)$. Writing $r$ in binary as a sum of its set bits’ values $r=2^{e_1}+\cdots +2^{e_m}$ ($e_1>\cdots >e_m$), the walk visits $r,r-2^{e_m},r-2^{e_m}-2^{e_{m-1}},\dots$ down to $0$, summing $t[r^{\prime }-1]$ at each stop — and $t[r^{\prime }-1]$‘s block is exactly $[r^{\prime }-2^{e^{\prime }},r^{\prime }-1]$ where $2^{e^{\prime }}=\text{lowbit}(r^{\prime })$, which is precisely the suffix of $[0,r)$ not yet covered by later (larger) terms already summed. Each of the $m=O(\log n)$ bits of $r$ contributes exactly one disjoint block, together tiling $[0,r)$ exactly, so the sum is exact.
$O(n)$ build. For each $i$, t[j] += t[i] where $j=i|(i+1)$ is exactly $i$‘s immediate successor in the ancestor chain add would walk, so this single bottom-up pass pushes each raw value up through that same chain one hop at a time; by the time index $j$ is itself processed it already holds the correct cumulative sum over its block, since every index below it in the chain has already pushed into it. Each index contributes to exactly one immediate parent, so the total work is $O(n)$ rather than the $O(n\log n)$ of $n$ separate add calls.
lowerBound(k) is binary search by level on a (conceptually) balanced binary structure over blocks of decreasing power-of-two size, descending only into a block when its prefix sum including that block would still be $\le k$ — the standard Fenwick-walk order-statistics argument, correct whenever all values are non-negative (so prefix sums are monotone in the walked position). $■$

Tested against brute-force prefix sums on random arrays with random point updates (build, add, sum) and against a monotone-count scan (lowerBound) — all match.

Range operations

Need	Trick
range add, point query	Fenwick over the difference array: add(l, v); add(r, -v), value = sum(i + 1)
range add, range sum	two Fenwicks $D$, $E$ over $d_i$ and $i\cdot d_i$: $\text{prefix}(r)=r\cdot D(r)-E(r)$
point update, prefix max with only increasing updates	t[i] = max(t[i], v) walks
range max with arbitrary updates	not a Fenwick job: segment tree
$k$-th element, rank	counts + descent
inversions, “smaller elements to the left”	scan, query, add (after compression)

template<class T> struct RangeFenwick {                       // a[l, r) += v, sum over [l, r)
    Fenwick<T> d, e; RangeFenwick(int n) : d(n + 1), e(n + 1) {}
    void add(int l, int r, T v) { d.add(l, v); d.add(r, -v); e.add(l, v * l); e.add(r, -v * r); }
    T prefix(int r) const { return d.sum(r) * r - e.sum(r); }
    T sum(int l, int r) const { return prefix(r) - prefix(l); }
};

Intermediate values reach about $n\cdot \max |\text{prefix}|$: use __int128 or a modint if they can overflow.

Proof: range-add range-sum via two Fenwicks

Let $d$ be the difference array of the range-add updates (so $d.\text{sum}(i+1)$ is the value at position $i$ after range-add-via-difference-array, same as Prefix Sums and Difference Arrays). The prefix sum is ${\sum }_{i<r}{\sum }_{j\le i}{d}_j$; swapping summation order, each $d_j$ ($j<r$) is counted once per $i\in [j,r)$, i.e. $(r-j)$ times: ${\sum }_{i<r}{a}_i={\sum }_{j<r}{d}_j(r-j)=r{\sum }_{j<r}{d}_j-{\sum }_{j<r}j{d}_j$. Tracking ${\sum }_{j<r}{d}_j$ in Fenwick $d$ and ${\sum }_{j<r}j{d}_j$ in Fenwick $e$ (both maintained by the same range-add-as-two-point-updates trick, since $e$‘s stamped value at a fixed position is just $v$ times that position, a constant multiple of the same update) gives prefix(r) = d.sum(r)*r - e.sum(r) exactly. Tested against direct $O(n)$ range-add simulation on random update/query sequences.

2D and higher

struct Fenwick2D {                                            // point add, rectangle sum, 0-indexed half-open
    int n, m; vector<vector<ll>> t;
    Fenwick2D(int n, int m) : n(n), m(m), t(n, vector<ll>(m)) {}
    void add(int x, int y, ll v) { for (int i = x; i < n; i |= i + 1) for (int j = y; j < m; j |= j + 1) t[i][j] += v; }
    ll sum(int x, int y) const { ll s = 0; for (int i = x; i > 0; i &= i - 1) for (int j = y; j > 0; j &= j - 1) s += t[i - 1][j - 1]; return s; }
    ll sum(int x1, int y1, int x2, int y2) const { return sum(x2, y2) - sum(x1, y2) - sum(x2, y1) + sum(x1, y1); }
};

• 2D range add + range sum: four 2D Fenwicks storing $d$, $d\cdot x$, $d\cdot y$, $d\cdot xy$ of the 2D difference array; then $\text{prefix}(X,Y)=(X)(Y)\sum d-Y\sum dx-X\sum dy+\sum dxy$ with the right $\pm 1$ shifts. $O(\log n\log m)$.

Structure	Build	Query	Update	Memory
2D Fenwick	$O(nm)$	$O(\log n\log m)$	$O(\log n\log m)$	$O(nm)$
2D segment tree (rows of column-segment-trees)	$O(nm)$	$O(\log n\log m)$	$O(\log n\log m)$	$O(nm)$
2D segment tree, sparse (nodes allocated on demand)	—	$O({\log }^2)$	$O({\log }^2)$	$O(q{\log }^{2}n)$

No lazy propagation in 2D

Range updates on a 2D segment tree with lazy propagation don’t work in general — a lazy tag on a row node can’t be pushed into its column tree consistently (there’s no single column-tree node to tag). Use the four-Fenwick range-update trick above (sums only), a sqrt decomposition, or offline processing instead.

Proof: Fenwick2D correctness, and the four-Fenwick 2D range formula

Fenwick2D applies the 1D add/sum bit-walk independently in each axis: add(x,y,v) loops i |= i+1 over rows while nesting j |= j+1 over columns, stamping every (row-block, column-block) pair containing $(x,y)$ — by the 1D proof above, the set of row-blocks containing $x$ and the set of column-blocks containing $y$ are each exactly the 1D ancestor chain, so their product is exactly the 2D ancestor set, and sum(x,y) by the symmetric argument sums exactly the 2D blocks tiling $[0,x)\times [0,y)$. The four-corner inclusion–exclusion sum(x2,y2)-sum(x1,y2)-sum(x2,y1)+sum(x1,y1) is the standard 2D prefix-sum rectangle identity. The four-Fenwick range-add/range-sum formula is the 2D analogue of the 1D two-Fenwick proof above: expanding ${\sum }_{i<X,j<Y}{a}_{ij}={\sum }_{i<X,j<Y}{\sum }_{i^{\prime }\le i,j^{\prime }\le j}{d}_{i^{\prime }{j}^{\prime }}$ and swapping summation order, each $d_{i^{\prime }{j}^{\prime }}$ ($i^{\prime }<X,j^{\prime }<Y$) is counted $(X-i^{\prime })(Y-j^{\prime })$ times, which expands to $XY-Y{i}^{\prime }-X{j}^{\prime }+i^{\prime }{j}^{\prime }$ — exactly the four terms tracked by $\sum d$, $\sum i^{\prime }d$, $\sum j^{\prime }d$, $\sum i^{\prime }{j}^{\prime }d$ respectively. $■$

• $d$ dimensions with compile-time sizes: a recursive template FenwickND<T, N, Ns...> holding N+1 lower-dimensional Fenwicks; $O({\log }^d)$ per operation and $\prod N_i$ memory.
• Everything known offline, no updates: compress both coordinates to $[0,q)$ and use a dense 2D structure directly — the simplest option when it applies.
• Large coordinates, offline: sort points and queries by $x$, sweep with a 1D Fenwick over compressed $y$ (Offline 2D Queries); $O((n+q)\log n)$ time, $O(n)$ memory — usually the right answer whenever queries can be sorted.
• Large coordinates, online, point updates: a Fenwick of sorted vectors, each with its own small Fenwick (compress per node, offline insertion of the set of $y$ per node), $O({\log }^{2}n)$ per operation with $O(n\log n)$ memory. Or a Fenwick of order-statistic trees.
• Online rectangle queries, no updates: a persistent segment tree where version $i$ contains all points with $x\le i$; a rectangle query is the difference of two versions, $O(\log n)$ per query, $O(n\log n)$ memory.
• Online, with insertions: a k-d tree, $O(\sqrt{n})$ per rectangle query, $O(n)$ memory.

On trees

• Subtree sum with point updates: Euler tour turns subtrees into ranges $[ti{n}_v,tou{t}_v)$.
• Path sum from the root with point updates: add $+v$ at $ti{n}_u$ and $-v$ at $tou{t}_u$; the root-to-$x$ sum is a prefix sum up to $ti{n}_x$. The $u$–$v$ path is $f(u)+f(v)-2f(\text{lca})+a_{\text{lca}}$.
• Path add, point query: add at both endpoints and subtract at the LCA and its parent; the value of $x$ is the subtree sum of $x$.

Proof: the tree-on-Fenwick formulas

Subtree-as-range: $v$‘s subtree is exactly the set of vertices visited between $v$‘s entry and exit in a DFS Euler tour (every descendant is entered after $v$ and exited before $v$‘s own exit, and nothing else is), so a Fenwick over tour positions answers subtree-sum as a range-sum query. Root-to-$x$ via stamping $ti{n}_u/tou{t}_u$: stamping $+v$ at $ti{n}_u$ and $-v$ at $tou{t}_u$ makes the Fenwick’s prefix sum at position $ti{n}_x$ equal ${\sum }_u{v}_u\cdot [ti{n}_u\le ti{n}_x<tou{t}_u]$, and $ti{n}_u\le ti{n}_x<tou{t}_u$ holds exactly when $x$ is in $u$‘s subtree, i.e. $u$ is an ancestor of $x$ (or $x$ itself) — so the prefix sum at $ti{n}_x$ is exactly $\sum$ of values over all ancestors of $x$ including $x$, the root-to-$x$ sum. The $u$-$v$ path formula and its proof are identical to Prefix Sums and Difference Arrays’s tree path-sum proof, with $s_v$ there equal to $f(v)$ here. Path add, point query is the Euler-tour transplant of the same note’s tree-difference-array proof: stamping $u,v$ with $+x$ and lca, parent(lca) with $-x$ makes the subtree-sum (now a Fenwick range-sum over $[ti{n}_w,tou{t}_w)$) at $w$ equal $x$ exactly for $w$ on the path and $0$ otherwise, by the identical ancestor-counting argument. $■$

Notes

• Use the 1-indexed variant (i += i & -i) if you prefer; the 0-indexed i |= i + 1 / r &= r - 1 form avoids off-by-one shifts with half-open ranges.
• Fenwick over values replaces std::set for rank queries and is 5-10x faster.
• XOR Fenwick: += becomes ^=, and range XOR is sum(r) ^ sum(l).
• Persistence: querying old versions of a Fenwick is awkward (each add touches $O(\log n)$ scattered nodes, so naive path-copying doesn’t save anything) — reach for a persistent segment tree instead whenever historical queries are needed.