算法（四）前缀和

前缀和也是一个重要的算法，一般用来快速求静态数组的某一连续区间内所有数的和，效率很高，但不支持修改操作。分为一维前缀和、二维前缀和。

重要的前言！

不要死记模板，具体题目可能是前缀和、前缀乘积、后缀和、后缀乘积等等多种情况！

主要是要领悟一维前缀和与二维前缀和的这种，通过预先计算某个位置之前的累积值，从而在后续查询中快速得到所需结果的思想！

一维前缀和

一维前缀和用来快速求静态一维数组的某一连续区间内所有数的和。

具体步骤如下：

1、预处理出一个前缀和数组 dp（数组下标从 1 开始，便于计算），元素个数与原静态数组一致，计算出 dp 数组各项的和 。dp[ i ] 表示原静态数组 [ 1, i ]  区间内所有元素的和。

元素公式：dp[ i ] = dp[ i - 1 ] + arr[ i ] （通过这里的 i - 1就可以看出，为什么要从1开始了，为了处理边界情况）

        

2、 使用前缀和数组计算某个字数组的和。 如果要求出 [ l, r ] 之间的和，dp[ i ] = dp[ r ] -  dp[ l - 1]。

一维前缀和模板题

二维前缀和

二维前缀和实际上就是在一维前缀和的基础上把静态一维数组变成一个二维矩阵。用来快速求静态二维数组的某一连续区间内所有数的和。思想大致相同。

具体步骤如下：

1、预处理出一个二维数组 dp，行数与列数都和原二维数组一致。计算出 dp 二维数组各项         的和 。dp[ i ][ j ] 表示原静态数组 [ 1, 1 ]  到 [ i, j ] 区间内所有元素的和。

     这里的元素公式是什么呢？ 

     我们采用容斥原理：

     元素公式：dp[ i ][ j ] = dp[ i - 1 ][ j ] + dp[ i ][ j - 1] + arr[ i ][ j ] - dp[ i - 1 ][ j - 1]

2、利用二维前缀和数组计算某个子矩阵的和。同样利用容斥原理。

     如果要求从 [ x1, y1 ] 到 [ x2, y2] 区间内所有元素的和 sum

     sum = dp[ x2 ] [ y2 ] - dp[ x1 - 1][ y2] - dp[ x2 ][ y1 - 1] + dp[ x1 -1 ][ y1 - 1]

二维前缀和模板题

AC代码：

#include 
#include 
using namespace std;

int main()
{
    int n, m, q;
    cin >> n >> m >> q;
    
    // 1、创建并输入一个 n+1 行， m + 1列的二维数组
    vector> arr(n+1, vector(m + 1));
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            cin >> arr[i][j];
        }
    }

    // 2、计算二维前缀和
    vector> dp(n+1, vector(m + 1));
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + arr[i][j];
        }
    }

    // 3、处理 q 次查询
    while(q--)
    {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        cout << (dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1]) << endl;
    }
    
    return 0;
}