??作者介紹：22級樹莓人（計算機專業(yè)），熱愛編程＜目前在c＋＋階段，因為最近參加新星計劃算法賽道(白佬)，所以加快了腳步，果然急迫感會增加動力>——目標Windows，MySQL，Qt，數(shù)據(jù)結(jié)構(gòu)與算法，Linux，多線程，會持續(xù)分享學習成果和小項目的
??作者主頁：熱愛編程的小K
??專欄鏈接：算法筆記

??歡迎各位→點贊?? + 收藏?? + 留言???
??總結(jié)：希望你看完之后，能對你有所幫助，不足請指正！共同學習交流 ??

??一、前綴和

?? A、一維前綴和

1、什么是一維前綴和

原數(shù)組: a[1], a[2], a[3], a[4], a[5], …, a[n]
前綴和 S[i]為數(shù)組的前 i項和
前綴和: S[i] = a[1] + a[2] + a[3] + … + a[i]

注意：前綴和的下標一定要從 1開始, 避免進行下標的轉(zhuǎn)換，即定義S[0]等于0

2、一維前綴和的作用

快速求出元素組中某段區(qū)間的和

例如要求出l-r區(qū)間的和，則只需要執(zhí)行sum[r]-sum[l-1]

原理如下：

sum[r] = a[1] + a[2] + a[3] + a[l-1] + a[l] + a[l+1] ...... a[r]; sum[l - 1] = a[1] + a[2] + a[3] + a[l - 1]; sum[r] - sum[l - 1] = a[l] + a[l + 1]+......+ a[r];

并且時間復雜度為O(1)

3、習題：Acwing 795. 前綴和

輸入一個長度為 n的整數(shù)序列。

接下來再輸入 m個詢問，每個詢問輸入一對 l,r。

對于每個詢問，輸出原序列中從第 l個數(shù)到第 r個數(shù)的和

輸入格式

第一行包含兩個整數(shù) n和 m。

第二行包含 n個整數(shù)，表示整數(shù)數(shù)列。

接下來 m 行，每行包含兩個整數(shù) l和 r，表示一個詢問的區(qū)間范圍。

輸出格式

共 m行，每行輸出一個詢問的結(jié)果。

數(shù)據(jù)范圍

1≤l≤r≤n
1≤n,m≤100000
?1000≤數(shù)列中元素的值≤1000

輸入樣例：

5 3
2 1 3 6 4
1 2
1 3
2 4

輸出樣例：

3
6
10

4、代碼詳解

#include<iostream>
using namespace std;
const int N=1e5+10;
int a[N],sum[N];  //原數(shù)組與求和數(shù)組
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        sum[i]=sum[i-1]+a[i];   //構(gòu)建前綴和
    }
    while(m--)
    {
        int L,R;
        cin>>L>>R;
        cout<<sum[R]-sum[L-1]<<endl;
    }
    return 0;
}

??B、二維前綴和(矩陣和)

1、二維前綴和推導

從上圖我們很容易得到：圖1的面積=圖二的面積+圖三的面積+圖四的面積-圖五的面積(重復的面積）

所以我們得出二維前綴和的預處理公式：s[i][j]=s[i-1][j]+s[i][j-1]+a[i][j]-s[i-1][j-1]

接下來回歸問題去求以(x1,y1)為左上角和以(x2,y2)為右下角的矩陣的元素的和。

如圖：

不難看出綠色的面積=s[x2][y2]+s[x2][y1-1]+s[x1-1][y2]-s[x1-1][y1-1]

且時間復雜度也為O(1)

2、習題：Acwing 796. 子矩陣的和

輸入一個 n行 m列的整數(shù)矩陣，再輸入 q個詢問，每個詢問包含四個整數(shù) x1,y1,x2,y2，表示一個子矩陣的左上角坐標和右下角坐標。對于每個詢問輸出子矩陣中所有數(shù)的和。

輸入格式

第一行包含三個整數(shù) n，m，q。

接下來 n行，每行包含 m個整數(shù)，表示整數(shù)矩陣。

接下來 q行，每行包含四個整數(shù) x1,y1,x2,y2,表示一組詢問。

輸出格式

共 q 行，每行輸出一個詢問的結(jié)果。

數(shù)據(jù)范圍

1≤n,m≤1000
1≤q≤200000
1≤x1≤x2≤n
1≤y1≤y2≤m
?1000≤矩陣內(nèi)元素的值≤1000

輸入樣例：

3 4 3
1 7 2 4
3 6 2 8
2 1 2 3
1 1 2 2
2 1 3 4
1 3 3 4

輸出樣例：

17
27
21

3、代碼詳解

#include<iostream>
using namespace std;
const int N=1010;
int a[N][N],s[N][N];
int main()
{
    int n,m,q;
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            scanf("%d",&a[i][j]);
            //構(gòu)建前綴和
            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);
        //求并輸出矩形前綴和
        cout<<s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]<<endl;
    }
    return 0;
    
}

??二、差分

??A、一維差分

1、什么是差分

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

這里舉一個例子：

先給一個原數(shù)組a：a[1]、a[2]、a[3]、a[4]、a[5]...a[n]

然后這里再構(gòu)建一個數(shù)組b:b[1]、b[2]、b[3]...b[n]

使得:a[i]=b[1]+b[2]+b[3]...b[i]

