?? PREFACE
??歡迎各位→點贊 ?? + 收藏 ? + 評論 ??
??系列專欄： 算法
?? 種一棵樹最好是十年前其次是現(xiàn)在

1.什么是前綴和

前綴和指一個數(shù)組的某下標(biāo)之前的所有數(shù)組元素的和（包含其自身）。前綴和分為一維前綴和，以及二維前綴和。前綴和是一種重要的預(yù)處理，能夠降低算法的時間復(fù)雜度?？梢钥焖俚厍蟪瞿骋欢蔚暮?。

2.一維前綴和

2.1 前綴和公式

已知數(shù)組 ：
前綴和：

2.2 前綴和的作用

而且前綴和時間復(fù)雜度：預(yù)處理O(n),查詢O(1)，效率比較高效，后續(xù)也會有一些其他的解法，比如說線段樹，樹狀數(shù)組等，前綴和的運行時間是最短的。

【補】關(guān)于左端邊界是1的選擇

我們會發(fā)現(xiàn)求l到r的和時，用的是,類似于數(shù)學(xué)里面的數(shù)列，此時令下標(biāo)要l-1>=0，這就保證了不需要定義任何的變量，使用起來比較簡單

2.3 習(xí)題：前綴和

#include <iostream>
using namespace std;
const int N=1e5+10;
int n,m;
int a[N],s[N];
int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)  scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)  s[i]=s[i-1]+a[i];//前綴和初始化
    
    while(m--)
    {
        int l,r;
        scanf("%d %d",&l,&r);
        printf("%d\n",s[r]-s[l-1]);//區(qū)間和計算
    }
    return 0;
    
}

3.二維前綴和

3.1 二維前綴和公式

首先二維前綴和公式的成立是基于容斥定理的，二維前綴和實際上就是二維數(shù)組上的前綴和了。一維數(shù)組的前綴和也是一個一維數(shù)組，同樣地，二維數(shù)組的前綴和也是一個二維的數(shù)組。

紅色區(qū)域的和：

3.2 習(xí)題：子矩陣的和

這一子矩陣中的所有數(shù)之和為：

#include <iostream>
using namespace std;
const int N =1010;
int n,m,q;
int a[N][N],s[N][N];

int main()
{
    scanf("%d %d %d",&n,&m,&q);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%d",&a[i][j]);
            
    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]+a[i][j];//求前綴和
            
            
    while(q--)
    {
        int x1,y1,x2,y2;
        scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
        printf("%d\n",s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1]);//算子矩陣的和
    }
    return 0;
}

4.什么是差分

類似于數(shù)學(xué)中的求導(dǎo)和積分，差分可以看成前綴和的逆運算。

5.一維差分

5.1 習(xí)題：差分

a數(shù)組是b數(shù)組的前綴和數(shù)組，比如對b數(shù)組的b[i]的修改，會影響到a數(shù)組中從a[i]及往后的每一個數(shù)。

首先讓差分b數(shù)組中的 b[l] + c ,a數(shù)組變成 a[l] + c ,a[l+1] + c,,,,,, ，a[n] + c;

然后我們還需要補充，b[r+1] - c, a數(shù)組變成 a[r+1] - c,a[r+2] - c,,,,,,,，a[n] - c;

我們畫個圖理解一下這個公式的由來:

#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int a[N], b[N];
int main()
{
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        b[i] = a[i] - a[i - 1];//構(gòu)建差分數(shù)組
    }
    int l, r, c;
    while (m--)
    {
        scanf("%d %d %d", &l, &r, &c);
        b[l] += c;//將[l,r]之間的每個數(shù)都加上c
        b[r + 1] -= c;
    }
    for (int i = 1; i <= n; i++)
    {
        a[i] = b[i] + a[i - 1];//前綴和運算
        printf("%d ", a[i]);
    }
    return 0;
}

5.2 時間復(fù)雜度的分析

如果采用暴力方法，用for循環(huán)l到r區(qū)間，時間復(fù)雜度O(n)，如果我們需要對原數(shù)組執(zhí)行m次這樣的操作，時間復(fù)雜度就會變成O(n*m)?？紤]差分做法可極大地降低復(fù)雜度。給a數(shù)組中的[ l, r]區(qū)間中的每一個數(shù)都加上c,只需對差分數(shù)組b做 b[l] + = c, b[r+1] - = c。時間復(fù)雜度為O(1), 大大提高了效率。

6.二維差分

6.1 習(xí)題：差分矩陣

#include <iostream>
using namespace std;
const int N=1010;
int n,m,q;
int a[N][N],b[N][N];
int main()
{
    scanf("%d %d %d",&n,&m,&q);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>a[i][j];
            //同時求二維差分矩陣b，即將前綴和公式移項
            b[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1];
        }
    }
    while(q--)
    {
        int x1,y1,x2,y2,c;
        cin>>x1>>y1>>x2>>y2>>c;
        //差分數(shù)組的模擬
        b[x1][y1]+=c;
        b[x1][y2+1]-=c;
        b[x2+1][y1]-=c;
        b[x2+1][y2+1]+=c;
    }
    
    //根據(jù)二維差分數(shù)組b去求二維前綴和矩陣a
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+b[i][j];
        }
    }
    
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            printf("%d ",a[i][j]);
        }
        printf("\n");
    }
    return 0;
    
}

6.2 差分矩陣的模擬

假定我們已經(jīng)構(gòu)造好了b數(shù)組，類比一維差分，我們執(zhí)行以下操作來使被選中的子矩陣中的每個元素的值加上c：

b[x1][y1] + = c;
b[x1,][y2+1] - = c;
b[x2+1][y1] - = c;
b[x2+1][y2+1] + = c;

每次對b數(shù)組執(zhí)行以上操作，等價于：

for(int i=x1;i<=x2;i++)
  for(int j=y1;j<=y2;j++)
      a[i][j]+=c;

圖解過程：文章來源地址http://www.zghlxwxcb.cn/news/detail-804243.html

b[x1][ y1 ] +=c ; //讓整個a數(shù)組中矩形面積的元素都加上了c。
b[x1,][y2+1]-=c ; //讓整個a數(shù)組中綠色矩形面積的元素再減去c，使其內(nèi)元素不發(fā)生改變。
b[x2+1][y1]- =c ; //讓整個a數(shù)組中紫色矩形面積的元素再減去c，使其內(nèi)元素不發(fā)生改變。
b[x2+1][y2+1]+=c; //讓整個a數(shù)組中紅色矩形面積的元素再加上c，紅色內(nèi)的相當(dāng)于被減了兩次，再加上一次c，才能使其恢復(fù)。