Präfixsummen
Berechne laufende Summen vor, sodass jede Bereichssummen-Abfrage O(1) wird - der Trick hinter Teilsummen- und Gleichgewichtsproblemen.
Deutsche Übersetzung in Arbeit
Diese Lektion ist noch nicht ins Deutsche übersetzt und wird daher auf Englisch angezeigt. Der Rest der Seite ist vollständig lokalisiert.
Auf dieser Seite
Some problems ask the sum of a range over and over: "sum from index i to j," many times, for different i and j. Computing each range by looping is O(n) per query. Prefix sums precompute once so every range-sum query afterward is O(1) - a small idea with outsized leverage.
Precompute the running totals
Build an array prefix where prefix[i] is the sum of the first i elements. Then the sum of any
range [i, j) is just a subtraction:
// prefix[i] = a[0] + a[1] + ... + a[i-1]
int[] prefix = new int[a.length + 1];
for (int i = 0; i < a.length; i++)
prefix[i + 1] = prefix[i] + a[i];
// sum of a[i..j-1] in O(1), no matter how big the range
int rangeSum(int i, int j) {
return prefix[j] - prefix[i];
}One O(n) precomputation, then every range query is a single subtraction. If a problem does many range-sum queries, this collapses an O(n·q) solution to O(n + q).
The real power: subarray-sum problems
Prefix sums shine on "count subarrays that sum to k." The insight: a subarray (i, j] sums to k
exactly when prefix[j] - prefix[i] == k, i.e. prefix[i] == prefix[j] - k. So as you sweep,
you ask a hash map how many earlier prefixes had the value you need:
// number of subarrays summing to k — O(n) with prefix sums + a hash map
int subarraySum(int[] a, int k) {
Map<Integer, Integer> seen = new HashMap<>();
seen.put(0, 1); // empty prefix
int prefix = 0, count = 0;
for (int x : a) {
prefix += x;
count += seen.getOrDefault(prefix - k, 0); // earlier prefixes that complete a k-sum
seen.merge(prefix, 1, Integer::sum);
}
return count;
}This is the two-patterns-combine moment from the catalog: prefix sums + hashing turns an O(n²) double loop into a single O(n) pass. It even works with negative numbers, where a sliding window would fail.
Prefix sums extend to 2D and to products
The same trick generalizes. A 2D prefix-sum matrix answers submatrix-sum queries in O(1). A prefix-product (or prefix-XOR) handles range products and range XORs. Whenever you see repeated range aggregation, ask whether a prefix structure precomputes it.
To know the distance between exit 12 and exit 47, you don't re-measure the road - you read the mile markers and subtract: 47's marker minus 12's. The markers are a one-time survey (the prefix array); after that, any stretch's length is a single subtraction. Prefix sums are mile markers for an array: survey the running totals once, then every range is marker minus marker.
You're given an array and asked to answer q queries, each asking for the sum of a range [i, j]. Naively each query loops the range. Explain how prefix sums change the total complexity from O(n·q) to O(n + q), and what the answer to a single query becomes.
After building a prefix-sum array, what is the cost of answering one range-sum query?
Key takeaways
- Prefix sums precompute running totals so any range sum is prefix[j] - prefix[i] in O(1).
- One O(n) build turns many range queries from O(n*q) into O(n + q).
- Prefix sums + a hash map count subarrays summing to k in O(n), even with negative numbers.
- The pattern generalizes: 2D prefix sums for submatrices, prefix products/XOR for other range aggregations.
- The tell is repeated range aggregation - precompute once, then subtract.