前言
作者本以为前缀和非常简单，但是近来遇到了很多题。发现存在非常多的应用，写这篇博客用于作者本人归纳应用以及供读者学习和总结。
区间和的静态询问
对于前缀和数组 ，这个应用就非常的常见且普遍。主要是用于优化区间和的静态询问。
#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;
}
区间子段中 0 出现的次数
对于这个应用是非常的经典的，主要目的就是求连续的子段中0出现了多少次 主要是思想就是利用前缀和的值的变化 ，即对前$i$个元素求和， 如果出现 $sum_l == sum_r 且 l < r$ , 那么 区间$[l + 1 , r]$ 为 0。
注意： 整段数组为0的情况 , 这个情况需要注意一下。
下面给出$O(nlogn)$ 做法
#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; // 注意整个序列为 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;
}
这是map 红黑树的做法 ，利用树形结构来做到$O(logn)$的查询 ， 明显我们不需要修改，只需要插入和查询。我们在之前可能学习过一个数据结构，主要支持查询和插入 。哈希表 , 通过hash到一个位置插入 ， 如果有冲突可能是使用拉链法或者是开放寻址法。我们可以直接使用$STL$自带的$std::unordered_map$
对于unordered_map 不熟悉的点这里
下面给出$O(n)$做法：
注意： 使用优化的hash算法
#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(); // 时间戳
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>
求连续子段中x出现的次数
对于这个问题，我们可以直接转化成连续子段中0出现次数，或者在这个基础上改进一下即可。
mp[A[i] + x] // 是否出现过
最大子段和
这种应用是结合动态规划的思想完成的应用，用于求最大子段和。
核心思想就是如果当前的子段和小于0, 那么必然不能对后面的子段产生正增益， 所以需要抛弃。 我们只需要在这些子段中求出一个最大值即可。 为什么要在众多子段和中取最大，而不是最后一个子段的和就是最大的呢？ 因为做到后面就一定要选后面的，如果不选后面的，肯定都没有做完，肯定是不能确定，最大子段和的。 可能最大子段和在前面，而不是后面。
例如:
1 2 3 -4 -5
参考代码:
#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 一定取的足够小 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;
}
题目：
最大子段和
Problem - A - Codeforces
环形最大子段和
考虑破环为链即可 ，将序列展成两倍长度，做一遍即可。 对于破环为链不熟悉的，请自查一下。
#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 一定取的足够小 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;
}
这是一个从 https://juejin.cn/post/7368777511952957466 下的原始话题分离的讨论话题