前言

也不知道这类题目有没有具体的名字，个人做过的感觉都是前缀和优化+桶再优化。
最早是在蓝桥杯里做过这种题目，但是当时没总结归纳，最近正好做到挺多这类题目，整理一个合集。

特点：

• 题目通常为给一个大小为n的数组，要对所有子数组进行操作。
• 判断哪些子数组符合条件，求出题目所需。

根据特点可以看出，如果用最暴力的写法通常需要三重循环$O(N^3)$，两重循环枚举区间左右端点，一个循环判断区间是否符合条件。通常我们需要把他优化到$O(N)$。

用前缀和优化区间判断，再用桶数组（常用map实现）优化掉一个循环。从而实现$O(N)$。

题目

洛谷P2697 宝石串 入门题

将一种颜色设为1另一种设为-1构造一个新的数组，然后对这个数组做前缀和。那么只要前缀和中的值相等就意味着这段区间两种宝石的数量相等。即sum[r] - sum[l] == 0 说明 [l + 1, r]这是个合法区间。
用桶数组保存第一次出现的数字，如果重复出现了找最大值即可。

#include <iostream>
#include <cstring>
#include <algorithm>
#include<map>

using namespace std;
#define x first
#define y second
typedef long long LL;
typedef pair<int, int> PII;
const int N = 300010;

int main()
{
    string  s;
    cin >> s;
    map<int,int> m;
    int x = 0, ans = 0;
    m[0] = 0;
    for(int i = 1; i <= s.size(); i ++)
    {
        if(s[i - 1] == 'G') x ++;
        else x --;
        if(m.count(x)) ans = max(ans, i - m[x]);
        else m[x] = i;
    }
    cout << ans << endl;
    return 0;
}

注意边界：枚举的区间[l,r],在转化为前缀和之后应该是 sum[r] - sum[l - 1]，所以会初始化m[0] = 0。

洛谷P1627 CQOI2009 中位数

这题其实最开始没什么思路，是在对应到这个算法的时候才想到。
首先要理解：如果某段区间以$x$为中位数，那么这段区间内比$x$小的数字和比x大的数字的个数要相同。根据这个定义来计算符合条件的区间数量，就可以用到之前的方法了。

因为所求的是中位数$m$，所以考虑改变原序列。把大于$m$的数全部变为$-1$，小于$m$的数变为$1$,等于$m$则为$0$。要求覆盖$m$位置的总和为0的区间数量，注意选择的区间，在没遍历到$m$时要统计数量即维护桶$cnt$，遍历到$m$后则统计答案，不再更新桶。

#include<iostream>
#include<map>

using namespace std;

const int N = 1000010;

int a[N];

int main()
{
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i ++)
        cin >> a[i];

    bool flag = 0; // 是否遍历到了m
    int x = 0;
    long long ans = 0;
    map<int,int> cnt;
    cnt[0] ++;
    for(int i = 1; i <= n; i ++)
    {
        if(a[i] < m) x ++;
        else if(a[i] > m) x --;
        else flag = 1;
        if(flag)
            ans += cnt[x];
        if(!flag) cnt[x] ++;
    }

    cout << ans << endl;

}

1230. K倍区间

这题写过题解就直接放链接了。
https://www.acwing.com/file_system/file/content/whole/index/content/1378387/

着重讲一下第二个循环如何优化的：设前缀和数组为sum[i]
用前缀和优化掉一重之后，还剩下两个循环，枚举的是原数组的所有区间。对应到前缀和数组就转化为，在前缀和数组中任意找两个数字，只要他们的差值是k的倍数则为合法答案，即对任意的l,r(l < r)，其中(sum[r] - sum[l]) % k == 0的情况有多少种 。
先把sum所有数字都取模k，则公式中的k就去掉了，再移项得sum[r] == sum[l]，即在前缀和中任取两个数字有多少种情况是相等的。
转化到这里就比较明显了，你甚至可以把每个数字的出现次数都统计出来然后求组合数。
不过我们使用桶数组记录次数，然后依次求出每个数字可以组合的数量即可。

#include<iostream>

using namespace std;

typedef long long LL;

const int N = 100010;

int n, k;
LL s[N];
int cnt[N];

int main()
{
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; i ++)
        scanf("%d", s + i), s[i] += s[i - 1];   //求前缀和

    LL ans = 0;
    cnt[0] = 1; //初始化
    for(int i = 1; i <= n; i ++)
    {
        ans += cnt[s[i] % k];   
        cnt[s[i] % k] ++;   // 前缀和取余k的余数的数量
    }
    cout << ans << endl;
}

ATC D - Pedometer

这题是个环，处理环把数组重复一遍。然后思考怎么枚举区间。
本题求出前缀和数组a[i]后：a[1],a[2],a[3],...,a[n],a[n+1],...,a[n*2]
对于每个点都有n-1个点可以走到，要判断这些距离是不是m的倍数
即1可以走到2，3…n；点2可以走到3，4，5…n，1（从n走到1）以此类推。

在前缀和中对应的区间：

1->2为a[1]-a[0], 1->3为a[2]-a[0]..., 1->n为a[n-1]-a[0]。即a[1~n-1] - a[0]
2->3为a[2] - a[1], 2->4为a[3] - a[1]..., 2->1为a[n] - a[1]。即a[2~n] - a[1]
本题因为给的是边，并且要转化为前缀和，在下标对应上会有差别，需要注意边界。

本题的区间是一个长度为n的滑动窗口，用桶维护这个区间的前缀和数字的数量。然后求出答案即可。

#include<iostream>
#include<vector>
#include<functional>
#include<cmath>
#include<cstring>
#include<map>

using namespace std;

const int N = 500010;
int a[N];
int main()
{
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) 
    {
        cin >> a[i];
        a[i + n] = a[i];
    }
    map<int,int> ma;
    long long ans = 0;
    // ma[0] = 1;
    for(int i = 1; i < n * 2; i ++)
    {
        if(i > n) ma[a[i - n]] --;
        a[i] = (a[i] + a[i - 1]) % m;

        if(i >= n) ans += ma[a[i]];
        ma[a[i]] ++;
    }
    cout << ans << endl;
    return 0;
}

总结

可以看出一些套路

1. 需要用到前缀和做区间查询操作
2. 找到哪些区间需要统计，在哪些区间求答案。
3. 用桶对前缀和做操作。

总的来说通过前缀和优化一层，然后找前缀和判定条件的规律再优化一重。套路大概是这样，掌握套路之后，困难点在于找需要的区间，因为前缀和之后下标会发生偏移，如果题目再给不对应的下标那么写起来会比较复杂。还有某些区间是用来统计的，某些区间用来求答案的，这也是比较复杂的部分。