例題

輸入一個長度為n的整數序列。

接下來輸入m個操作，每個操作包含三個整數l, r, c，表示将序列中[l, r]之間的每個數加上c。

請你輸出進行完所有操作後的序列。

輸入格式

第一行包含兩個整數n和m。

第二行包含n個整數，表示整數序列。

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

輸出格式

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

資料範圍

1≤n,m≤100000,

1≤l≤r≤n,

−1000≤c≤1000,

−1000≤整數序列中元素的值≤1000

輸入樣例：

6 3

1 2 2 1 2 1

1 3 1

3 5 1

1 6 1

輸出樣例：

3 4 5 3 4 2

思路

該題求某一段一維序列中，加上常量c後的新序列。

對于最簡單、暴力的方法，無腦的for循環。

然後若進行插入操作，無疑會TLE。

差分思想

即将輸入的序列存入數組a[N]中，另創一組a的差分數組為b[N]。

即a[N]為b[N]的字首和。（ a[i] - a[i-1] = b[i] ）

若在[l,r]區間上加c，

即隻需

b[l]+=c,b[r+1]-=c;

則插入函數應為

void insert(int l,int r,int c)
{
    b[l]+=c;
    b[r+1]-=c;
}
           

已知a[N]序列，在求差分數組b[N]時，

可認為在[i,i]區間上加上a[i]。

即

insert(i,i,a[i]);

二維差分

對于二維字首和，如圖

若在[x1,y1]到[x2,y2]這一塊矩形中每個元素加上c，如圖

則插入函數應為

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;
}
           

求二維差分數組b[i][j]時，同一維數組

即

insert(i,j,i,j,a[i][j]);

源代碼

❤️C++代碼如下❤️

#include<iostream>
#include<cstdio>

using namespace std;
const int N=1e6+10;
int a[N],b[N];
//b為a的差分數組，a為b的字首和數組

void insert(int l,int r,int c);

int main(){
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;i++){
        insert(i,i,a[i]);
    }
    while(m--){
        int l,r,c;
        scanf("%d %d %d",&l,&r,&c);
        insert(l,r,c);
    }
    for(int i=1;i<=n;i++){
        b[i]+=b[i-1];
        printf("%d ",b[i]);
    }

    return 0;
}
void insert(int l,int r,int c)
{
    b[l]+=c;
    b[r+1]-=c;
}