即a是b的前綴和，反過來b就是a的差分

2、如何構(gòu)建差分數(shù)組

這里我們采取最暴力的做法，直接構(gòu)造，并且需要注意下標，所以我們這里還是令a[0]=0

注意：下面的構(gòu)造中，a為前綴和數(shù)組，b為差分數(shù)組

a[0]=0;
b[1]=a[1]-a[0];
b[2]=a[2]-a[1];
......
b[i]=a[i]-a[i-1];

3、差分數(shù)組有什么作用

我們先來看一個問題

給定區(qū)間[l ,r ]，讓我們把a數(shù)組中的[ l, r]區(qū)間中的每一個數(shù)都加上c,即 a[l] + c , a[l+1] + c , a[l+2] + c ,,,,,, a[r] + c;

暴力做法是for循環(huán)l到r區(qū)間，時間復雜度O(n)，如果我們需要對原數(shù)組執(zhí)行m次這樣的操作，時間復雜度就會變成O(n * m)。 這個時候就體現(xiàn)出差分的作用了，讓我們往下接著看

我們知道a是b的前綴和數(shù)組，所以改變b的一項就會改變a中有b的所有項

但是在有邊界之外的也多加上一個C，如圖所示

所以這里我們需要執(zhí)行兩步操作

b[l]+=c;

b[r+1]-=c;

因此我們得出一維差分結(jié)論：給a數(shù)組中的[ l, r]區(qū)間中的每一個數(shù)都加上c,只需對差分數(shù)組b做 b[l] + = c, b[r+1] - = c。時間復雜度為O(1), 大大提高了效率。

4、練習 Acwing 797. 差分

輸入一個長度為 n 的整數(shù)序列。接下來輸入 m個操作，每個操作包含三個整數(shù) l,r,c，表示將序列中 [l,r]之間的每個數(shù)加上 c。請你輸出進行完所有操作后的序列

輸入格式

第一行包含兩個整數(shù) n和 m。

第二行包含 n個整數(shù)，表示整數(shù)序列。

接下來 m行，每行包含三個整數(shù) l，r，c，表示一個操作。

輸出格式

共一行，包含 n個整數(shù)，表示最終序列。

數(shù)據(jù)范圍

1≤n,m≤100000
1≤l≤r≤n
?1000≤c≤1000
?1000≤整數(shù)序列中元素的值≤1000

輸入樣例：

6 3
1 2 2 1 2 1
1 3 1
3 5 1
1 6 1

輸出樣例：

3 4 5 3 4 2

5、代碼詳解

注意使用scanf進行輸入，效率比較高

#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N], b[N];
int main()
{
    int n, m;
    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;
}

??B、二維差分(差分矩陣)

類似于前面的二維前綴和，這里引用大佬林小鹿的圖解

所以要執(zhí)行四步操作：

b[x1][y1] += c;

b[x1][y2+1] -= c;

b[x2+1][y1] -= c;

b[x2+1][y2+1] += c;

3、習題：Acwing 798. 差分矩陣

輸入一個 n行 m列的整數(shù)矩陣，再輸入 q 個操作，每個操作包含五個整數(shù) x1,y1,x2,y2,c，其中 (x1,y1)和 (x2,y2) 表示一個子矩陣的左上角坐標和右下角坐標。每個操作都要將選中的子矩陣中的每個元素的值加上 c。請你將進行完所有操作后的矩陣輸出。

輸入格式

第一行包含整數(shù) n,m,q。

接下來 n行，每行包含 m個整數(shù)，表示整數(shù)矩陣。

接下來 q行，每行包含 55 個整數(shù) x1,y1,x2,y2,c，表示一個操作。

輸出格式

共 n行，每行 m個整數(shù)，表示所有操作進行完畢后的最終矩陣。

數(shù)據(jù)范圍

1≤n,m≤1000
1≤q≤100000,
1≤x1≤x2≤n
1≤y1≤y2≤m
?1000≤c≤1000
?1000≤矩陣內(nèi)元素的值≤1000文章來源地址http://www.zghlxwxcb.cn/news/detail-411368.html

輸入樣例：

3 4 3
1 2 2 1
3 2 2 1
1 1 1 1
1 1 2 2 1
1 3 2 3 2
3 1 3 4 1

輸出樣例：

2 3 4 1
4 3 4 1
2 2 2 2

4、代碼詳解

#include<iostream>
using namespace std;
const int N=1010;
int a[N][N],s[N][N];
int main()
{
    int n,m,q;
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%d",&s[i][j]);
    //構(gòu)建差分矩陣
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            a[i][j]=s[i][j]-s[i][j-1]-s[i-1][j]+s[i-1][j-1]; 
    while(q--)
    {
        int x1,y1,x2,y2,c;
        scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&c);
        a[x1][y1]+=c;
        a[x1][y2+1]-=c;
        a[x2+1][y1]-=c;
        a[x2+1][y2+1]+=c;
    }
    //求和
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
           s[i][j] = a[i][j] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
    for (int i = 1; i <= n; i ++ )
    {
        for (int j = 1; j <= m; j ++ ) 
        printf("%d ", s[i][j]);
        cout << endl;
    }
    return 0;
}

到了這里，關(guān)于一文帶你深入了解算法筆記中的前綴與差分（附源碼）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！