Prefix Sum Arrays and Range Queries

Building the prefix array

prefix[i] holds the sum of the first i elements. Using a length of n+1 and keeping prefix[0] = 0 removes every special case for ranges that start at index 0 — worth doing every time.

int[] buildPrefix(int[] a) {
    int[] prefix = new int[a.length + 1];   // prefix[0] = 0
    for (int i = 0; i < a.length; i++) {
        prefix[i + 1] = prefix[i] + a[i];
    }
    return prefix;
}

// Sum of a[l..r] inclusive, in O(1)
int rangeSum(int[] prefix, int l, int r) {
    return prefix[r + 1] - prefix[l];
}

Building costs O(n) once. After that, q queries cost O(q) instead of O(q x n) — the whole point when a problem hands you thousands of queries over one fixed array.

Prefix sum + hash map

"How many subarrays sum to k?" A subarray (i, j] sums to k exactly when prefix[j] - prefix[i] = k, which rearranges to prefix[i] = prefix[j] - k. So while scanning, ask how many earlier prefixes had the value current - k — a hash map answers that in O(1).

int countSubarrays(int[] a, int k) {
    Map<Integer, Integer> seen = new HashMap<>();
    seen.put(0, 1);              // the empty prefix, so subarrays from index 0 count

    int running = 0, count = 0;
    for (int value : a) {
        running += value;
        count += seen.getOrDefault(running - k, 0);
        seen.merge(running, 1, Integer::sum);
    }
    return count;
}

This version is O(n) time and O(n) space, it handles negative numbers correctly, and it is the standard answer when a sliding window fails for that reason.

Variants worth knowing

• Prefix XOR — same structure with XOR instead of addition; solves "count subarrays with XOR equal to k".
• Prefix count — store a running count of a property (vowels, even numbers) to answer "how many X in this range".
• 2D prefix sums — an (n+1) x (m+1) grid answers any rectangle sum with four lookups and inclusion-exclusion.
• Difference array — the inverse idea: apply many range updates in O(1) each, then a single prefix pass materialises the final array.