Prefix Sums and Difference Arrays

TL;DR: A prefix-sum array P where P[i] is the sum of the first i elements answers any range sum [l, r) as P[r] - P[l] in O(1) after an O(n) precompute. Pair prefix sums with a hash map of seen sums to count subarrays whose total equals k (or whose sum is divisible by k, by keying on the residue). The difference array is the inverse: to add a value over a range, bump two positions, and a single prefix-sum pass at the end materializes all the updates, turning many range updates into O(1) each.

Prefix sums: range queries in O(1)

Define P[0] = 0 and P[i] = P[i-1] + nums[i-1]. Then the sum of nums[l..r-1] is P[r] - P[l]. One O(n) pass builds P, and every subsequent range query is a single subtraction.

def build_prefix(nums):
    P = [0] * (len(nums) + 1)
    for i, x in enumerate(nums):
        P[i + 1] = P[i] + x
    return P                            # range [l, r) sum = P[r] - P[l]

The win shows up when you have many queries: q queries naively cost O(q * n), but with a prefix array it is O(n + q). This generalizes to 2D (an integral image, where each cell stores the sum of the rectangle above-left, answering any submatrix sum in O(1) with inclusion-exclusion).

Prefix sums plus a hash map

The real interview workhorse is counting subarrays with a given property. A subarray [l, r) sums to k exactly when P[r] - P[l] = k, that is P[l] = P[r] - k. So as you sweep r, you ask how many earlier prefixes equal P[r] - k. A hash map of prefix-sum frequencies answers that in O(1) per step.

def subarrays_sum_k(nums, k):
    count = 0
    running = 0
    seen = {0: 1}                       # one empty prefix with sum 0
    for x in nums:
        running += x
        count += seen.get(running - k, 0)   # earlier prefixes that close a k-sum here
        seen[running] = seen.get(running, 0) + 1
    return count

For "subarray sum divisible by k," key on the residue instead. Two prefixes with the same running % k bound a subarray whose sum is a multiple of k, because their difference is divisible by k.

def subarrays_div_by_k(nums, k):
    count = 0
    running = 0
    seen = {0: 1}
    for x in nums:
        running = (running + x) % k     # Python % is non-negative for positive k
        count += seen.get(running, 0)   # any earlier prefix with the same residue
        seen[running] = seen.get(running, 0) + 1
    return count

In other languages guard the residue with ((running % k) + k) % k so negatives map correctly. Both run in O(n) time and O(min(n, k)) space.

Difference arrays: range updates in O(1)

Flip the relationship. If you must add v to every element in [l, r] many times, doing it directly is O(range) per update. Instead keep a difference array D where D[i] = nums[i] - nums[i-1]. Adding v over [l, r] is two edits: D[l] += v and D[r+1] -= v. After all updates, a single prefix sum over D reconstructs the final array.

def apply_range_updates(n, updates):    # updates: list of (l, r, v)
    D = [0] * (n + 1)
    for l, r, v in updates:
        D[l] += v
        D[r + 1] -= v                   # cancel the bump past the range end
    out = [0] * n
    run = 0
    for i in range(n):
        run += D[i]                     # prefix sum turns diffs back into values
        out[i] = run
    return out

This is the standard trick behind problems like the airplane-booking / car-pooling family and any "apply m range increments, then read the array."

Why interviewers probe this

Prefix sums are the first thing a strong candidate reaches for the moment they see repeated range queries, and the prefix-sum-plus-hash-map pattern for subarray counting is one of the most reused tricks in the medium tier. The probe is whether you spot that "subarray sum equals k" is a complement lookup (P[l] = P[r] - k) rather than a sliding window, which matters because the array can contain negatives and a window would break. The difference-array follow-up tests the inverse insight: that a range update and a range query are duals, and you pick the structure based on which operation is frequent. Expect "what if the values can be negative?" (windows break, prefix-plus-map still works) and "what if updates and queries interleave?" (now you need a Fenwick or segment tree, and saying so is the right answer).

Common misconceptions

• "Use a sliding window for subarray-sum-equals-k." A window assumes monotonic growth, which fails with negative numbers; the prefix-sum-plus-hash-map approach handles negatives.
• "The difference array needs a final loop per query." Updates are O(1); you reconstruct the whole array exactly once at the end, not per update.
• "Prefix sums handle updates too." A plain prefix array is rebuilt in O(n) after any single update; if updates and queries interleave, you need a Fenwick or segment tree.
• "Residues can be negative." In languages where % follows the sign of the dividend, normalize with ((x % k) + k) % k before using it as a key.

Key takeaways

• Build a prefix-sum array once in O(n) and answer any range sum as P[r] - P[l] in O(1).
• Count subarrays summing to k with a hash map of prefix sums: for each P[r], look up P[r] - k; this works with negatives where a window does not.
• For divisibility, key the hash map on running % k; equal residues bound a subarray whose sum is a multiple of k.
• A difference array makes range updates O(1) by editing two endpoints; one prefix-sum pass reconstructs the final array.