##一、前缀和###1一维前缀和定义与初始化此为一维前缀和的定义与初始化应用一维前缀和的应用便于计算一维数组中的区间和eg.求一个而二维数组中的最大子串洛谷p1115在这之前需要用到上面的定义与初始化进阶思维求最大子段和例如2 -4 3 -1 2 -4 3ans:43-12可以用最大前缀和来解决也可以用新的思维1.先看第一给最大一定是22.再看如果最大子串和包含了-4那么他一定要包含前面的2这样是最优解因为-42-4;3.接着看第三个是3若最大子串中包含3那一定不包含前面的2和-4因为这使3变小了4.同理若包含-1一定包含前面的3这样是最优的25.若包含2则一定包含前面的-13此时最优为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];如果不需要存储原数组可以cina,节省空间更标准的写法是写为vector diff(n 2, 0)应用将原数组从i到j加上一个数那么相当于只对差分数组i处加一个数在j1处减去这个数既diff[i]num, diff[j1]-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][y21]-val,diff[x21][y1]-val,diff[x21][y21]-val,即为利用二位差分的性质可以得到新的初始化二位差分的方法即可以视为从ij到ij的位置加上了arr[i][j]