Optional challenge: find matching prefixes
Count target-sum subarrays and verify every summary against its meaning.
Turn a range equation into a lookup
A nonempty subarray [l, r] sums to K exactly when P[r] − P[l − 1] = K, so the earlier prefix must equal P[r] − K. Scan right endpoints and count how many earlier prefix totals equal the needed value.
Use a frequency map because prefix totals may be negative, large, and repeated. A set would only remember existence and would undercount multiple valid earlier boundaries. Initialize seen[0] = 1 for the empty prefix so subarrays starting at position 1 are included.
Query before inserting the current boundary
Look up prefix − target before incrementing seen[prefix]. For target zero, inserting first would let the current prefix match itself and incorrectly count an empty subarray. Before each step, seen must contain exactly the earlier prefix boundaries.
With std::map, time is O(n log(n + 1)) apart from constant setup and storage is O(n). The answer may reach n(n + 1)/2, so store the running prefix, frequencies, target arithmetic, and answer as long long.
// Complete C++23 program. Input: n target, then n signed values.
// n <= 200000; |value|,|target| <= 1e9. Counts nonempty subarrays.
#include <iostream>
#include <map>
int main() {
int n;
long long target;
std::cin >> n >> target;
std::map<long long, long long> seen;
seen[0] = 1;
long long prefix = 0, answer = 0;
for (int i = 0; i < n; ++i) {
long long value;
std::cin >> value;
prefix += value;
auto it = seen.find(prefix - target);
if (it != seen.end()) answer += it->second;
++seen[prefix];
}
std::cout << answer << '\n';
}Verify meanings and reset every case
Check P[0] = 0, P[i] − P[i − 1] = a[i], and P[n] equals the direct total. Frequency counts should be nonnegative and sum to the number of observations. An update-only difference table including the sentinel has marker sum zero; this says nothing about the sum of the real final values.
Create local zero-initialized summaries inside solve() for independent cases. A full frequency-domain reset costs O(U + 1) per case, even if few observations arrive. For range methods, compare with direct scans on tiny arrays, updates, and rectangles. Include singleton intervals, both boundaries, zero updates, negative values, exact cancellation, and nonsquare grids.
Turn the tools into a method
Before coding, state what one entry means, how it is built, how an answer follows, and why its index and numeric bounds are safe. A frequency array uses values as indices; a position prefix uses prefix lengths; a difference array stores changes. Similar-looking loops do not make their meanings interchangeable.
When a test fails, keep a smallest counterexample and inspect the state. For single-element sums returning zero, check l − 1. For last-position update crashes, check n + 2 allocation. For overlaps disappearing, check +=. A simple correct reference solution is useful evidence when validating a faster one.
For [0, 0, 0] and target 0, how many nonempty subarrays have the target sum?
Turn the idea into code
For [1, 2, −1, 1, 2] and target 3, list all matching subarrays using one-based inclusive endpoints. Explain the role of seen[0] = 1.
Give me a hint
The padded prefixes are [0, 1, 3, 2, 3, 5]. For each right prefix, look for an earlier value three smaller.
Show the explained solution
The matching ranges are [1,2], [1,4], and [4,5]. The initial zero prefix supplies the left boundary before position 1 for the first two matches. Looking up before insertion keeps all counted subarrays nonempty.
Your notes
Mark complete when you can explain it yourself.