i. Prefix Sums and Difference Arrays

Prefix sums give $O(1)$ range queries on a static array. Difference arrays give $O(1)$ range updates that are read at the end. Each is the inverse transform of the other. Check them before reaching for any tree.

	Prefix sum	Difference array
Fast operation	range query	range update
Slow operation	update ($O(n)$)	query ($O(n)$)
Build	$O(n)$	$O(1)$
Finalise	—	$O(n)$ prefix pass
Best when	all updates precede all queries	all updates precede all queries (the other way round)

Prefix sums

vector<ll> p(n + 1);                          // p[i] = a[0] + ... + a[i-1]
for (int i = 0; i < n; i++) p[i + 1] = p[i] + a[i];
// sum of a[l..r) = p[r] - p[l]

Half-open indices with $p_0=0$ remove every special case at the left edge.

2D: $P_{i,j}=P_{i-1,j}+P_{i,j-1}-P_{i-1,j-1}+a_{i,j}$, and the rectangle sum is the four-term inclusion-exclusion. In $d$ dimensions it takes $2^d$ terms, or one prefix pass per axis (that’s cheaper to build: $O(d\cdot N)$).

What can be prefixed: any group operation (sum, XOR, product of non-zero values mod prime). Min, max and gcd aren’t invertible, so use a sparse table (Sparse Table) or prefix and suffix arrays when you only need to exclude one element:

// gcd of the array without a[i]: pre[i] = gcd(a[0..i)), suf[i] = gcd(a[i..n))
ll without(int i) { return gcd(pre[i], suf[i + 1]); }

The general version of this trick: for any associative operation with an identity, pre[i] aggregates $[0,i)$ and suf[i] aggregates $[i,n)$, and combine(pre[i], suf[i+1]) excludes position $i$ without needing an inverse (unlike subtracting from a prefix sum, which only works when the operation is invertible). Preserve argument order for non-commutative operations, and make sure the sentinel identity values actually match the operation (0 for sum/XOR, 1 for product, a suitably large/small value for min/max). Preprocessing and every exclusion query cost $O(n)$ total.

Trick	Use
prefix XOR	subarray XOR in $O(1)$
prefix counts per value	”how many $v$ in $[l,r]$“
prefix of $[a_i=a_{i-1}]$	“is $[l,r]$ constant”
prefix min/max	not decomposable — use a sparse table
prefix product mod $p$	range product, with modular inverses
prefix sums of the sorted array	”sum of the $k$ smallest”

Counting subarrays = counting pairs of prefixes

A subarray $(l,r]$ is a pair of prefixes, so “count subarrays with property $P$” becomes “count pairs $l<r$ with $Q(p_l,p_r)$”.

Subarrays with	Pairs of prefixes	Tool
sum $=k$	$p_r-p_l=k$	hash map of counts
sum divisible by $k$	$p_r\equiv p_l$	count residues; remember $p_0$
XOR $=k$	$p_r\oplus p_l=k$	hash map; for “XOR $\ge k$” or max XOR use a binary trie
equal number of 0s and 1s	map $0\to -1$, then sum $=0$	hash map, or offset array
sum in $[L,R]$	$L\le p_r-p_l\le R$	BIT over compressed prefixes, or merge sort
longest with sum $=k$	first occurrence of each prefix	map value $\to$ first index
max sum	${\max }_r(p_r-{\min }_{l<r}{p}_l)$	running minimum (Kadane)
max sum with length in $[A,B]$	sliding window minimum of $p_l$	monotonic deque
average $\ge x$	subtract $x$, then sum $\ge 0$	binary search on $x$
median $\ge x$	$\pm 1$ by comparing with $x$, then sum $\ge 0$ (or $>0$)	binary search on $x$
balanced brackets	$+1/-1$, $p$ never below $p_l$ and $p_r=p_l$	sparse table on $p$, or stack

Difference arrays

vector<ll> d(n + 1);
auto add = [&](int l, int r, ll x) { d[l] += x; d[r] -= x; };   // a[l..r) += x
// finalize: prefix-sum d to recover the array

$q$ updates plus one pass is $O(n+q)$. Uses: interval coverage counts (“how many intervals contain each point”), booking problems, sweep events, and grid stamping.

