Prefix Sum Pattern — Range Queries, Hashmap Trick, Three Walkthroughs

Prefix sums answer "sum of a range" in constant time after a linear precomputation. That's the shallow version. The deep version is that any question about a sum over a contiguous range becomes a question about the difference of two prefix sums — and that reframe unlocks a whole class of "subarray with sum X" problems via a hashmap trick that turns O(n²) brute force into O(n).

Recognition — when to reach for it

Prefix sums are the right tool when all three of these hold:

1. Your input is a linear sequence — usually an array — and the question involves contiguous subarrays.
2. The question can be phrased in terms of sums over a range, or in terms of a cumulative quantity (running count, running XOR, running product with tolerance).
3. The naïve solution recomputes the range sum for each candidate range, giving O(n²) or worse.

The two flavours you'll actually meet in interviews:

• Range-sum queries. "Given many (i, j) queries, return the sum of nums[i..j]." LC 303, LC 304 (2D variant).
• Subarray-sum-equals-k queries. "How many subarrays have sum equal to k?" — or divisible by k, or at most k. LC 560, LC 974, LC 523.

The first uses just the prefix array. The second uses the prefix array plus a hashmap — the trick that promotes prefix sums from "obvious optimisation" to real technique.

Mental model — a running total, then differences

Define P[i] = sum of nums[0..i-1]. That is, P[0] = 0, P[1] = nums[0], P[2] = nums[0] + nums[1], and so on. P has n + 1 entries.

Now the sum of any range nums[i..j] (inclusive) equals P[j + 1] - P[i]. Precompute P once in O(n); every subsequent range-sum query is O(1) subtraction.

That's the elementary technique. The interesting move is asking:

Given a target sum k, how many contiguous subarrays sum to exactly k?

Each subarray nums[i..j] sums to P[j + 1] - P[i]. Setting that equal to k: P[j + 1] - P[i] = k, or equivalently P[i] = P[j + 1] - k. So for each right endpoint j + 1, we want to count the number of prior prefix sums equal to P[j + 1] - k. A hashmap of {prefix_sum: count_of_indices_with_that_sum} gives us that count in O(1) per right endpoint — total O(n).

That's the whole trick. Every "sum equals / divisible / at most k" subarray problem is a variation.

The two templates

Range-sum queries

class NumArray:
    def __init__(self, nums: list[int]):
        self.prefix = [0] * (len(nums) + 1)
        for i, x in enumerate(nums):
            self.prefix[i + 1] = self.prefix[i] + x

    def sumRange(self, i: int, j: int) -> int:
        return self.prefix[j + 1] - self.prefix[i]

Construction O(n), each query O(1). Space O(n).

Subarray-sum-equals-k (hashmap variant)

def subarraySum(nums: list[int], k: int) -> int:
    seen = {0: 1}                # empty prefix: sum 0 has been "seen" once
    prefix = 0
    count = 0
    for x in nums:
        prefix += x
        if prefix - k in seen:
            count += seen[prefix - k]
        seen[prefix] = seen.get(prefix, 0) + 1
    return count

O(n) time, O(n) space. The seen[0] = 1 initialisation handles the edge case where a prefix from index 0 sums to exactly k — treating the empty prefix as an implicit starting point.

Three flavours worth naming

• Sum equals k. The template above. LC 560.
• Sum divisible by k. Replace the hashmap key with prefix % k. Two prefixes with the same modulo give a subarray whose sum is divisible by k. LC 974, LC 523.
• Longest / shortest / count subarray with sum condition. Add extra bookkeeping — first index for a given prefix (for longest), most-recent index (for shortest). LC 525 (longest with equal 0s and 1s, treating 0 as −1), LC 1546.

Every flavour uses the same "reframe as prefix-sum difference, dictionary-lookup the complementary prefix" pattern.

Walkthrough 1 — LeetCode 303, Range Sum Query — Immutable

Implement a class supporting sumRange(left, right) — sum of nums[left..right] inclusive — on an immutable input.

The elementary template. Precompute once; O(1) per query.

class NumArray:
    def __init__(self, nums: list[int]):
        self.prefix = [0] * (len(nums) + 1)
        for i, x in enumerate(nums):
            self.prefix[i + 1] = self.prefix[i] + x

    def sumRange(self, left: int, right: int) -> int:
        return self.prefix[right + 1] - self.prefix[left]

Trace nums = [-2, 0, 3, -5, 2, -1]:

• prefix = [0, -2, -2, 1, -4, -2, -3]
• sumRange(0, 2) = prefix[3] - prefix[0] = 1 - 0 = 1. (Confirming: -2 + 0 + 3 = 1.) ✓
• sumRange(2, 5) = prefix[6] - prefix[2] = -3 - (-2) = -1. (Confirming: 3 + (-5) + 2 + (-1) = -1.) ✓

The + 1 offset in the prefix array is what makes both left = 0 and the formula symmetric. Without it, you'd need a special case for left = 0 — bug-prone.

Walkthrough 2 — LeetCode 560, Subarray Sum Equals K

Return the number of contiguous subarrays whose sum equals k.

The hashmap trick. For each right endpoint, count the number of prior prefix sums that would complete a k-sum subarray.

def subarraySum(nums: list[int], k: int) -> int:
    seen = {0: 1}
    prefix = 0
    count = 0
    for x in nums:
        prefix += x
        count += seen.get(prefix - k, 0)
        seen[prefix] = seen.get(prefix, 0) + 1
    return count

Trace nums = [1, 1, 1], k = 2:

