Preface
The author originally thought prefix sums were very simple, but has recently encountered many problems that demonstrate they have a wide variety of applications. This blog post is written for the author to organize these use cases, and for readers to learn from and reference.
Static Range Sum Queries
This is the most common and widespread application of prefix sum arrays, primarily used to optimize static range sum queries.
#include #include #include #include#define LL long long
#define PII std::pair<int , int>int main(){
std::ios::sync_with_stdio(0); std::cout.tie(0); std::cin.tie(0); int n; std::vector<ll> A(n + 1); for (int i = 1; i <= n; i ++ ) std::cin >> A[i]; for (int i = 1; i <= n; i ++ ){ A[i] = A[i] + A[i - 1]; std::cout << A[i] << '\n'; } return 0;
}
Example Problems:
Range Sum Query - Luogu
Sum - Luogu
Counting Zero-sum Contiguous Subsegments
This is a very classic application. The core idea uses the property of prefix sum values: we compute the prefix sum of the first i elements, and if we ever have sum_l == sum_r with l < r, then the interval [l + 1, r] has a sum of 0.
Note: You need to pay special attention to the case where the entire array sums to 0.
Below is the O(nlogn) implementation:
#include #include #include #include #includeconst int N = 510 , INF = 0x3f3f3f3f;
#define LL long long
#define PII std::pair<int , int>void solved(){
int n; std::cin >> n; std::vector<ll> A(n + 1); for (int i = 1; i <= n; i ++ ) std::cin >> A[i]; std::map<ll , bool> mp; mp[0] = 1; // Note the case where the entire sequence sums to 0 for (int i = 1; i <= n; i ++ ){ A[i] = A[i] + A[i - 1]; if (mp[A[i]]){ std::cout << "Yes" << '\n'; return ; }else mp[A[i]] = 1; } std::cout << "No" << '\n';}
int main(){
std::ios::sync_with_stdio(0); std::cout.tie(0); std::cin.tie(0); int tc = 1; std::cin >> tc; while (tc --) solved(); return 0;
}
This is an implementation using map (red-black tree), which achieves O(logn) query time using a tree structure. We do not need modification operations here, we only need insertion and query. You have likely already learned of another data structure that natively supports query and insertion: hash tables. Entries are hashed to an index for insertion, and collisions are resolved with chaining or open addressing. We can directly use the built-in std::unordered_map from STL.
If you are not familiar with unordered_map, click here
Below is the O(n) implementation:
Note: This uses an optimized hash algorithm
#include #include #include #include #include #includeconst int N = 510 , INF = 0x3f3f3f3f;
#define LL long long
#define PII std::pair<int , int>struct custom_hash {
static LL splitmix64(LL x) {
x ^= x << 13;
x ^= x >> 7;
x ^= x << 17;
return x;
}
size_t operator () (LL x) const {
static const LL FIXED_RANDOM = std::chrono::steady_clock::now().time_since_epoch().count(); // Timestamp
return splitmix64(x + FIXED_RANDOM);
}
};void solved(){
int n; std::cin >> n; std::vector<ll> A(n + 1); for (int i = 1; i <= n; i ++ ){ std::cin >> A[i]; A[i] *= (i & 1) ? 1 : -1; } std::unordered_map<ll , bool, custom_hash> mp; mp[0] = 1; for (int i = 1; i <= n; i ++ ){ A[i] = A[i] + A[i - 1]; if (mp[A[i]]){ std::cout << "Yes" << '\n'; return ; }else mp[A[i]] = 1; } std::cout << "No" << '\n';}
int main(){
std::ios::sync_with_stdio(0); std::cout.tie(0); std::cin.tie(0); int tc = 1; std::cin >> tc; while (tc --) solved(); return 0;
}
</unordered_map>
Practice Problem: Problem - E - Codeforces
Counting Contiguous Subsegments with Sum x
For this problem, we can directly transform it into the zero-sum subsegment problem, or make a small modification to the above approach to solve it.
mp[A[i] + x] // Whether it has appeared before
Maximum Subarray Sum
This application combines ideas from dynamic programming to solve the maximum subarray sum problem.
The core idea is that if the current subarray sum is less than 0, it cannot provide a positive gain to any future subarray, so we can discard it. We only need to track the maximum value among all candidate subarray sums. Why do we need to take the maximum over all subarrays instead of just returning the final sum? Because the maximum subarray can end at any position when processing left to right, not just the last element. The maximum subarray may be located earlier in the array, not at the end.
Example:
1 2 3 -4 -5
Reference Code:
#include #include #include #include #includeconst int N = 510 , INF = 2e9 + 10;
#define LL long long
#define PII std::pair<int , int>void solved(){
int n; std::cin >> n; std::vector<int> A(n + 1); for (int i = 1; i <= n; i ++ ) std::cin >> A[i]; LL max_sum = -INF , cur_sum = 0; // max_sum must be initialized to a sufficiently small value for (int i = 1; i <= n; i ++ ){ cur_sum += A[i]; max_sum = std::max (max_sum , cur_sum); if (cur_sum < 0) cur_sum = 0; } std::cout << max_sum << '\n';}
int main(){
std::ios::sync_with_stdio(0); std::cout.tie(0); std::cin.tie(0); int tc = 1; // std::cin >> tc; while (tc --) solved(); return 0;
}
Practice Problems:
Maximum Subarray Sum - Luogu
Problem - A - Codeforces
Maximum Circular Subarray Sum
We can simply use the break the cycle into a chain technique: expand the sequence to twice its original length, then run the algorithm once. If you are not familiar with this technique, please look it up on your own.
#include #include #include #includeconst int N = 510 , INF = 2e9 + 10;
#define LL long long
#define PII std::pair<int , int>void solved(){
int n; std::cin >> n; std::vector<int> A(n); for (int i = 0; i < n; i ++ ) std::cin >> A[i]; A.insert(A.end() , A.begin() , A.end()); LL max_sum = -INF , cur_sum = 0; // max_sum must be initialized to a sufficiently small value for (int i = 0; i < int(A.size()); i ++ ){ cur_sum += A[i]; max_sum = std::max (max_sum , cur_sum); if (cur_sum < 0) cur_sum = 0; } std::cout << max_sum << '\n';}
int main(){
std::ios::sync_with_stdio(0); std::cout.tie(0); std::cin.tie(0); int tc = 1; // std::cin >> tc; while (tc --) solved(); return 0;
}
This is a separate discussion topic split from the original thread at https://juejin.cn/post/7368777511952957466