前綴和一維前綴和問題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的位置的刪掉 } //輸出答案}
寫到這里，取尺法和前綴和，最常用的用法就全部介紹完拉~
