Prefix Sums and Difference Arrays

The two cheapest range techniques, and the first things to try. Full detail in Prefix Sum and Difference Array; this page is the decision guide.

The duality

	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)

They are inverse transforms of each other: prefix-summing a difference array recovers the original.

The four combinations

Updates	Queries	Structure	Cost
none	range sum	prefix sum	$O(1)$ per query
range add	read everything at the end	difference array	$O(1)$ per update
point	range sum	BIT	$O(\log n)$
range add	point query	BIT over the difference array	$O(\log n)$
range add	range sum	two BITs	$O(\log n)$
range assign / min / max	anything	lazy segment tree	$O(\log n)$

Range update, range query with two BITs

For a range add of $x$ on $[l,r]$ and range-sum queries:

$\text{prefix}(i)=({\sum }_{j\le i}{B}_1[j])\cdot i-{\sum }_{j\le i}{B}_2[j]$

void rangeAdd(int l, int r, long long x) {
    b1.add(l, x);        b1.add(r + 1, -x);
    b2.add(l, x * (l-1)); b2.add(r + 1, -x * r);
}
long long prefix(int i) { return b1.sum(i) * i - b2.sum(i); }
long long rangeSum(int l, int r) { return prefix(r) - prefix(l - 1); }

Shorter and faster than a lazy segment tree for this specific pair of operations, and worth having in a template file.

Prefix tricks worth knowing

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”
2D prefix sums	submatrix sums, inclusion-exclusion
Prefix sums on a tree	root-to-node sums; combine with LCA for path sums

The pair-counting pattern

Nearly every “count subarrays with property $P$” problem becomes “count pairs of prefix values with property $Q$“:

Question	Pairs of prefixes
Subarrays with sum $=k$	$\mathrm{pref}[r]-\mathrm{pref}[l]=k$ → hash map
Subarrays with sum divisible by $k$	equal residues → hash map
Subarrays with XOR $=k$	$\mathrm{pref}[r]\oplus \mathrm{pref}[l]=k$ → hash map or trie
Subarrays with equal 0s and 1s	map 0 to $-1$, look for sum 0
Subarrays with sum in $[L,R]$	count prefixes in a range → BIT
Number of inversions	count smaller prefixes → BIT

Recognising this converts an $O(n^2)$ enumeration into $O(n)$ or $O(n\log n)$.

Tree prefix sums

Root the tree and store distToRoot[v]. Then:

$\text{path sum}(u,v)=d_u+d_v-2d_{\mathrm{lca}},$

and for vertex values, add back the LCA’s own value. Combined with the tree difference array for updates, this handles a large class of tree problems without HLD.

Before reaching for a segment tree

Ask, in order:

1. Are there no updates? → prefix sum or sparse table.
2. Do all updates precede all queries? → difference array.
3. Are the queries offline? → sort and sweep with a BIT.
4. Is the update a point and the query a prefix? → BIT.
5. Only then → segment tree.

Each step down this list roughly doubles the code length. Most problems stop at step 3.

See also: Prefix Sum · Difference Array · Offline Query Processing