一维差分复习+二维差分

#include <bits/stdc++.h>
using namespace std;
const int n=2e5+10;
int n, m,a[N],c[N],x,y;
//如果对原数组从x到y这段范围进行修改   +K
//那么对于差分数组而言 修改就是 c[x]+=K  c[y+1]-=K
// 1.先通过原数组构建差分数组
//c[i][j]=a[i][j]+a[i-1][j-1]-a[i-1][j]-a[i][j-1]
// 2.利用差分数组 快速的完成区间修改操作
//假设我们现在想对a数组的  左上角坐标是 (x,y) 右下角坐标是(xx,yy)   +K
//c[x][y]+=K   c[xx+1][y]-=K   c[x][yy+1]-=K c[xx+1][yy+1]+=k
// 3.还原原数组
for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        a[i][j]=c[i][j]-a[i-1][j-1]+a[i-1][j]+a[i][j-1] 
    }
}
// 4.通过原数组 计算答案

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) {
        cin>>a[i];
        c[i]=a[i]-a[i-1];
    }
    while(m--){
        cin>>x>>y;
        c[x]++;
        c[y+1]--;
    }
    for(int i=1;i<=n;i++) a[i]=c[i]+a[i-1];
    for(int i=1;i<=n;i++) cout<<a[i]<<" ";
	return 0;
}