前綴和差分是一對(duì)逆運(yùn)算

1.一維前綴和

有一個(gè)長(zhǎng)度為n的數(shù)組an:a1,a2…an;

對(duì)于前綴和：Si= a1+a2+…+ai

如何求Si,S[i] = s[i-1]+a[i]

前綴和可以快速求出原數(shù)組里面一段數(shù)的和。比如求一段區(qū)間[l,r],如果按照原來(lái)的做法，需要循環(huán)一遍，O(n),有前綴和的算法：

這個(gè)區(qū)間的數(shù)就是(Sr) - (sl-1)。同時(shí)，為了方便計(jì)算令s[0] = 0.比如計(jì)算[1,l],既s[l]-s[0] = s[l].

其實(shí)前綴和就是一個(gè)區(qū)間相減的操作，統(tǒng)一處理。前綴和其實(shí)是非常簡(jiǎn)單的

練習(xí)題：

輸入一個(gè)長(zhǎng)度為 nn 的整數(shù)序列。

接下來(lái)再輸入 mm 個(gè)詢(xún)問(wèn)，每個(gè)詢(xún)問(wèn)輸入一對(duì) l,rl,r。

對(duì)于每個(gè)詢(xún)問(wèn)，輸出原序列中從第 ll 個(gè)數(shù)到第 rr 個(gè)數(shù)的和。

輸入格式

第一行包含兩個(gè)整數(shù) nn 和 mm。

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

接下來(lái) mm 行，每行包含兩個(gè)整數(shù) ll 和 rr，表示一個(gè)詢(xún)問(wèn)的區(qū)間范圍。

輸出格式

共 mm 行，每行輸出一個(gè)詢(xún)問(wèn)的結(jié)果。

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

1≤l≤r≤n1≤l≤r≤n,

1≤n,m≤1000001≤n,m≤100000,

−1000≤數(shù)列中元素的值≤1000

#include <iostream>
using namespace std;
const int N = 100010;
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]);
    }
    return 0;
}

2.二維前綴和

二維前綴和是在一個(gè)二維矩陣?yán)锴笞泳仃嚨暮?/p>

練習(xí)題：

輸入一個(gè) nn 行 mm 列的整數(shù)矩陣，再輸入 qq 個(gè)詢(xún)問(wèn)，每個(gè)詢(xún)問(wèn)包含四個(gè)整數(shù) x1,y1,x2,y2x1,y1,x2,y2，表示一個(gè)子矩陣的左上角坐標(biāo)和右下角坐標(biāo)。

對(duì)于每個(gè)詢(xún)問(wèn)輸出子矩陣中所有數(shù)的和。

輸入格式

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

接下來(lái) nn 行，每行包含 mm 個(gè)整數(shù)，表示整數(shù)矩陣。

接下來(lái) qq 行，每行包含四個(gè)整數(shù) x1,y1,x2,y2x1,y1,x2,y2，表示一組詢(xún)問(wèn)。

輸出格式

共 qq 行，每行輸出一個(gè)詢(xún)問(wèn)的結(jié)果。

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

1≤n,m≤10001≤n,m≤1000,

1≤q≤2000001≤q≤200000,

1≤x1≤x2≤n1≤x1≤x2≤n,

1≤y1≤y2≤m1≤y1≤y2≤m,

−1000≤矩陣內(nèi)元素的值≤1000\

#include <iostream>
using namespace std;
const int N = 1010;
int n,m,q;
long 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]);
            //求前綴和
            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;
}

3.一維差分

給定a[1],a[2],…,a[n]構(gòu)造差分?jǐn)?shù)組b[N],使得a[i] = b[1]+b[2]+…+b[i]

b1 = a1,b2 = a2-a1,b3 = a3-a2,直到bn = an-an-1

b是a的差分，a是b的前綴和。有b數(shù)組就可以通過(guò)O(n)的時(shí)間復(fù)雜度得到a數(shù)組。

推導(dǎo)過(guò)程：

現(xiàn)在在a數(shù)組[L,R]中全部加上C，那就是al+C,al+1+C,…,ar+C,通過(guò)暴力的方式O(n)可以求解，那差分可以變成O(1)

在[L,R]中，如果我們?cè)赽數(shù)組bl+C,那么al也會(huì)加上C，al+1也會(huì)加上C…an+1也會(huì)加上C，因?yàn)槊恳淮味紩?huì)加上一個(gè)bl。但是我們只要al到ar加上C，那么ar后面不要加上C，那么我們直接讓br-c即可完成數(shù)組a在[L,R]范圍里全部加上C。

