算法【前缀和与差分】
差分的应用场景主要是那些对于数组进行一系列操作后，才查询数组中的值，不是边操作边查询。在这种情况下，如果我们每一次操作都是通过遍历数组实现的，速度就会大打折扣。而使用差分我们只需遍历一次数组就可以完成。
一、一维差分
一维差分就是只需对一维数组（初始值为0，否则需要一个初值为0的新数组）进行若干次（一般是1次）求前缀和，就可以得到最终的结果数组。比如，我想在结果数组上的[left, right]区域整体加上3，如果通过遍历数组一个一个的加3，就太慢了。我们可以在数组的left位置加上3，right+1位置减去3，这样只需对每个位置求一次前缀和就可以得到每个位置的值。下面通过一个题目理解一下。
题目一
测试链接：https://leetcode.cn/problems/corporate-flight-bookings/
分析：这个就是一个一维差分，注意题目中是从1开始的。代码如下。
class Solution {
public:vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {vector <int> ans;ans.assign(n+1, 0);for(int i = 0;i < bookings.size();++i){ans[bookings[i][0]-1] += bookings[i][2];ans[bookings[i][1]] -= bookings[i][2];}for(int i = 1;i < n;++i){ans[i] += ans[i-1];}ans.pop_back();return ans;}
};二、等差数列差分
等差数列差分问题描述：一开始1~n范围上的数字都是0。接下来一共有m个操作，每次操作：left~right范围上依次加上首项s、末项e、公差d的数列。最终1~n范围上的每个数字都要正确得到。
等差数列差分的过程：
- 1.每个操作调用set方法
- 2.所有操作完成后在arr上生成两遍前缀和，即调用build方法
- 3.arr里就是最终1~n范围上的每个数字
具体代码如下所示。
void set(int left, int right, int s, int e, int d){arr[left] += s;arr[left + 1] += (d - s);arr[right + 1] -= (d + e);arr[right + 2] += e;
}void build(){for(int i = 1;i <= n;++i){arr[i] += arr[i-1];}for(int i = 1;i <= n;++i){arr[i] += arr[i-1];}
}具体原理和一维差分，类似，这里不做推导。下面通过两个题目来加深理解。
题目二
测试链接：https://www.luogu.com.cn/problem/P4231
分析：这就是一个等差数列差分的模版题。代码如下。
#include <iostream>
using namespace std;
long long arr[10000005] = {0};
int n, m;
int main(void){int l, r, s, e, d;long long sum = 0, max_value = 0;scanf("%d%d", &n, &m);for(int i = 0;i < m;++i){scanf("%d%d%d%d", &l, &r, &s, &e);d = (e - s) / (r - l);arr[l] += s;arr[l + 1] += (d - s);arr[r + 1] -= (d + e);arr[r + 2] += e;}for(int i = 1;i <= n;++i){arr[i] += arr[i-1];}for(int i = 1;i <= n;++i){arr[i] += arr[i-1];sum ^= arr[i];max_value = max_value > arr[i] ? max_value : arr[i];}printf("%lld %lld", sum, max_value);return 0;
}其中，用long long防止溢出。
题目三
测试链接：https://www.luogu.com.cn/problem/P5026
分析：可以发现，每一个落水的人对整体造成的影响就是四个等差数列差分，所以直接套用等差数列差分模板即可。代码如下。
#include <iostream>
#define MAXN 1000005
#define OFFSET 30001
using namespace std;
long long arr[MAXN + OFFSET + OFFSET] = {0};
int n, m;
void set(long long left, long long right, long long s, long long e, long long d)
{arr[left + OFFSET] += s;arr[left + 1 + OFFSET] += (d - s);arr[right + 1 + OFFSET] -= (d + e);arr[right + 2 + OFFSET] += e;
}
void build()
{for (int i = 1; i <= m + OFFSET; ++i){arr[i] += arr[i - 1];}for (int i = 1; i <= m + OFFSET; ++i){arr[i] += arr[i - 1];}
}
int main(void)
{int v, x;scanf("%d%d", &n, &m);for (int i = 0; i < n; ++i){scanf("%d%d", &v, &x);set(x - 3 * v + 1, x - 2 * v, 1, v, 1);set(x - 2 * v + 1, x, v - 1, -v, -1);set(x + 1, x + 2 * v, -v + 1, v, 1);set(x + 2 * v + 1, x + 3 * v - 1, v - 1, 1, -1);}build();int begin = 1 + OFFSET;printf("%lld", arr[begin++]);for (int i = 2; i <= m; ++i){printf(" %lld", arr[begin++]);}return 0;
}其中，OFFSET是用来避免边界判断的一个手段，将所有需要操作的下标全部加上OFFSET，得到一个有效下标。这样就可以避免操作下标为负或者下标超出数组最大下标值的判断，只需要将数组的容量扩展两个OFFSET的大小就可以实现。
三、二维差分
学习二维差分首先得知道二维前缀和。假设我们有一个二维前缀和数组sum，其中sum[i][j]代表左上角(0, 0)到右下角(i, j)这个范围的累加和。sum[i][j] += sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1]。如果要查询左上角(a, b)到右下角(c, d)这个范围的累加和，其值为sum[c][d] - sum[c][b-1] - sum[a-1][d] + sum[a-1][b-1]。这些计算式子可以通过画图很容易推导出来，这里不做详细讲解。实际过程中往往补第0行、第0列来减少很多条件判断，当然也可以不补，根据个人习惯决定。
在二维数组中，如果经历如下操作的过程：
1.批量的做如下的操作，每个操作都有独立的a、b、c、d、v，void add(a, b, c, d, v) : 左上角(a,b)到右下角(c,d)范围上，每个数字+v，怎么快速处理？
2.操作做完后，如何正确得到二维数组中每个位置的值？
这就是二维差分的主要工作，add时候快速处理，最后build得到每个位置的值，修改操作必须集中在一起，不能边修改边查询。
1.add方法实现，比较巧妙。
2.build方法实现，和处理前缀和类似。
3.真实数据用一圈0包裹起来，可以减少很多边界讨论。
下面给出add方法和build方法，代码如下。
void add(int a, int b, int c, int d, int v) {diff[a][b] += v;diff[c + 1][b] -= v;diff[a][d + 1] -= v;diff[c + 1][d + 1] += v;
}void build() {for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {diff[i][j] += diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1];}}
}下面通过几个题目加深对二维差分的理解。
题目四
简要描述：二维前缀和模版。
测试链接：https://leetcode.cn/problems/range-sum-query-2d-immutable/
分析：这就是一个二维前缀和的模版，可以通过对最上一层和最左一层设置成0避免边界判断。代码如下所示。
class NumMatrix {
public:int arr[201][201] = {0};NumMatrix(vector<vector<int>>& matrix) {for(int i = 0;i < matrix.size();++i){for(int j = 0;j < matrix[0].size();++j){arr[i+1][j+1] = matrix[i][j] + arr[i+1][j] + arr[i][j+1] - arr[i][j];}}}int sumRegion(int row1, int col1, int row2, int col2) {return arr[row2+1][col2+1] - arr[row2+1][col1] - arr[row1][col2+1] + arr[row1][col1];}
};/*** Your NumMatrix object will be instantiated and called as such:* NumMatrix* obj = new NumMatrix(matrix);* int param_1 = obj->sumRegion(row1,col1,row2,col2);*/题目五
测试链接：https://leetcode.cn/problems/largest-1-bordered-square/
分析：从每个点枚举边长，得到一个正方形的左上角点和右下角点，判断这个正方形是否边长全是1，可以通过这个正方形区域的累加和减去这个正方形内边长减1的正方形区域的累加和，看看值是否为边长值，是则这个正方形是否边长全是1。代码如下。
class Solution {
public:int sum[101][101] = {0};int largest1BorderedSquare(vector<vector<int>>& grid) {int ans = 1;int m = grid.size();int n = grid[0].size();for(int i = 0;i < m;++i){for(int j = 0;j < n;++j){sum[i+1][j+1] = grid[i][j] + sum[i+1][j] + sum[i][j+1] - sum[i][j];}}if(sum[m][n] == 0){return 0;}for(int i = 1;i <= m;++i){for(int j = 1;j <= n;++j){for(int k = ans+1, c = i+k-1, d=j+k-1;c <= m && d <= n;++k, ++c, ++d){if((sum[c][d] - sum[c][j-1] - sum[i-1][d] + sum[i-1][j-1]) - (sum[c-1][d-1] - sum[c-1][j] - sum[i][d-1] + sum[i][j])== ((k - 1) << 2)){ans = k;}}}}return ans * ans;}
};题目六
简要描述：二维差分模版。
测试链接：https://www.luogu.com.cn/problem/P3397
分析：这就是一个二维差分的模版。代码如下。
#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> diff;
int n, m;
void add(int a, int b, int c, int d, int v) {diff[a][b] += v;diff[c + 1][b] -= v;diff[a][d + 1] -= v;diff[c + 1][d + 1] += v;
}
void build() {for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {diff[i][j] += diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1];}}
}
int main() {scanf("%d%d", &n, &m);vector<int> v;v.assign(n+2, 0);for(int i = 0;i < n+2;++i){diff.push_back(v);}for(int i = 1, x1, y1, x2, y2;i <= m;++i){scanf("%d%d%d%d", &x1, &y1, &x2, &y2);add(x1, y1, x2, y2, 1);}build();for(int i = 1;i <= n;++i){printf("%d", diff[i][1]);for(int j = 2;j <= n;++j){printf(" %d", diff[i][j]); }printf("\n");}return 0;
}题目七
测试链接：https://leetcode.cn/problems/stamping-the-grid/
分析：我们可以对每一个0点，也就是空的点计算出，以这个点为左上角点，然后贴一张邮票的右下角点。计算这个区域的累加和，如果是0，代表这个区域可以贴上邮票，如果大于0代表有被占据的格子，不能贴上邮票。可以新建一个二维矩阵处理贴上邮票的位置，也就是差分数组，把贴上邮票的位置集体加1,。把所有的邮票贴完之后判断原来矩阵中为0的位置，在新建矩阵中是否大于0。如果是等于0代表这个格子并没有贴上邮票返回false，遍历玩整个数组如果没有返回false就返回true。代码如下。
class Solution
{
public:int m;int n;vector<vector<int>> diff;vector<vector<int>> sum;void add(int a, int b, int c, int d, int v){diff[a][b] += v;diff[c + 1][b] -= v;diff[a][d + 1] -= v;diff[c + 1][d + 1] += v;}void build(){for (int i = 1; i <= m; i++){for (int j = 1; j <= n; j++){diff[i][j] += diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1];}}}int get_value(int x1, int y1, int x2, int y2){return sum[x2 + 1][y2 + 1] - sum[x2 + 1][y1] - sum[x1][y2 + 1] + sum[x1][y1];}void build_sum(vector<vector<int>> &grid){for (int i = 0; i < m; ++i){for (int j = 0; j < n; ++j){sum[i + 1][j + 1] = grid[i][j] + sum[i + 1][j] + sum[i][j + 1] - sum[i][j];}}}void clear(){vector<int> v1;vector<int> v2;v1.assign(n + 1, 0);v2.assign(n + 2, 0);for (int i = 0; i < m + 1; ++i){sum.push_back(v1);diff.push_back(v2);}diff.push_back(v2);}bool possibleToStamp(vector<vector<int>> &grid, int stampHeight, int stampWidth){m = grid.size();n = grid[0].size();clear();build_sum(grid);int c, d;for (int i = 0; i < m; ++i){for (int j = 0; j < n; ++j){if (grid[i][j] == 0){c = i + stampHeight - 1;d = j + stampWidth - 1;if (c < m && d < n && get_value(i, j, c, d) == 0){add(i + 1, j + 1, c + 1, d + 1, 1);}}}}build();for (int i = 0; i < m; ++i){for (int j = 0; j < n; ++j){if (grid[i][j] == 0 && diff[i + 1][j + 1] <= 0){return false;}}}return true;}
};其中，sum和diff数组都是下标从1开始，sum是在最上层和最左层赋0，diff是在四周赋0，都是为了避免边界判断和越界。
题目八
测试链接：https://leetcode.cn/problems/xepqZ5/
分析：这个题需要用到离散化的技巧，因为不可能根据力场的范围大小去生成一个相应长度的数组。比如一个力场最大范围到几百万，我们不可能生成一个几百万的二维数组，所以需要将力场的真实值范围转化为下标到一个数组当中。同时，因为力场的范围可能存在小数，所以需要放大坐标消除小数的影响。数组中的下标从小到大存储着力场的边界坐标，相邻下标并不代表力场的范围是相邻的。这样就可以把所有力场转化为每个下标，可以将下标看成是新的力场边界，虽然和原来的坐标范围没有相邻关系，不过将覆盖关系保留了，比如两个力场之前不是相邻的，但在新的边界上，有可能是相邻下标；但如果两个力场之前是相互覆盖的，在新的边界上也会是覆盖的，这就保证了计算的正确。遍历每个力场，找到力场范围对应的下标，在此下标范围内进行差分。构建差分数组得到最大立场值。代码如下。
class Solution {
public:int n;vector <long> trans_x;vector <long> trans_y;vector<vector<int>> diff;int sort_getNum(vector <long>& v){int length = 1;int range = (n << 1);sort(v.begin(), v.end());for(int i = 1;i < range;++i){if(v[i] != v[i-1]){v[length++] = v[i];}}return length;}int rank(vector <long> v, long real_value, int length){int ans = 0;int left = 0, right = length-1;int middle;while (left <= right){middle = (left + ((right - left) >> 1));if(v[middle] >= real_value){ans = middle;right = middle - 1;}else{left = middle + 1;}}return ans + 1;}void add(int a, int b, int c, int d, int v){diff[a][b] += v;diff[c + 1][b] -= v;diff[a][d + 1] -= v;diff[c + 1][d + 1] += v;}int build(int m, int n){int ans = 0;for (int i = 1; i <= m; i++){for (int j = 1; j <= n; j++){diff[i][j] += diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1];ans = ans > diff[i][j] ? ans : diff[i][j];}}return ans;}int fieldOfGreatestBlessing(vector<vector<int>>& forceField) {n = forceField.size();trans_x.assign(n<<1, 0);trans_y.assign(n<<1, 0);for(int i = 0, j = 0, k = 0;i < n;++i){trans_x[j++] = (long)(forceField[i][0] << 1) - (long)forceField[i][2];trans_x[j++] = (long)(forceField[i][0] << 1) + (long)forceField[i][2];trans_y[k++] = (long)(forceField[i][1] << 1) - (long)forceField[i][2];trans_y[k++] = (long)(forceField[i][1] << 1) + (long)forceField[i][2];}int length_trans_x = sort_getNum(trans_x);int length_trans_y = sort_getNum(trans_y);vector<int> temp;temp.assign(length_trans_y+2, 0);for(int i = 0;i < (length_trans_x+2);++i){diff.push_back(temp);}for(int i = 0;i < n;++i){int rank_front_x = rank(trans_x, (long)(forceField[i][0] << 1) - (long)forceField[i][2], length_trans_x);int rank_back_x = rank(trans_x, (long)(forceField[i][0] << 1) + (long)forceField[i][2], length_trans_x);int rank_front_y = rank(trans_y, (long)(forceField[i][1] << 1) - (long)forceField[i][2], length_trans_y);int rank_back_y = rank(trans_y, (long)(forceField[i][1] << 1) + (long)forceField[i][2], length_trans_y);add(rank_front_x, rank_front_y, rank_back_x, rank_back_y, 1);}return build(length_trans_x, length_trans_y);}
};其中，trans_x和trans_y数组就是转化的数组，sort_getNum方法是在去除重复值并返回去重后的长度。