AcWing笔记——前缀和
前言
数组的前缀和，代表着一个数组前N个数的和。主要用于优化这样一种场景：
当题目要求进行求出一个数组从下标 \(i\) 到下标 \(j\) 之间的元素的和，且会多次进行这种操作时，我们可以使用前缀和的方法来优化求和的过程。
时间复杂度对比：
- 若使用for循环遍历整个数组，对于n次操作，时间复杂度会达到O(n2)的级别，可见非常的耗时。
- 若使用前缀和的方法，我们要在原数组的基础上求出其前缀和数组，对应的代码如下
for(int i = 1 ;i < = length; i++)
Sum[i] = Sum[i-1] + Arr[i];
显然求出前缀和只需要遍历一遍原数组即可，时间复杂度为O(n)。而求出前缀和之后，对于每次对\(i\) 以及 \(j\) 之间和的询问，都可以这样求出 \(Ans = S[j] - S[i-1]\)。可以看出对于每次询问，求出答案的时间复杂度是O(1)数量级的。因此整个题目的时间复杂度也就从n方复杂度优化到了线性的复杂度。
\(1.\) 一维前缀和
现在让我们先考虑一维数组的前缀和
对于一个一维数组Arr[N],我们定义其前缀和数组为Sum[N]。
为方便起见，Arr以及Sum从1开始计数，Arr[0] = 0
从前言中对前缀和的定义，前缀和即为数组中前n个数的和。如Sum[6]代表着即为数组中前6个数的和，而Sum[7]代表着数组中前7个数的和。不难看出，Sum[7] = Sum[6] + Arr[7]。
这样我们就找出了对于前n个数的和的递推公式，即\(Sum[N] = Sum[N-1] +Arr[N]\)
因此要求前缀和，只需扫描一遍数组，递推求即可，代码如下
for(int i = 1 ;i < = length; i++)
Sum[i] = Sum[i-1] + Arr[i];
注意这里Arr[0] = 0，且下标从1开始，因此不需要考虑数组越界的问题
求出前缀和数组之后，若要求原数组从 \(i\) 到 \(j\) 的元素和，可以知道\(S[j]\)是从1加到\(j\)的元素之和，而\(S[i-1]\)为从1加到\(i-1\)的元素之和。那么从\(i\)加到\(j\)的元素之和即为\(S[j] - S[i-1]\)。
\(2.\) 二维前缀和
接下来我们将情况推广至二维数组前缀和
对于二维数组Arr[M][N]，给出一个点（i，j），我们称S[i][j]代表着数组Arr以（1，1）以及（i，j）为对角点的矩形中元素之和。
如上图，每一个方格代表一个数组元素，而前缀和S[i][j]即为（1，1）与（i，j）连成对角线的矩形内方格元素之和。
定义原数组为A[N][M]，其前缀和数组为S
我们可以从递推的思想来考虑这样一个二维前缀和的求法。
\(S[i][j] = S[j-1][i] + S[i][j-1] + S[j-1][i-1] + A[i][j] - 2S[i-1][j-1]\)
即\(S[i][j] = S[j-1][i] + S[i][j-1] + A[i][j] - S[i-1][j-1]\)
即i，j处的前缀和可以由其相邻的前缀和求出。
求二维前缀和的代码如下
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= M; j++)
{
S[i][j] = S[i - 1][j] + S[j][i - 1] + A[i][j] - S[i - 1][j - 1];
}
}
当我们要用到前缀和求由（x1 , y1）（x2 , y2）两点所构成的对角线的矩形内元素和时
如上图，要求（k，l）以及（i，j）之间的元素和，则可以看出answer = S[i][j]减去三部分，分别为S[i-1][j-1] S[i][l-1] S[k-1][j]，而且在减去后面的两个块的时候，会重复多减去两次S[i-1][j-1]，于是结果再加上2倍的S[i-1][j-1]。最终得到
\(Answer = S[i][j] - S[i][l-1] - S[k-1][j] + S[k-1][l-1]\)