企业官网建设流程全解析

##一、前缀和
###1）一维前缀和
定义与初始化：

此为一维前缀和的定义与初始化
应用：一维前缀和的应用，便于计算一维数组中的区间和
eg.求一个而二维数组中的最大子串（洛谷p1115）
在这之前需要用到上面的定义与初始化

进阶思维：
求最大子段和
例如：2 -4 3 -1 2 -4 3
ans:4（3，-1，2）
可以用最大前缀和来解决
也可以用新的思维：
1.先看第一给最大一定是2；
2.再看如果最大子串和包含了-4，那么他一定要包含前面的2，这样是最优解，因为-4+2>-4;
3.接着看第三个，是3若最大子串中包含3，那一定不包含前面的2和-4，因为这使3变小了；
4.同理若包含-1，一定包含前面的3，这样是最优的2；
5.若包含2，则一定包含前面的-1，3，此时最优为4;........
6.综上所述:
- 第一个数为一个有效序列
- 如果一个数加上上一个有效序列得到的结果比这个数大，那么该数也属于这个有效序列。
- 如果一个数加上上一个有效序列得到的结果比这个数小，那么这个数单独成为一个新的有效序列
- 在执行上述处理的过程中实时更新当前有效序列的所有元素之和并取最大值。
- 如果出现可加可不加的序列，最好带上，这样方便与后面序列联系

得出此解法
###2）二维前缀和
定义与初始化：
1.s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1]
2.以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：
s[x2, y2] - s[x1 - 1, y2] - s[x2, y1 - 1] + s[x1 - 1, y1 - 1]；
综上：
初始化方法
1.

此时可以完美处理边界，因为用到i-1时如果从零开始就会访问到-1的位置；
2.

单独处理边界问题
eg.P1719
求出一个矩阵中的包含数据总和最大的矩形

##二、差分数组（解决区间的批量增减问题）
###1）一维差分数组
差分数组可以视为前缀和的逆运算，定义为数组当前位置处的数与前一个位置处的数的差值，记为diff；
初始化
diff[i]=arr[i]-arr[i-1];

如果不需要存储原数组可以cin>>a,节省空间；更标准的写法是写为vector diff(n + 2, 0)；
应用：将原数组从i到j加上一个数，那么相当于只对差分数组i处加一个数，在j+1处减去这个数既diff[i]+=num, diff[j+1]-=num;
###2）二位差分数组

故二位差分的一种定义为
diff[i][j] = arr [i][j] − arr [i − 1][j] − arr[i][j − 1] + arr[i −1 ][j − 1]
二位差分的应用：矩阵 (x1, y1)到 (x2, y2) 加 val，则相当于diff[x1][y1]+val , diff[x1][y2+1]-val,diff[x2+1][y1]-val,diff[x2+1][y2+1]-val,
即为：

利用二位差分的性质，可以得到新的初始化二位差分的方法（即可以视为从ij到ij的位置加上了arr[i][j]）