Prefix
Prefix Techniques
Prefix sums, suffix sums, difference arrays, prefix XOR and 2D prefix sums.
Prefix Sum
▶ viz
Precompute P[i] = a[0] + … + a[i-1] once so that any subarray sum a[l..r] is P[r+1] − P[l] in O(1).
O(n) · O(n) space
Suffix Sum
▶ viz
Precompute S[i] = a[i] + … + a[n-1] by scanning right to left, so questions about "everything after index i" are answered in O(1) — usually paired with a prefix sum.
O(n) · O(n) space
Difference Array
▶ viz
Apply many range increments in O(1) each by writing +v at l and −v at r+1, then recover the final array with a single prefix-sum pass.
O(n + m) · O(n) space
Prefix XOR
▶ viz
Precompute X[i] = a[0] ^ … ^ a[i-1] so any range XOR a[l..r] is X[r+1] ^ X[l] — XOR is its own inverse, so no subtraction is needed.
O(n + q) · O(n) space
2D Prefix Sum
▶ viz
Precompute P[i][j] = sum of the rectangle from (0,0) to (i-1,j-1) so any submatrix sum is four lookups via inclusion–exclusion.
O(R·C + q) · O(R·C) space