Prefix Sum Pattern

When we want to work on a range [l, r] or subarray[l,r] or substring[l,r], many a times we can pre-compute some operation of the array/string one time and efficiently query a response for a given range. If this is what we need to do, we can use prefix-sum pattern.

Precompute cumulative sum so any range sum [L,R] is answered in O(1) instead of O(N).

prefix[i] = arr[0] + arr[1] + ... + arr[i]

sum(L, R) = prefix[R] - prefix[L-1]

Build: O(N) Query: O(1) → This is where PrefixSum shines.

Template code for 1-D prefix Sum:

// One time operation
int[] buildPrefix(int[] arr) {
    int n = arr.length;
    int[] prefix = new int[n + 1];
    for (int i = 0; i < n; i++)
        prefix[i + 1] = prefix[i] + arr[i];
    return prefix;
}

// Query sum of arr[l..r] (0-indexed, inclusive) -> Constant time operation
int query(int[] prefix, int l, int r) {
    return prefix[r + 1] - prefix[l];
}

Variations:

If we need to track cumulative sum from the right side (Suffix) as well, we can first calculate the total sum and maintain a running prefixSum so that at each point:

prefixSum = running prefixSum

suffixSum = totalSum - prefixSum

Problems to practice: