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.

What Prefix Sum Actually Does for Range Queries

A prefix sum array transforms a static sequence into a structure that answers range sum queries in O(1) time. Precompute cumulative sums from index 0 to i: prefix[i] = arr[0] + arr[1] + ... + arr[i]. Then sum(L, R) = prefix[R] - prefix[L-1] (with prefix[-1] = 0). That's the entire mechanic — no hidden complexity.

Key property: prefix sums are only correct when the underlying array never changes. Any mutation invalidates all subsequent prefix values. This O(1) query speed comes at the cost of O(n) precomputation and zero tolerance for writes. The array must be immutable for the lifetime of the prefix structure.

Use prefix sums when you have a static array and need many range queries — think analytics dashboards, game leaderboards, or financial reports. In real systems, this pattern appears in materialized views and precomputed aggregations. The moment data updates, you either rebuild (O(n)) or switch to a mutable structure like a Fenwick tree.

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));
    }
}

Product of Array Except Self — Why Prefix Thinking Isn't Always Sums

Here's where most devs get stuck: they see 'prefix' and think 'addition'. But the technique is about _cumulative state_, not just addition. The classic 'Product of Array Except Self' problem proves it. You're asked to return an array where output[i] equals the product of all elements except nums[i]. No division allowed.

The trick? Build a prefix product from the left, then a suffix product from the right. For each index i, output[i] = left_product[i-1] * right_product[i+1]. This is the same pattern as prefix sum, but with multiplication. The WHY: you're accumulating a value that represents 'everything before this point' and 'everything after this point'. That's the prefix mindset.

Most juniors reach for division and get burned when zeros appear. The prefix approach sidesteps that entirely. You don't need two arrays either — compute left products in the output array, then multiply by a running suffix product in one backwards pass. O(n) time, O(1) extra space.

// io.thecodeforge — interview tutorial

def product_except_self(nums):
    n = len(nums)
    result = [1] * n
    
    # left pass: prefix products
    prefix = 1
    for i in range(n):
        result[i] = prefix
        prefix *= nums[i]
    
    # right pass: multiply by suffix
    suffix = 1
    for i in range(n - 1, -1, -1):
        result[i] *= suffix
        suffix *= nums[i]
    
    return result

print(product_except_self([1, 2, 3, 4]))
print(product_except_self([-1, 1, 0, -3, 3]))

Longest Subarray With Sum K — When Prefix Sum Meets Hash Maps

The 'Subarray Sum Equals K' problem counts subarrays. But what if they ask for the _longest_ subarray with sum K? That changes the game. You can't just increment a counter — you need to track positions.

Here's the pattern: compute prefix sums as you iterate. For each prefix sum current_sum, store its first occurrence index in a hash map. When you see current_sum - k in the map, the subarray from that index+1 to the current index has sum K. Track the maximum length.

Why does this work? The prefix sum at index j minus the prefix sum at index i gives the sum of subarray [i+1, j]. If that difference equals K, you've found a match. Storing the _first_ occurrence ensures you get the longest possible span. Storing the _last_ would give the shortest. Pick your battles.

The map starts with {0: -1} — edge case for subarrays starting at index 0. Forget that and you'll miss the subarray [0..j] with sum K. Seen it break production code more than once.

// io.thecodeforge — interview tutorial

def longest_subarray_sum_k(nums, k):
    prefix_sum = 0
    first_occurrence = {0: -1}
    max_len = 0
    
    for i, num in enumerate(nums):
        prefix_sum += num
        if prefix_sum - k in first_occurrence:
            length = i - first_occurrence[prefix_sum - k]
            max_len = max(max_len, length)
        if prefix_sum not in first_occurrence:
            first_occurrence[prefix_sum] = i
    
    return max_len

print(longest_subarray_sum_k([1, -1, 5, -2, 3], 3))
print(longest_subarray_sum_k([-2, -1, 2, 1], 1))

Equilibrium Index — The Minimalist Prefix Application

