Prefix Sum — Stale Snapshot Breaks Range Queries

Range queries are everywhere in software: analytics dashboards summing sales between two dates, game engines calculating cumulative scores, financial systems aggregating transactions over arbitrary windows. The naive approach — loop over the subarray every time — works fine once, but collapses the moment you have thousands of queries on millions of data points. That's not a theoretical problem; it's the exact bottleneck that gets spotted in production and in whiteboard interviews alike.

Prefix sums solve a deceptively simple problem: given an array, answer 'what is the sum of elements from index i to index j?' in O(1) time, after a single O(n) preprocessing pass. The trick is that any subarray sum can be expressed as the difference between two prefix totals. Once you see that, you also start seeing it everywhere — subarray problems, sliding window variants, 2D grid queries, even problems disguised as hash-map lookups all share the same DNA.

By the end of this article you'll be able to: build a prefix sum array from scratch, apply it to solve classic interview problems like 'subarray sum equals K' and 'range sum query', extend the pattern to 2D matrices, and recognise the three or four disguises this pattern wears in real interviews so you can reach for it confidently the moment you see a range or subarray problem.

Building the Prefix Sum Array — The Foundation Everything Else Rests On

A prefix sum array (also called a cumulative sum array) is built by a single left-to-right pass where each cell stores the sum of all elements from index 0 up to and including that index. That's it. The magic comes from what you can do with it afterward.

If you want the sum of elements from index left to index right (inclusive), the formula is:

rangeSum = prefix[right] - prefix[left - 1]

Why does this work? Because prefix[right] already contains the total of everything from 0 to right. Subtracting prefix[left - 1] strips away everything before your window. What remains is exactly the subarray you care about.

The most common implementation uses a 1-indexed prefix array — meaning you shift the prefix array one position to the right and set prefix[0] = 0. This eliminates the need for an annoying left == 0 edge case check. It's a small discipline shift that pays off every time.

Time complexity for building: O(n). Space: O(n). Each query after that: O(1). That trade-off is almost always worth making when you know multiple queries are coming.

package io.thecodeforge.prefixsum;

public class PrefixSumFoundation {

    /**
     * Builds a 1-indexed prefix sum array.
     * prefix[i] = sum of scores[0..i-1]
     * prefix[0] = 0  (sentinel — eliminates left-edge special cases)
     */
    public static int[] buildPrefixSum(int[] scores) {
        int n = scores.length;
        int[] prefix = new int[n + 1];  
        prefix[0] = 0;

        for (int i = 1; i <= n; i++) {
            prefix[i] = prefix[i - 1] + scores[i - 1];
        }
        return prefix;
    }

    /**
     * Returns the sum of scores[left..right] (0-indexed, inclusive)
     * in O(1) time using the 1-indexed prefix array.
     */
    public static int rangeSum(int[] prefix, int left, int right) {
        // Shift to 1-indexed access: prefix[right+1] - prefix[left]
        return prefix[right + 1] - prefix[left];
    }

    public static void main(String[] args) {
        int[] monthlySales = {120, 340, 210, 480, 95, 310, 275};
        int[] prefix = buildPrefixSum(monthlySales);

        System.out.println("Sales months 1-3: " + rangeSum(prefix, 0, 2));
    }
}

Subarray Sum Equals K — The Classic FAANG Interview Problem

This is the problem that separates candidates who understand prefix sums deeply from those who just memorised the array-building step. The problem: given an array of integers (can include negatives) and a target K, count how many contiguous subarrays have a sum equal to K.

The brute force is O(n²) — try every start and end pair. The prefix sum + hash-map approach is O(n) and it's beautiful.

Here's the insight: a subarray from index i to j sums to K when:

prefix[j] - prefix[i-1] = K ⟹ prefix[i-1] = prefix[j] - K

So as you scan the array left to right, maintaining a running prefix total, you ask: 'how many times have I seen the value currentPrefix - K before?' Each time you've seen it is another valid subarray ending right here. You track the count of each prefix value seen so far in a HashMap.

Negative numbers? No problem — this approach handles them naturally because you're not making any assumptions about monotonicity. That's why it beats a sliding window for this specific problem.

package io.thecodeforge.prefixsum;

import java.util.HashMap;
import java.util.Map;

public class SubarraySumEqualsK {

    /**
     * FAANG-standard implementation using the Prefix Sum + Hashmap pattern.
     * Space Complexity: O(N) | Time Complexity: O(N)
     */
    public static int countSubarraysWithSum(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        // Seed the map with the base case: sum 0 seen once.
        map.put(0, 1);

        int sum = 0;
        int count = 0;

        for (int num : nums) {
            sum += num;
            // If (current_sum - k) was seen before, it means a subarray sums to k.
            if (map.containsKey(sum - k)) {
                count += map.get(sum - k);
            }
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }

        return count;
    }

    public static void main(String[] args) {
        int[] temperatureDeltas = {3, -1, 2, 1, -2, 4, -3, 2};
        int target = 3;
        System.out.println("Result: " + countSubarraysWithSum(temperatureDeltas, target));
    }
}

2D Prefix Sums — Extending the Pattern to Grid Problems

Once you're comfortable with 1D prefix sums, the 2D extension is a natural next step — and it appears in interviews more than you'd expect (image processing, grid-based games, matrix range queries).

The idea is the same: precompute a cumulative sum table where each cell prefix[row][col] stores the sum of ALL elements in the rectangle from (0,0) to (row, col). Then any rectangular subgrid sum can be computed in O(1) using inclusion-exclusion.

