Unit 1.8 · about 4 h
95 / 324Prefix sums, difference arrays and prefix plus hash
Precomputation trades linear space for constant queries, and the prefix-plus-hash reduction is the template for turning a range condition into a lookup across counting problems.
- implement
You can now
- Build prefix and difference arrays and answer range queries in \(O(1)\).
- Reduce subarray counting to prefix-frequency lookup with the seed-first rule.
- Choose windows versus prefix-plus-hash from the sign of the numbers.
Covers
- Prefix sums, difference arrays and prefix plus hash
Study, in this order
2 steps
- Prefix sums and difference arraysDSA Handbook - Foundations and linear patterns
The pattern (build \(\mathrm{prefix}[n+1]\) once, query in \(O(1)\)); Worked example LC 303; What it costs (1D and 2D builds and queries, difference-array updates); 2D prefix sums: inclusion-exclusion on four corners; Difference arrays: the inverse direction
- The prefix-sum + hash-map comboDSA Handbook - Foundations and linear patterns
Why sliding window fails on negatives, in one trace (
[1, -1, 1, 1]); The reduction (\(\mathrm{prefix}[l] = \mathrm{prefix}[r+1] - k\)); The pattern with the{0: 1}seed; Worked example LC 560 on[1, 1, 1]with \(k = 2\); When the pattern bends (modulo LC 974, first-seen LC 525)
Focus on
- The prefix array has \(n+1\) entries with \(P[0] = 0\): a range sum is \(P[r+1]-P[l]\), with no special case.
- Counting needs the seed
{0: 1}: subarrays starting at index 0 would otherwise be missed. - Difference arrays mark \(+v\) at \(l\) and \(-v\) at \(r+1\); one prefix pass materializes the array, and a second prefix over it answers queries.
- Python's
%already normalizes negatives for positive \(k\); the((x%k)+k)%kform is for C++ and Java ports.
Reproduce closed-book
[1, 1, 1] with \(k = 2\): seed {0: 1}; running prefixes 1, 2, 3 need -1, 0, 1 with counts 0, 1, 1, totaling 2. Then implement range-add via difference marks plus range-sum queries, differential-tested against naive loops (\(n\) up to 20, up to 10 updates, derandomize) in Python 3.13: expect 1 passed.Traps
- Off-by-one: \(P\) has \(n+1\) entries and the query is \(P[r+1]-P[l]\).
- Missing seed
{0: 1}: every valid prefix starting at index 0 vanishes. - Using a window on possibly-negative inputs; reach for prefix-plus-hash instead.
Practice
LeetCode 303: Range Sum Query - Immutable
Build the \(n+1\) prefix once and answer each sumRange in \(O(1)\). Judge with the Example array [-2, 0, 3, -5, 2, -1].
After submitting, compare against the handbook prefix-sums worked example LC 303.
LeetCode 560: Subarray Sum Equals K
Implement the prefix-frequency reduction with the {0: 1} seed. Judge with the Examples [1, 1, 1] \(k = 2\) giving 2, and [1, 2, 3] \(k = 3\) giving 2.
After submitting, compare your trace against the handbook prefix-sum-hash worked example on [1, 1, 1].
Self-test
-
Derive the 2D range-sum formula.
\(P[i+1][j+1] - P[i][j+1] - P[i+1][j] + P[i][j]\): subtract the top and left rectangles, add back the doubly-subtracted corner. -
Why does the difference marking work?
Telescoping: position x accumulates all marks at indices up to x, exactly the updates covering x. A second prefix over the materialized array answers sums. -
Where does the
{0: 1}seed enter the LC 560 trace?Prefix 2 needs 0, which never appears as a running total. The seed supplies its count of 1. -
Modulo keys with negative running sums in Python?
key = running % kworks directly since Python floors to non-negative for positive \(k\). Ports to C++ or Java need the double-mod form.
Completion criterion
Stop when
Both are accepted, your hand trace totals 2, and you can state the window-versus-prefix choice rule from the sign of the input.
Mark passed, then open 2.1 Only mark this when you can do it without notes.Leads to
- 5.1 Dynamic programming states, transitions and base cases Prefix recurrences become DP states with more structure.
- 2.3 Binary search: intervals, bounds and feasibility predicates Prefix sums plus binary search answer constrained-rectangle queries.
Comes after
- 1.3 Loop invariants, brute-force oracles and differential testsPrefix counting is the next brute-force-oracle pattern.
- 1.5 Hash tables: collisions, load factor, resizing and tombstonesPrefix counting turns hash maps into subarray oracles.
- 1.7 Two pointers and sliding windowsWhen the numbers can be negative, prefix sums replace shrinking windows.
Resources for this unit
- DSA Handbook - Foundations and linear patterns Study Part 0, Part 1, Part 3 and Part 4 in order, plus the Part 5 Linked-list fundamentals chapter. Use the routing-rule pages for arrays versus lists, map choice, stack versus queue, two pointers, sliding windows and prefix methods before seeing solved code.
Also in this section
- AlgoMaster DSA - linear structures slice Attempt Design HashMap, Longest Substring Without Repeating Characters and Sliding Window Maximum cold. Hide tags, state the invariant first, and add randomized operation histories to Design HashMap.
- MIT 6.042J - asymptotics and invariants Use the asymptotics, state-machine invariants and proof-method readings when a cost or correctness argument is weak. Solve only the matching problems.
- Algorithms lecture notes - amortized analysis and hashing Use note 9 Amortized Analysis for the summation, taxation, charging and potential-function proofs, and note 5 Hashing for chaining, universal hashing and open-addressing analysis, when the handbook treatment is too brief for a proof.
- Algorithmica - memory and data layout Read the memory hierarchy, cache and complexity-model chapters, then measure one contiguous-versus-linked and one hash-versus-ordered workload crossover.
- NeetCode - unseen linear problems Use only for two tag-hidden transfer problems after the AlgoMaster slice. Do not start another full roadmap or watch a solution before the attempt is complete.
- Hypothesis documentation - Quickstart and stateful testing Follow Quickstart for
@givenstrategies and the pytest combination, Configuring test settings formax_examplesandderandomize, then Rule-based state machines (rule,precondition,invariant,run_state_machine_as_test) for randomized operation histories againstdictanddequeoracles. - CPython source - list and dict objects Read
list_resizeinObjects/listobject.cfor the growth formula and pattern comment, and theUSABLE_FRACTIONdefinition, perturbation-probing comment and dummy-entry handling inObjects/dictobject.c. Read the cited functions and comments only.