Prefix and suffix techniques

Define prefix[i] as the sum of the first i elements, so prefix[0] = 0 and prefix[i + 1] = prefix[i] + arr[i]. Building it takes one O(n) pass.

The extra leading zero is deliberate: it makes the range formula work for l = 0 without a special case. Change l and r in the animation and watch which two prefix cells are subtracted.

1static int[] buildPrefix(int[] arr) {
2    int[] prefix = new int[arr.length + 1];      // prefix[i] = arr[0] + ... + arr[i-1]
3    for (int i = 0; i < arr.length; i++) {
4        prefix[i + 1] = prefix[i] + arr[i];
5    }
6    return prefix;
7}
8
9static int rangeSum(int[] prefix, int l, int r) {   // sum of arr[l..r]
10    return prefix[r + 1] - prefix[l];
11}

Prefix products work the same way, but division to answer range queries breaks when any value is zero. A classic application avoids division altogether: product of the array except self.

Compute, for each i, the product of everything to its left (a prefix product) and the product of everything to its right (a suffix product). Their product is the answer, in O(n) without dividing.

1static int[] productExceptSelf(int[] nums) {
2    int n = nums.length;
3    int[] out = new int[n];
4    out[0] = 1;
5    for (int i = 1; i < n; i++) out[i] = out[i - 1] * nums[i - 1];   // product of everything left of i
6    int right = 1;
7    for (int i = n - 1; i >= 0; i--) {
8        out[i] *= right;                                               // times everything right of i
9        right *= nums[i];
10    }
11    return out;
12}

XOR is its own inverse: a ^ a = 0. So with px[i + 1] = px[i] ^ arr[i], the XOR of arr[l..r] is px[r + 1] ^ px[l], exactly like the subtraction for sums.

Prefix XOR also counts subarrays whose XOR equals k: a subarray ending at i qualifies when px[i+1] ^ k appeared as an earlier prefix, which a frequency map tracks.

1static int[] buildPrefixXor(int[] arr) {
2    int[] px = new int[arr.length + 1];
3    for (int i = 0; i < arr.length; i++) px[i + 1] = px[i] ^ arr[i];
4    return px;
5}
6
7static int rangeXor(int[] px, int l, int r) {
8    return px[r + 1] ^ px[l];
9}

A suffix sum runs the same idea from the right: suffix[i] is the sum of arr[i..n-1]. It answers “everything from here to the end” directly and pairs with prefix sums for split-point questions.

Example: the pivot index is the first i where the sum to the left equals the sum to the right. Using a total, the right sum is total - left - arr[i], so only a running left sum is needed.

1static int pivotIndex(int[] nums) {
2    int total = 0;
3    for (int x : nums) total += x;
4    int left = 0;
5    for (int i = 0; i < nums.length; i++) {
6        if (left == total - left - nums[i]) return i;   // right sum = total - left - nums[i]
7        left += nums[i];
8    }
9    return -1;
10}

A difference array stores how each element differs from the previous one: diff[i] = arr[i] - arr[i - 1]. Taking the prefix sum of diff rebuilds arr. The two operations are inverses.

That makes a range update cheap. To add v to arr[l..r], change only two entries: diff[l] += v and diff[r + 1] -= v. Enter your own updates in the animation as l, r, v triples.

1static int[] applyUpdates(int n, int[][] updates) {   // each update adds v to arr[l..r]
2    int[] diff = new int[n + 1];
3    for (int[] u : updates) {
4        diff[u[0]] += u[2];                          // start adding v at l
5        diff[u[1] + 1] -= u[2];                      // stop after r
6    }
7    int[] arr = new int[n];
8    int running = 0;
9    for (int i = 0; i < n; i++) {
10        running += diff[i];
11        arr[i] = running;
12    }
13    return arr;
14}

With prefix sums, the sum of arr[l..r] is prefix[r + 1] - prefix[l]. A bigger application: count subarrays whose sum equals k. A subarray (j, i] sums to k when prefix[i] - prefix[j] = k, so for each i count how many earlier prefixes equal prefix[i] - k, using a frequency map. This works with negative numbers, where a sliding window would fail.

1static int subarraySum(int[] nums, int k) {
2    Map<Integer, Integer> seen = new HashMap<>();
3    seen.put(0, 1);                                   // the empty prefix
4    int prefix = 0, count = 0;
5    for (int x : nums) {
6        prefix += x;
7        count += seen.getOrDefault(prefix - k, 0);   // earlier prefixes that leave exactly k
8        seen.merge(prefix, 1, Integer::sum);
9    }
10    return count;
11}

With q range updates on an array of length n, updating every index directly costs O(n · q). With a difference array each update costs O(1), and one O(n) prefix pass at the end rebuilds the array: O(n + q).

This only works when all updates come before all reads. If reads and updates interleave, use a Fenwick tree or a segment tree with lazy propagation (Chapter 29).