Result: 2. The two subarrays are nums[0..1] and nums[1..2], both summing to 2.

The key invariant to name in an interview: we look up seen[prefix - k] before recording seen[prefix]. If we swapped the order, a subarray of length 0 would falsely count itself when k = 0. The seen = {0: 1} initialisation is what handles the "starts from index 0" edge case correctly.

Walkthrough 3 — LeetCode 974, Subarray Sums Divisible by K

Return the number of contiguous subarrays whose sum is divisible by k.

Same shape as LC 560 with one twist: the key isn't the prefix sum itself; it's the prefix sum modulo k. Two prefixes with the same modulo give a subarray whose sum is divisible by k.

def subarraysDivByK(nums: list[int], k: int) -> int:
    seen = {0: 1}
    prefix = 0
    count = 0
    for x in nums:
        prefix = (prefix + x) % k
        count += seen.get(prefix, 0)
        seen[prefix] = seen.get(prefix, 0) + 1
    return count

The Python modulo trick: % on negative numbers returns a non-negative result (-7 % 3 == 2, not -1). This is what makes the algorithm handle negative inputs cleanly — the modulo class is always in [0, k) regardless of sign. If you write this in Java or C++, you need ((prefix + x) % k + k) % k to normalise.

Trace nums = [4, 5, 0, -2, -3, 1], k = 5:

• Prefixes: 4, 9, 9, 7, 4, 5; mod 5: 4, 4, 4, 2, 4, 0.
• Each pair of positions with equal mod contributes one subarray divisible by k. Positions with mod-value 4 appear at indices [0, 1, 2, 4] and the implicit "start" at index −1 has mod 0. Positions with mod 0 appear at index 5 and the implicit start.
• The math works out to 7 subarrays. Verify by enumeration.

Common bugs

• Off-by-one in the prefix array. P[0] = 0 and P[i + 1] = P[i] + nums[i] is the safe convention. Some references start P[0] = nums[0] and shift the query formula. Pick one and stick with it inside a function.
• Forgetting seen = {0: 1}. Without it, subarrays that start at index 0 aren't counted correctly. This is the interview-visible bug in LC 560.
• Recording seen[prefix] before checking seen[prefix - k]. For k = 0, this counts each element as a length-0 subarray summing to 0. Always look up first, then record.
• Modulo in the wrong direction. LC 974 needs prefix mod k, not prefix. Storing raw prefixes fails on negative inputs.
• Skipping negative-mod normalisation in non-Python languages. Java's % returns negative results for negative inputs. Normalise with ((x % k) + k) % k.

When prefix sum is not the tool

• The problem is about the minimum / maximum of a range, not the sum. Reach for a monotonic deque (min in a sliding window) or a segment tree. Prefix sums don't extend to non-linear aggregations.
• The array is being mutated between queries. Prefix sums are precomputed and immutable. For mutable arrays with range-sum queries, use a Fenwick tree (BIT) or a segment tree — see the Big-O cheat sheet's specialised-structures row.
• You need subarrays with a product condition on positive integers. Prefix products work in principle but overflow fast. Use two-pointer (sliding-window with product ≤ target).
• The condition is non-linear — "subarray whose max is X", "subarray whose element count of Y is Z". These want frequency counters or monotonic stacks, not prefix sums.

How the Algotrek tutor would prompt you here

When a learner opens a prefix-sum problem on Algotrek, the tutor doesn't reveal the template. It asks three questions:

1. "Is the question about sums over contiguous subarrays?" — This is what the technique answers. If the question is about maxes, mins, or non-contiguous subsets, prefix sums are the wrong tool.
2. "Are you asked for the sum of one specific range, or something over many ranges?" — One range → prefix array alone. Many ranges with a target condition → prefix array plus a hashmap.
3. "What are you looking up in the hashmap?" — For "sum equals k", look up prefix - k. For "sum divisible by k", look up prefix % k. Naming the key is what turns the hashmap trick from mysterious to inevitable.

Answer all three and the template picks itself. Try the Subarray Sum Equals K lesson on Algotrek to see the prompt-then-reveal flow on the flagship prefix-sum-with-hashmap problem.

Where to go next

• LC 304, Range Sum Query 2D — Immutable. The 2D extension of LC 303. P[i][j] = sum of the rectangle from (0, 0) to (i-1, j-1). Range-sum via inclusion-exclusion. A great study in "the technique generalises up a dimension".
• LC 525, Contiguous Array. Longest subarray with equal 0s and 1s. Treat 0 as −1; prefix sums become "balance"; a hashmap of first-seen balance gives longest. The classic "reframe the values before applying the technique" problem.
• LC 523, Continuous Subarray Sum. Prefix mod k with a length-≥-2 constraint. Same shape as LC 974 with a twist.
• LC 1546, Maximum Number of Non-Overlapping Subarrays With Sum Equals Target. LC 560's harder sibling — greedy plus prefix sums.
• LC 363, Max Sum of Rectangle No Larger Than K. Combines prefix sums with a sorted-set search. Boss-level, worth the graduation exercise.

Cross-reference the sliding-window post — both are "contiguous subarray" techniques. Sliding window handles "smallest / longest subarray with a monotone constraint"; prefix sums handle "exact sum / divisibility" and unrestricted subarrays (including negative values, which sliding window can't handle). Cross-reference the hash-map-vs-hash-set post — the hashmap variant here needs the map's key-value shape (prefix → count), so hash set alone wouldn't work.

For the O(n) time and O(n) space claims, see the Big-O cheat sheet.