本篇內(nèi)容主要學習前綴和與其應用。

一、前綴和概念

前綴和是指某序列的前n項和，可以把它理解為數(shù)學上的數(shù)列的前n項和，而差分可以看成前綴和的逆運算。合理的使用前綴和與差分，可以將某些復雜的問題簡單化。

簡單來說：我們有一個數(shù)組x和它的前綴和數(shù)組y，他們滿足以下公式。

y 0 = x 0

y 1 = x 0 + x 1

y 2 = x 0 + x 1 + x 2

...

即 y[n]=x[1]+x[2]+...+x[n]。

二、前綴和分為一維前綴和二維前綴和

（1）一維前綴和

一維前綴和的得到很簡單，也很好理解，我們只需要遍歷的時候一直把之前計算的和 加上自己就能得到當前的和。

for (i=1; i<=n; i++) {
    cin >> a[i];
    s[i] = s[i-1] + a[i];
}

（2）二維前綴和

先上一張圖，看圖就知道是個什么邏輯了。

前綴和數(shù)組里每一個位置都表示原數(shù)組當前index左上方的數(shù)字的和。

比如像圖里面畫的：prefixSum[3, 3] = src[0~2, 0~2]的和;

二維前綴和數(shù)組要怎么計算出來呢？

可以分為四種情況

1. i==0 && j==0，只有一個直接賦值即可：prefixSum[0, 0] = src[0, 0]。

2. i==0，最左邊的一排，圖中黃色部分，prefixSum[0, j] = prefixSum[0, j-1] + src[0, j]；

3. j==0，最上面一排，途中紅色部分，prefixSum[i, o] = prefixSum[i-1, 0] + src[i, 0];

4. i!=0 || j!=0，圖中綠色部分，prefixSum[i][j] = prefixSum[i - 1][j] + prefixSum[i][j - 1] + src[i][j] - prefixSum[i - 1][j - 1];

具體講第四步：

我們要得到prefixSum[2,2]，我們知道應該是圖一中箭頭指向的區(qū)域。也就是9個方框加起來的和，也就是54。

看圖二，我們可以利用prefixSum[1, 2]和prefixSum[2, 1]，但是他倆的區(qū)域是重合的，如圖二所示，重合的區(qū)域又恰好是prefixSum[1, 1]負責的區(qū)域，相當于加了兩份，需要減掉一份。

所以prefixSum[2,2] = prefixSum[1, 2] + prefixSum[2, 1] - prefixSum[1, 1] + src[2, 2];

也就是54 = 33 + 21 -12(這個是prefixSum[1, 1]) +12(這是src[2, 2])

for(int i = 1; i <= n; i ++ )
        for(int j = 1; j <= m; j ++ )
            s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];

三、前綴和的應用

例題：區(qū)間求和

給你一串長度為 n 的數(shù)列 a1, a2, a3, ..., an，再給出 m 個詢問，每次詢問給出 L, R 兩個數(shù)，要求給出區(qū)間 [L, R] 里的數(shù)的和。

#include <iostream>
 
using namespace std;
 
const int MAXN = 1e5+2;
long long arr[MAXN] = {};
long long sum[MAXN] = {};
 
int main() {
    int n;
    cin >> n;
    
    int i, j;
    for (i=1; i<=n; i++) {
        cin >> arr[i];
        sum[i] = sum[i-1] + arr[i];
    }
 
    int m;
    int l, r;
    cin >> m;
    for (i=0; i<m; i++) {
        cin >> l >> r;
        cout << sum[r] - sum[l-1] << endl;
    }
 
    return 0;
}