2D: add $x$ to rows $[r_1,r_2)$ and columns $[c_1,c_2)$ with $+x$ at $(r_1,c_1)$, $-x$ at $(r_1,c_2)$ and $(r_2,c_1)$, $+x$ at $(r_2,c_2)$. Finalize with a 2D prefix sum.

Polynomial updates via higher-order differences. Adding a polynomial of degree $k$ over a range needs $k+1$ levels of differences. For an arithmetic progression $a,a+s,\dots ,a+(m-1)s$ on positions $[l,l+m)$, with $D$ the second difference array (prefix-sum twice to finalize):

D[l]         += a;
D[l + 1]     += s - a;
D[l + m]     -= a + m * s;              // a + (m-1)s is the last term
D[l + m + 1] += a + (m - 1) * s;

When in doubt, derive boundary terms by writing the first difference array for a tiny example. For degree $k$ in general, add $\left(\genfrac{}{}{0ex}{}{i-l+k}{k}\right)$-shaped patterns: the $k$-th difference of $\left(\genfrac{}{}{0ex}{}{x}{k}\right)$ is a single 1.

Proof: the second-difference boundary terms

Applying the ordinary (first-order) difference-array trick twice means: $D$ is the difference array of $d$, which is itself the difference array of the target $f$ — so $f$ is recovered by prefix-summing $D$ twice. The target is $f(l+k)=a+ks$ for $k=0,\dots ,m-1$ and $0$ outside $[l,l+m)$. Its first difference is $g(i)=f(i)-f(i-1)$: $g(l)=a$ (jumping from 0), $g(l+\mathrm{1..}l+m-1)=s$ (the constant step of the AP), and $g(l+m)=-(a+(m-1)s)$ (dropping back to 0 after the last term). $D$ is $g$‘s own difference array (the difference-of-differences): $D(l)=g(l)-g(l-1)=a-0=a$; $D(l+1)=g(l+1)-g(l)=s-a$; $D(l+m)=g(l+m)-g(l+m-1)=-(a+(m-1)s)-s=-(a+ms)$; $D(l+m+1)=g(l+m+1)-g(l+m)=0-(-(a+(m-1)s))=a+(m-1)s$ — matching the code exactly. $■$

Tested against direct double prefix-summing, comparing the reconstructed array to the intended AP on random $(l,m,a,s)$.

Interleaved updates and queries: a Fenwick tree over the difference array gives range add with point query. Two Fenwick trees give range add with range sum, using $\text{prefix}(i)=i\cdot {\sum }_{j<i}{d}_j-{\sum }_{j<i}j{d}_j$ (Fenwick Tree).

Proof: the two-Fenwick range-sum formula

With $d$ the difference array, the value at position $i$ is $a_i={\sum }_{j\le i}{d}_j$ (point query from one Fenwick tree over $d$, already correct for range-add/point-query). The prefix sum is ${\sum }_{i\le I}{a}_i={\sum }_{i\le I}{\sum }_{j\le i}{d}_j$; swapping the order of summation, each $d_j$ ($j\le I$) is counted once for every $i$ with $j\le i\le I$, i.e. $(I-j+1)$ times: ${\sum }_{i\le I}{a}_i={\sum }_{j\le I}{d}_j(I-j+1)=(I+1){\sum }_{j\le I}{d}_j-{\sum }_{j\le I}j{d}_j$. Tracking ${\sum }_{j\le I}{d}_j$ and ${\sum }_{j\le I}j{d}_j$ each in their own Fenwick tree (both updated by the same range-add-via-difference-array trick, since $j{d}_j$ at a fixed add position is just a constant multiple of the same $\pm x$ update) gives both sums in $O(\log n)$, and the formula above (with a 0/1-indexing shift matching the code’s $i\cdot \sum -\sum j{d}_j$) recovers the range sum. $■$

On trees

Let $s_v$ be the sum of values on the root-to-$v$ path. Then $\text{path}(u,v)=s_u+s_v-2s_{\text{lca}}+a_{\text{lca}}$ (drop the last term for edge values).

Proof: the tree path-sum formula