Building the table: prefix[r][c] = grid[r][c] + prefix[r-1][c] + prefix[r][c-1] - prefix[r-1][c-1]

The minus corrects for double-counting the overlap in the top-left corner.

Querying a rectangle from (r1, c1) to (r2, c2): sum = prefix[r2][c2] - prefix[r1-1][c2] - prefix[r2][c1-1] + prefix[r1-1][c1-1]

Again, inclusion-exclusion: start with the big rectangle, subtract the two strips above and to the left, then add back the corner you subtracted twice.

Using a 1-indexed table (padding row 0 and column 0 with zeros) makes the formula work uniformly for every cell, including the top-left corner of the grid — no special cases.

package io.thecodeforge.prefixsum;

public class Grid2DPrefixSum {

    private final int[][] prefix;

    /**
     * Constructor builds the 2D prefix table in O(M*N) time.
     */
    public Grid2DPrefixSum(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        prefix = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                prefix[i][j] = grid[i-1][j-1] + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1];
            }
        }
    }

    /**
     * Queries rectangular sum in O(1).
     */
    public int sumRegion(int r1, int c1, int r2, int c2) {
        return prefix[r2 + 1][c2 + 1] - prefix[r1][c2 + 1] - prefix[r2 + 1][c1] + prefix[r1][c1];
    }

    public static void main(String[] args) {
        int[][] grid = {{2, 4, 6}, {5, 3, 8}, {1, 7, 4}};
        Grid2DPrefixSum forgeGrid = new Grid2DPrefixSum(grid);
        System.out.println("Sum of sub-rectangle (0,0) to (1,1): " + forgeGrid.sumRegion(0, 0, 1, 1));
    }
}

Recognising Prefix Sum Disguises — When the Problem Doesn't Say 'Sum'

The hardest prefix sum problems in interviews don't announce themselves. They look like completely different problems until you squint. Knowing the disguises is the real skill.

Disguise 1 — Binary arrays with equal counts: 'Find the longest subarray with equal numbers of 0s and 1s.' Replace every 0 with -1. Now you want the longest subarray summing to 0. That's a prefix sum + HashMap problem: find the earliest index where you've seen the same prefix value before.

Disguise 2 — Equilibrium index: 'Find an index where the sum of elements to the left equals the sum to the right.' Total sum minus prefix up to that point versus prefix up to that point — a single prefix scan solves it in O(n).

Disguise 3 — Product arrays: 'Build an array where each element is the product of all others.' Left prefix products and right suffix products, combined without division.

Disguise 4 — Difference arrays for range updates: When you need to apply an increment to a range [l, r] repeatedly, you record diff[l] += val and diff[r+1] -= val, then take one prefix sum at the end to get the final state. This is the inverse direction of prefix sums and turns O(n) per update into O(1) per update.

The pattern recognition test: does the problem involve subarrays, ranges, or cumulative aggregation? If yes, ask yourself if a prefix precomputation turns repeated work into O(1) lookups.

package io.thecodeforge.prefixsum;

import java.util.HashMap;
import java.util.Map;

public class PrefixSumDisguises {

    /**
     * Disguise 1: Longest Subarray with equal 0s and 1s.
     * Strategy: Map 0 to -1, then find longest subarray with sum 0.
     */
    public static int findMaxLength(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
        int maxlen = 0, count = 0;
        for (int i = 0; i < nums.length; i++) {
            count = count + (nums[i] == 1 ? 1 : -1);
            if (map.containsKey(count)) {
                maxlen = Math.max(maxlen, i - map.get(count));
            } else {
                map.put(count, i);
            }
        }
        return maxlen;
    }

    public static void main(String[] args) {
        int[] binarySignals = {0, 1, 0, 0, 1, 1, 0};
        System.out.println("Longest equal subarray: " + findMaxLength(binarySignals));
    }
}

Prefix Sum with Modulo — Subarray Divisibility Problems

Another powerful disguise: problems that ask for subarrays whose sum is divisible by K. Example: 'Given an array of integers, return the number of subarrays with sum divisible by K.'

This is a direct extension of the hashmap pattern. Instead of tracking sum - K, you track sum % K. The key insight: if prefix[j] % K == prefix[i-1] % K, then the subarray from i to j has sum divisible by K. Because (prefix[j] - prefix[i-1]) % K = 0.

You seed the map with {0: 1} again — the empty prefix has remainder 0. Then for each prefix remainder, you count how many times it has appeared before.

This works for negative numbers too — just take care to normalise the modulo result to a non-negative value in languages where % can be negative (Java, C++). The formula: ((sum % K) + K) % K.

Time: O(n), Space: O(K) in the worst case (only K distinct remainders).

package io.thecodeforge.prefixsum;

import java.util.HashMap;
import java.util.Map;

public class SubarraysDivisibleByK {

    public static int countSubarraysDivisible(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        int sum = 0;
        int count = 0;

        for (int num : nums) {
            sum += num;
            int remainder = ((sum % k) + k) % k; // normalise
            if (map.containsKey(remainder)) {
                count += map.get(remainder);
            }
            map.put(remainder, map.getOrDefault(remainder, 0) + 1);
        }
        return count;
    }

    public static void main(String[] args) {
        int[] stockReturns = {4, 5, -2, 3, 1, -4, 6};
        int k = 5;
        System.out.println("Divisible subarrays: " + countSubarraysDivisible(stockReturns, k));
    }
}