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." It is also the array-indexed form of the sweep line used on interval problems: +1 where a range opens, -1 where it closes, and the running sum tells you how many are active at each point. Recognizing them as the same move means one of the two always transfers.

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.