Let's get back to basics with a problem that looks deceptively simple: find an index where the sum of elements to the left equals the sum to the right. That's the equilibrium index. If your first instinct is 'two pointers' or 'brute force sum on each side', you're not thinking like a senior.

The cleanest solution uses prefix sums to compute total sum in O(n) once, then iterate while maintaining a running left sum. For each index i, the right sum is total_sum - left_sum - nums[i]. Compare. No extra array needed. O(n) time, O(1) space.

This is the kind of problem where overcomplicating will sink you. You don't need cumulative arrays or binary search. Just one pass to get total, another to find equilibrium. The WHY: equilibrium problems test your ability to compute both sides of a partition with a single variable. It's the same muscle as 'split array into two equal sum subarrays'.

Edge cases: multiple equilibrium indices exist? Return the first. No equilibrium? Return -1. Negative numbers? Works fine — sum is sum.

Consider this a warm-up. If you can't solve this in 5 minutes, you're not ready for harder prefix variations.

// io.thecodeforge — interview tutorial

def find_equilibrium(nums):
    total = sum(nums)
    left_sum = 0
    
    for i, num in enumerate(nums):
        right_sum = total - left_sum - num
        if left_sum == right_sum:
            return i
        left_sum += num
    
    return -1

print(find_equilibrium([1, 7, 3, 6, 5, 6]))
print(find_equilibrium([1, 2, 3]))

Filters — Why Your Prefix Sum Interview Pattern Needs Guard Rails

A common trap is applying prefix sums everywhere, even when constraints mismatch. The prefix sum pattern is powerful but has specific filters: it thrives when queries are static (no in-place updates) and range-based (subarray, submatrix). If the problem allows BST or BIT for dynamic ranges, don't force prefix sums. Another filter: memory cost. A 2D prefix sum is O(n*m), which is lethal for large grids with sparse queries — here, a Fenwick tree is cleaner. Also, watch for negative values: prefix sums work fine with negatives, but subarray sum equality problems then require hash maps (not just two-pointer). The real filter is: does the problem reduce to a commutative, associative operation? Sum fits; min/max do not. Use prefix products (log-space) or XOR prefix when operation matches. The filter saves you from overengineering: if the problem says "any order" or "permutation", prefix sums likely don't apply. The rule: if you can't answer "what aggregation over contiguous range", stop and reconsider.

// io.thecodeforge — interview tutorial
# Filter: static array, range sum query
arr = [3, -1, 2, 5]
n = len(arr)
prefix = [0] * (n + 1)
for i in range(n):
    prefix[i + 1] = prefix[i] + arr[i]
# range [l, r] inclusive
def range_sum(l, r):
    return prefix[r + 1] - prefix[l]
print(range_sum(1, 3))  # (-1 + 2 + 5) = 6

Topics — The Three Axes That Define Every Prefix Sum Problem

Prefix sum interview problems decompose into three core topics: range query, hash map extension, and modular arithmetic. Range query is the beginner tier: given a static array, compute sums over intervals in O(1) — e.g., Equilibrium Index or standard subarray queries. The hash map extension is where FAANG lives: Subarray Sum Equals K uses prefix sums with a dictionary to find count or length in O(n). This pattern generalises to longest subarray with sum K, also zero-sum subarrays, and even XOR subarrays. The third topic, modulo prefix sums, transforms the problem into remainder tracking. When a problem asks "subarray sum divisible by K", you store prefix_sum % K in a map. Key edge: negative modulo in Python requires (prefix[i] % K + K) % K to avoid wrong buckets. Topics also hide in disguise — look for "average", "median shift" (using prefix count), or "range product" (convert to log or use prefix product with zero handling). Recognising which axis the problem sits on instantly narrows your solution space from 5 patterns to 1.

// io.thecodeforge — interview tutorial
# Topic: hash map extension for subarray sum
arr = [1, 2, 3, -2, 5]
k = 5
prefix_map = {0: 1}
current = 0
count = 0
for num in arr:
    current += num
    target = current - k
    count += prefix_map.get(target, 0)
    prefix_map[current] = prefix_map.get(current, 0) + 1
print(count)  # subarrays summing to 5