Prefix Sum

01 / The shared mechanism

Pay O(N) once to build a cumulative table — every range query that follows reduces to a constant-time subtraction. Flip the trick inside-out and you get cheap range updates instead.

01 / The one-sentence essence

Stream the running prefix once — at every step the count of valid subarrays ending here is whatever the hash map already knows about prefix − k.

Problemcount subarrays with sum = kInput[1, 2, 3, -1, 2, 3]k5

prefix0

arr

-1

map

0·1

Stream arr left to right with target k = 5. The hash map starts seeded with { 0: 1 } — that one entry covers subarrays that start at index 0.

step

0 / 19

phase

init

prefix

lookup

found

count

0 / 19

arrk

02 / The pattern signature

# walk arr, maintain hashcount ← 0prefix ← 0map ← { 0: 1 } # empty-prefix seedfor x in arr:prefix ← prefix + x# lookupif (prefix − k) in map:count += map[prefix − k]map[prefix] += 1 # record this prefix for later steps

03 / When to recognize this pattern

"count subarrays with sum = k"

The canonical signal. A subarray sum is the difference of two prefixes, so every valid subarray ending at i corresponds to a prior prefix equal to prefix[i] − k. Lookup, not nested loops.

"subarrays divisible by k"

Same idea, hash on prefix mod k instead of prefix itself. Any additive-mod-k quantity works.

"+1 / −1 prefix"

Re-encode the values (e.g. 0 → −1) so the property you care about becomes "prefix equal". Then the same hash trick counts matches.

"longest / shortest subarray with property P"

Same machinery, but store the first (or earliest) index for each prefix value and take i − map[prefix − k]. Counting becomes indexing.

04 / Common pitfalls

Forgetting the { 0: 1 } seed.

The seed handles subarrays that start at index 0 — i.e. cases where prefix[i] itself equals k. Without it, you silently miss every prefix that already equals the target on its own.

ii.

Recording the prefix before the lookup.

The order is lookup, then record. If you bump map[prefix] first, a subarray of length 0 (with sum 0, when k = 0) counts itself. The map should only contain prefixes from strictly earlier positions when you query.

iii.

Adding 1 instead of the frequency.

count += map[prefix − k] — not count += 1. There can be many earlier prefixes with the same value (especially with negatives or zeros), and each one is a distinct subarray ending at i.

05 / Go practice — on LeetCode

Four problems, ordered by difficulty. No solutions here, by design.

01Subarray Sum Equals K— LC 560medium→02Subarray Sums Divisible by K— LC 974medium→03Contiguous Array— LC 525medium→04Count Number of Nice Subarrays— LC 1248medium→

— / When to use which

1-D linear

Use when you have many range-sum queries on a fixed array.

range-sum · running-total · LC 303

2-D grid

Use for rectangle queries on a matrix — inclusion-exclusion on the corners.

matrix-region · block-sum · LC 304

difference

Flip the direction: many range updates, then a single read of every cell.

range-add · car-pooling · flight-bookings

hash map

Count subarrays whose sum hits a target — prefix + map of seen prefixes.

subarray-sum-k · divisible-by-k · LC 560