The root-to-$v$ path splits as (root-to-lca) + (lca-to-$v$, exclusive of lca), so $s_v=s_{\text{lca}}+\sigma (\text{lca}\to v)$ where $\sigma$ excludes the lca’s own value; symmetrically $s_u=s_{\text{lca}}+\sigma (\text{lca}\to u)$. The $u$-$v$ path is the disjoint union of (lca-to-$u$, excl.) + $\{\text{lca}\}$ + (lca-to-$v$, excl.), so $\text{path}(u,v)=\sigma (\text{lca}\to u)+a_{\text{lca}}+\sigma (\text{lca}\to v)=(s_u-s_{\text{lca}})+a_{\text{lca}}+(s_v-s_{\text{lca}})=s_u+s_v-2s_{\text{lca}}+a_{\text{lca}}$. For edge weights (no vertex value to add back), the three pieces are already disjoint without the $+a_{\text{lca}}$ correction, giving $s_u+s_v-2s_{\text{lca}}$. $■$

Path updates with all reads at the end (the tree difference array): to add $x$ on the path $u$–$v$, do d[u] += x; d[v] += x; d[lca] -= x; d[parent(lca)] -= x;. Then each vertex’s value is the sum of d over its subtree, which one DFS computes. For edge values stored at the child endpoint: d[u] += x; d[v] += x; d[lca] -= 2x.

Proof: the tree difference array

Let $D(w)$ be the value stamped at $w$ (the four $\pm x$ updates), and let $S(w)={\sum }_{w^{\prime }\in \text{subtree}(w)}D(w^{\prime })$ be the DFS subtree sum the algorithm reports for $w$. The claim is $S(w)=x$ for $w$ on the path $u$–$v$ and $S(w)=0$ otherwise. Each stamp at a vertex $z$ contributes to $S(w)$ exactly when $w$ is an ancestor of $z$ (inclusive). So $S(w)=x\cdot [w⪯u]+x\cdot [w⪯v]-x\cdot [w⪯\text{lca}]-x\cdot [w⪯\text{parent(lca)}]$, where $w⪯z$ means $w$ is an ancestor of $z$ or equals $z$. Split on where $w$ sits: (1) $w$ strictly between lca and $u$ (inclusive of $u$, exclusive of lca) — ancestor of $u$ only, none of the other three — $S(w)=x$, matching $w$ being on the path. (2) symmetrically for $v$. (3) $w=\text{lca}$ — ancestor (reflexively) of $u$, $v$, and itself, but not of parent(lca) — $S(w)=x+x-x=x$, correct. (4) $w$ a proper ancestor of lca — ancestor of $u$, $v$, lca, and parent(lca) all at once — $S(w)=x+x-x-x=0$, correctly off the path. (5) $w$ anywhere else (not an ancestor of $u$ or $v$) — all four indicators are 0 — $S(w)=0$. This covers every vertex, proving the claim. The edge-value variant stamps only $u,v$ with $+x$ and lca with $-2x$ (no stamp at parent(lca)): case (3) becomes $S(\text{lca})=x+x-2x=0$ (correct: the lca has no incident edge above the path’s branch point to charge), case (4) becomes $S(w)=x+x-2x=0$ unchanged, and cases (1)/(2) are unaffected, so every edge strictly between lca and $u$ or $v$ still nets $x$ while lca and above net $0$. $■$

Tested by brute force: random trees, random path-update batches, comparing the DFS-subtree-sum reconstruction against directly adding $x$ to every vertex (or edge) on each path.

Subtree updates and queries become ranges after an Euler tour (Euler Tour).

Decision order

1. No updates: prefix sums, or a sparse table for idempotent operations.
2. All updates before all queries: difference array.
3. Queries offline: sort and sweep with a BIT.
4. Point update with prefix query: BIT.
5. Anything else: segment tree, possibly lazy.

Pitfalls

• Prefix sums of $2\cdot 10^5$ values up to $10^9$ reach $2\cdot 10^{14}$: use ll.
• Counting “subarrays with sum divisible by $k$” with negative numbers: normalise residues into $[0,k)$.
• Hash maps keyed by prefix sums are hackable on Codeforces: use a safe hash or sort and compress instead.