核心操作是將a[L~R]全部加上C等價(jià)于b[L] +=C,b[R+1]-=C

把O(n)提高到O(1)

假定a數(shù)組全是初始化為0，那b數(shù)組也是全為0，但是題目a數(shù)組并不是0，我們可以看成進(jìn)行n次插入操作，第一次是在原數(shù)組a[1,1]加上a1,第二次是在原數(shù)組a[2,2]加上a2…以此類(lèi)推即可，所以并不需要去想如何構(gòu)造差分

題目：

輸入一個(gè)長(zhǎng)度為 nn 的整數(shù)序列。

接下來(lái)輸入 mm 個(gè)操作，每個(gè)操作包含三個(gè)整數(shù) l,r,cl,r,c，表示將序列中 [l,r][l,r] 之間的每個(gè)數(shù)加上 cc。

請(qǐng)你輸出進(jìn)行完所有操作后的序列。

輸入格式

第一行包含兩個(gè)整數(shù) nn 和 mm。

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

接下來(lái) mm 行，每行包含三個(gè)整數(shù) l，r，cl，r，c，表示一個(gè)操作。

輸出格式

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

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

1≤n,m≤1000001≤n,m≤100000,

1≤l≤r≤n1≤l≤r≤n,

−1000≤c≤1000−1000≤c≤1000,

−1000≤整數(shù)序列中元素的值≤1000

#include <iostream>
using namespace std;
const int N = 100010;
int n,m;
int a[N],b[N];
void insert(int l,int r,int c)
{
    b[l]+=c;
    b[r+1]-=c;
}
int main()
{
    cin>>n>>m;
    for(int i = 1;i<=n;i++)
    {
        cin>>a[i];
        insert(i,i,a[i]);
    }
    while(m--)
    {
        int l,r,c;
        cin>>l>>r>>c;
        insert(l,r,c);
    }
    for(int i = 1;i<=n;i++) a[i] = a[i-1]+b[i];
    for(int i = 1;i<=n;i++) printf("%d ",a[i]);
    return 0;
}

4.二維差分

二維差分也是一樣的道理

練習(xí)題：

輸入一個(gè) nn 行 mm 列的整數(shù)矩陣，再輸入 qq 個(gè)操作，每個(gè)操作包含五個(gè)整數(shù) x1,y1,x2,y2,cx1,y1,x2,y2,c，其中 (x1,y1)(x1,y1) 和 (x2,y2)(x2,y2) 表示一個(gè)子矩陣的左上角坐標(biāo)和右下角坐標(biāo)。

每個(gè)操作都要將選中的子矩陣中的每個(gè)元素的值加上 cc。

請(qǐng)你將進(jìn)行完所有操作后的矩陣輸出。

輸入格式

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

接下來(lái) nn 行，每行包含 mm 個(gè)整數(shù)，表示整數(shù)矩陣。

接下來(lái) qq 行，每行包含 55 個(gè)整數(shù) x1,y1,x2,y2,cx1,y1,x2,y2,c，表示一個(gè)操作。

輸出格式

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

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

1≤n,m≤10001≤n,m≤1000,

1≤q≤1000001≤q≤100000,

1≤x1≤x2≤n1≤x1≤x2≤n,

1≤y1≤y2≤m1≤y1≤y2≤m,

−1000≤c≤1000−1000≤c≤1000,

−1000≤矩陣內(nèi)元素的值≤1000

#include <iostream>
using namespace std;
const int N = 1010;
int n,m,q;
int a[N][N],b[N][N];
void Insert(int x1,int y1,int x2,int y2,int c)
{
    b[x1][y1]+=c;
    b[x2+1][y1]-=c;
    b[x1][y2+1]-=c;
    b[x2+1][y2+1]+=c;
}
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++)
        {
            Insert(i,j,i,j,a[i][j]);
        }
    }
    while(q--)
    {
        int x1,y1,x2,y2,c;
        scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&c);
        Insert(x1,y1,x2,y2,c);
    }
    for(int i = 1;i<=n;i++)
    {
        for(int j = 1;j<=m;j++)
        {
            b[i][j] += b[i-1][j]+b[i][j-1]-b[i-1][j-1];
        }
    }
     for(int i = 1;i<=n;i++)
    {
        for(int j = 1;j<=m;j++)
        {
            printf("%d ",b[i][j]);
        }
        puts("");
    }
    return 0;
}

到此這篇關(guān)于C++前綴和與差分的使用示例講解的文章就介紹到這了,更多相關(guān)C++前綴和與差分內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論