前缀和一维前缀和问题1静态区间求和问题2求是否有子区间之和m等于x问题3n个数选数字之和整除n问题4从两端延伸的问题问题5先区间更新然后再区间查询二维前缀和问题1静态子矩阵求和问题2先子矩阵更新然后再子矩阵查询取尺法问题1处理同一类连续区间问题2一类具有单调性的问题
前缀和
一维前缀和
定义PRe[n]=∑i=1nA[i]
问题1：静态区间求和
给定大小为n的数组(1≤n≤105)，接下来读入n个数字表示A[i](1≤A[i]≤109) 接下来输入Q(1≤Q≤105),然后有Q行，表示Q次查询。 每次查询，输入l,r(1≤l≤r≤n),要求输出sum=A[l]+A[l+1]+A[l+2]+...+A[r−1]+A[r]
思路： 预处理一下前缀和pre，那么每次查询，sum就等于pre[r]−pre[l−1]
问题2：求是否有子区间之和%m等于x
给定大小为n的数组和数字m(1≤n,m≤105)，接下来读入n个数字表示A[i](1≤A[i]≤109) 问是否能找到一个子区间，使得区间内的数字之和%m等于x
思路： 从左往右处理前缀和pre，如果当前处理到了第i个，记录当前的前缀和pre[i]%m为t 那么如果这个位置，是我们要求的子区间的右边界，那么l - 1的位置的前缀和%m的值就应该等于(t−x+m)%m 所以我们一边处理前缀和，一边记录pre[i]%m是否出现了即可。
问题3：n个数，选数字之和整除n
给定大小为n的数组和数字m(1≤n,m≤105)，接下来读入n个数字表示A[i](1≤A[i]≤109) 是否能选出一些数字，使得这些数字之和%n为0
思路： 求前缀和pre，求和的时候顺便%n。如果某一个pre等于0，那么就取前这么多个数字，之和%n就等于0了。 否则，没有pre等于0。 通过问题2，我们可以知道，如果有两个不同位置的pre相同，那么这两个位置中间所夹的区间，之和%n就等于0 又因为有n个pre，但是pre%n的结果只可能是1~n-1这n-1种情况 所以至少有两个pre是相同的。 那么两个相同的pre的位置，中间所夹的区间，就会是满足条件的
问题4：从两端延伸的问题
给定大小为n的数组(1≤n≤105)，接下来读入n个数字表示A[i](1≤A[i]≤109) 接下来输入Q(1≤Q≤105),然后有Q行，表示Q次查询。 每次查询，输入l,r(1≤l≤r≤n),要求输出[l,r]区间外面，所有数字的总的gcd
思路： 可以发现，gcd只可以合并，但是并不能和加法一样，做到逆运算(加法的逆运算就是减法) 但是这个题实际上是除去了[l,r]区间的，那么有效的区间都是从左边或者是右边延伸的 所以可以这样做：
int n, A[MX];int pre[MX], suf[MX];LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a;}void presolve() { pre[0] = 0; for(int i = 1; i <= n; i++) { pre[i] = gcd(pre[i - 1], A[i]); } suf[n + 1] = 0; for(int i = n; i >= 1; i--) { suf[i] = gcd(suf[i + 1], A[i]); }}int query(int l, int r) { return gcd(pre[l - 1], suf[r + 1]);}问题5：先区间更新，然后再区间查询
给定大小为n的数组(1≤n≤105)，刚开始每个位置的值都为0 接下来输入m(1≤m≤105)，接下来m行表示m次修改，每次修改输入l r x,表示区间[l,r]中的数字全部加上x 接下来输入Q(1≤m≤105)，接下来Q行表示Q次查询，每次查询输入l r,要求输出A[l]+A[l+1]+A[l+2]+...+A[r−1]+A[r]
思路： 这个题特别之处在于，并不是一边修改一边查询，而是先修改，然后再是查询，那么就没必要使用复杂的数据结构，直接用前缀和就能搞定了。 创建数组A 对于m次修改，每次直接A[l] += x, A[r + 1] -= x 然后再对A数组求一次前缀和，假如依然保存在A数组里。 此时，A[i]就表示，m次修改以后，第i个位置的值了~ 那么我们现在要区间修改，又回到了问题1，再对A数组做一遍前缀和就行了
二维前缀和
pre[n][m]=∑i=1n∑j=1mA[i][j]
问题1：静态子矩阵求和
给定大小为n*m的矩阵(1≤n,m≤103)，接下来读入n*m个数字表示A[i][j](1≤A[i]≤109) 接下来输入Q(1≤Q≤105),然后有Q行，表示Q次查询。 每次查询，输入x1,y1,x2,y2(1≤x1≤x2≤n,1≤y1≤y2≤m),要求输出子矩阵中的所有数字之和
思路： 按二维前缀和的定义，预处理出pre 对于每次查询，答案就是pre[x2][y2]−pre[x2][y1−1]−pre[x1−1][y2]+pre[x1−1][y1−1] 预处理pre可以这样做
void presolve() { for(int i = 1; i <= n; i++) { LL line = 0; for(int j = 1; j <= m; j++) { line += A[i][j]; pre[i][j] = pre[i - 1][j] + line; } }}问题2：先子矩阵更新，然后再子矩阵查询
给定大小为n*m的矩阵(1≤n,m≤103)，接下来读入n*m个数字表示A[i][j](1≤A[i]≤109) 接下来输入P(1≤P≤105),然后有P行，表示P次修改。 每次修改，输入x1,y1,x2,y2,x(1≤x1≤x2≤n,1≤y1≤y2≤m),那么子矩阵中所有数字会加上x 接下来输入Q(1≤Q≤105)，然后有Q行，表示Q次修改。 每次查询，输入x1,y1,x2,y2(1≤x1≤x2≤n,1≤y1≤y2≤m),要求输出子矩阵中所有数字之和
思路： 感觉写到这里，前缀和的套路大家也应该能明白了。 对于每次修改，我们A[x1][y1]+=d,A[x2+1][y1]−=d,A[x1][y2+1]−=d,A[x2+1][y2+1]+=d 然后对A求二维前缀和，得到每个位置的数字。 再求一次前缀和，保存到A中 然后回到问题1，对于每次查询，答案就是pre[x2][y2]−pre[x2][y1−1]−pre[x1−1][y2]+pre[x1−1][y1−1]
取尺法
又叫两点法(two point)
问题1：处理同一类连续区间
一个长为n(1≤n≤105)的只有0和1的串。 求连续1最长是多少。
思路：这种处理连续区间的方法非常多，也有更简单的，不详细说了
int l, r, ans = 0;for(l = 1; l <= n; l = r + 1) { for(r = l; r + 1 <= n && A[r + 1] == A[l]; r++); if(A[l] == 1) ans = max(ans, r - l + 1);}printf("%d/n", ans);问题2：一类具有单调性的问题
有n(1≤n≤105)个位置放了物品，每个物品有a和b(1≤a,b≤105)。 现在要找到一个子区间，使得这个子区间的a之和小于等于W(1≤W≤109),且b的和最大。 求这个最大值。
这一类问题，如果想用取尺法解决，基本上都有以下的特征： - 能够判断当前状态是否符合题意 - 能维护增加一个，和删除一个 - 左边界不变时，右边界一定是越大越好，直到不符合题意 - 右边界不变时，左边界一定是越小越好，直到不符合题意
一旦满足了这些要求，就能用取尺法了。 这里有一个对于这一类题的模板
void solve() { int l, r = 0; for(l = 1; l <= n; l++) { //check是检查把这个位置加进去，是否还符合题意 while(r + 1 <= n && check(r + 1)) { r++; add(r);//把这个位置的加进去 } //在这个地方更新答案 delete(l);//把l的位置的删掉 } //输出答案}
写到这里，取尺法和前缀和，最常用的用法就全部介绍完拉~
