Card 08/ 08
Recap: Prefix Sums
Totals before each position, p[j + 1] − p[i] for a range, a map of totals for exact runs, and a remainder that is never negative.
A prefix sum array p holds n + 1 running totals, with p[0] = 0 and p[i] the sum of the first i elements, so the sum of indices i to j inclusive is p[j + 1] − p[i]. Building it is O(n), and every read after is O(1). The same idea answers four kinds of question:
| Question | What to store | Formula | Cost |
|---|---|---|---|
| Many range sums over an unchanging array | The prefix array | p[j + 1] − p[i] | O(n) to build, O(1) per range |
| How many runs total exactly k | A map from each total seen to its count, seeded with {0: 1} | Add the count of total − k | O(n) time, O(n) space |
| How many runs total a multiple of k | A map from each remainder to its count | ((s % k) + k) % k as the key | O(n) time, O(k) space |
| How many ranges cover each position | A difference array: +1 at a, −1 at b + 1 | The running total of the marks | O(c + n) for c ranges |
Three slips undo it. Reading a range as p[j] − p[i] drops its last element. A remainder from Java's or TypeScript's % can be negative, so two totals that should match do not. A Java total past 2³¹ − 1 overflows an int, so totals are stored as long. Prefix sums work on negative values, which is why they count exact runs where a sliding window cannot.
← → move through sections and cards