Prefix Sum

Precompute cumulative sums so that any range sum is answered in $O(1)$.

$\mathrm{pref}[0]=0,\mathrm{pref}[i+1]=\mathrm{pref}[i]+a_i,\mathrm{sum}(l,r)=\mathrm{pref}[r+1]-\mathrm{pref}[l].$

vector<long long> pref(n + 1, 0);
for (int i = 0; i < n; i++) pref[i + 1] = pref[i] + a[i];
auto sum = [&](int l, int r) { return pref[r + 1] - pref[l]; };   // inclusive [l, r]

Use the 1-indexed, size $n+1$ convention. It removes every special case at $l=0$, and the bugs that come with them.

2D prefix sums

$P[i][j]=P[i-1][j]+P[i][j-1]-P[i-1][j-1]+a[i][j]$

vector<vector<long long>> P(n + 1, vector<long long>(m + 1, 0));
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
        P[i][j] = P[i-1][j] + P[i][j-1] - P[i-1][j-1] + a[i-1][j-1];
 
// sum of the rectangle (r1,c1)..(r2,c2), 1-indexed inclusive
auto rect = [&](int r1, int c1, int r2, int c2) {
    return P[r2][c2] - P[r1-1][c2] - P[r2][c1-1] + P[r1-1][c1-1];
};

The four-term formula is inclusion-exclusion; it generalises to $2^d$ terms in $d$ dimensions.

Prefix aggregates other than sum

Operation	Invertible?	Prefix works?
$+$, XOR	yes	✔ range = $\mathrm{pref}[r]\mathrm{op}\mathrm{pref}[l-1{]}^{-1}$
$\times$ (mod a prime, no zeros)	yes	✔ with modular inverses
$\min$, $\max$, $\gcd$	no	✘ — use a sparse table
count of a value	yes	✔ one prefix array per value

XOR prefix is the workhorse for subarray-XOR problems: $\mathrm{xor}(l,r)=\mathrm{pref}[r+1]\oplus \mathrm{pref}[l]$, which turns “count subarrays with XOR $=k$” into “count pairs of prefixes differing by $k$” — a hash map counting problem.

Classic applications

Problem	Technique
Range sum queries, no updates	prefix sum
Count subarrays with sum $=k$	hash map of prefix counts
Count subarrays with sum divisible by $k$	hash map of $\mathrm{pref}\mathrm{mod}k$
Longest subarray with sum $=k$	hash map of first occurrence of each prefix
Count subarrays with XOR $=k$	hash map of prefix XORs
Longest subarray with equal 0s and 1s	map 0 to $-1$, then look for sum 0
Maximum subarray sum	Kadane, or $\max (\mathrm{pref}[r]-{\min }_{l<r}\mathrm{pref}[l])$
Number of subarrays with sum in $[L,R]$	prefix sums + a BIT or merge sort
2D submatrix sums	2D prefix
Maximum sum submatrix	fix the row pair, collapse to 1D, apply Kadane

The “count pairs of prefixes” pattern is worth internalising: almost every “count subarrays with property P” problem becomes “count pairs $(l,r)$ of prefix values satisfying Q”, which a hash map or a BIT answers in near-linear time.

When updates are needed

Updates	Queries	Structure
none	range sum	prefix sum, $O(1)$
range add	point query	difference array, $O(1)$
point update	range sum	Fenwick tree, $O(\log n)$
range add	range sum	two Fenwick trees, or a lazy segment tree
none	range min/max/gcd	sparse table, $O(1)$
any	any associative op	segment tree

Overflow

Prefix sums of $10^5$ values up to $10^9$ reach $10^{14}$ — always long long. This is one of the most common overflow bugs in competitive programming.

See also: Difference Array · Fenwick Tree · Prefix Techniques