知识点整理（1）差分/前缀和
本系列是为中大校赛做准备，顺便整理目前学到的算法知识点。
前缀和
一维前缀和及基础知识点
- 定义：对于一个数组，如a[5]=[1,2,3,4,5]，维护一个前缀和数组sum[5],其中sum[i]=a[0]+···a[i]。
- 经典应用：区间求和，如求a[1]+···a[3]的和，即ans=sum[3]-sum[0];
例一：随机权重问题
原题链接：leetcode528按权重随机选择
解题思路：此题的含义便是谁权重大谁被选中的概率就高，而解题便可以将权重化成实质性的数字，如权重为3，就占3个数，即对于[3,5,2]，3代表1,2,3，5代表4,5,6,7,8，2代表9,10，于是生成一个10以内的随机数判断其在哪个范围以选择数字。
具体操作就是对于权重数组生成一个前缀和数组，然后通过二分查找(lower_bound)来查找生成的随机数在哪个范围。
代码实现：
class Solution {
public:
int n,sum=0;
vector<int>nums;
Solution(vector<int>& w) {
n=w.size();
sum=0;
for(int i=0;i<n;i++){
sum+=w[i];
nums.push_back(sum);
}
}
int pickIndex() {
int num = rand()%sum+1;
return lower_bound(nums.begin(),nums.end(),num)-nums.begin();
}
};前缀和其实更贴近一种思想，不会专门提，但是在很多题中都会用到。
二维前缀和与容斥原理
定义：先假设出以下二维矩阵a
1 2 4 3
5 1 2 4
6 3 5 9二维前缀和即可定义为$sum_{x,y}=\sum\limits_{i=1}^x\sum\limits_{j=1}^ya_{i,j}$，则对应二维前缀和矩阵sum如下
1 3 7 10
6 9 15 22
12 18 29 45先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复，这种计数的方法称为容斥原理。
经典应用：利用容斥原理，来求子矩阵的和。显然在求二维前缀和时为
$$sum_{x,y}=sum_{x-1,y}+sum_{x,y-1}-sum_{x-1,y-1}+a_{x,y}$$
ps:实际操作是可在矩阵外围包上一层0以避免越界问题
而求和时，如求$(x_1,y_1)-(x_2,y_2)$的子矩阵和为
$$ans=sum_{x2,y2}-sum_{x1-1,y2}-sum_{x2,y1-1}+sum_{x1-1,y1-1}$$
代码实现：
class NumMatrix {
public:
int a[202][202],sum[202][202];
int m,n;
NumMatrix(vector<vector<int>>& matrix) {
memset(a,0,sizeof(a));
memset(sum,0,sizeof(sum));
m=matrix.size();
n=matrix[0].size();
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
a[i+1][j+1]=matrix[i][j];
}
}
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];
}
}
}
int sumRegion(int row1, int col1, int row2, int col2) {
return sum[row2+1][col2+1]-sum[row1][col2+1]-sum[row2+1][col1]+sum[row1][col1];//题目要求
}
};差分
很多人会把差分定义为前缀和的逆过程，但是我认为差分在很多题解中更像是对求前缀和的一种预处理，使像区间修改等的一些过程变得更加迅速。
一维差分
- 定义：将前缀和数组还原成原数组的过程，即
$$ a[i]=\left\lbrace
\begin{array}{llc}
sum[i] & i=1 & \\
sum[i]-sum[i-1] & i>1 &
\end{array}
\right.
$$
- 经典应用：区间修改，如让一个数组中a[1]到a[3]都加上一个数，如果用常规的方法，每次修改都可能达到$O(n)$的复杂度，这显然无法接受，而差分则是利用巧妙的方式完成了这个过程。
例一：航班预订统计
原题链接：leetcode1109航班预订统计
题解：这可以说差分典中典题了，题目翻译一下就是给定n条记录，m条修改，每次修改对于[first,last]这个区间里的每个数都加1，差分的操作如下：
- 对于每条修改，令a[first]++,a[last+1]–,最后执行完所有修改后，再求前缀和，sum[n]即为答案
代码实现：
class Solution {
public:
vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
vector<int>ans(n);
int m=bookings.size();
for(int i=0;i<m;i++){
ans[bookings[i][0]-1]+=bookings[i][2];
if(bookings[i][1]<n)ans[bookings[i][1]]-=bookings[i][2];
}
for(int i=1;i<n;i++){
ans[i]+=ans[i-1];
}
return ans;
}
};二维差分
先定义出一个初始化为零的二维矩阵，然后修改子矩阵的值，这就是二维差分最经典的应用
例一：子矩阵修改
原题链接：洛谷P3397地毯
解题思路：假设要使$(x_1,y_1)-(x_2,y_2)$这个子矩阵中的值都加1，只需执行以下步骤：
$$a_{x1,y1}++,a_{x1,y2+1}–,a_{x2+1,y1}–,a_{x2+1,y2+1}++$$
这里同样运用了容斥原理。最后求二维前缀和即可得出答案。
代码实现：
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1010;
int map_[maxn][maxn];
int n, m;
int main(){
cin >> n >> m;
int x1, x2, y1, y2;
memset(map_, 0, sizeof(map_));
for (int i = 1; i <= m;i++){//对差分数组的预处理
cin >> x1 >> y1 >> x2 >> y2;
map_[x1][y1]++;
map_[x2+1][y2+1]++;
map_[x1][y2 + 1]--;
map_[x2 + 1][y1]--;
}
for (int i = 1; i <= n;i++){//求二维前缀和
for (int j = 1; j <= n;j++){
map_[i][j] += map_[i - 1][j] + map_[i][j - 1] - map_[i - 1][j - 1];
}
}
for (int i = 1; i <= n;i++){//输出
for (int j = 1; j <= n;j++){
cout << map_[i][j] << ' ';
}
cout << endl;
}
return 0;
}树上前缀和及差分未完待续……
