核心概念公式
设想S数组是 前缀和数组 ;;; B数组是 差分数组
S[i]= B[1]+B[2]+…+B[i]
S[i]= S[i-1]+B[i]
模拟构造差分数组的过程
S: 1 2 2 1 2 1
B: 1 -1 0 0 0 0
1 1 -2 0 0 0
1 1 0 -1 0 0
构造差分数组的方法
B[i] = S[i] - S[i-1]
等价于
在B[i]处加上S[i]的同时在B[i+1]处减去S[i]
C++ 代码
#include<iostream>
using namespace std;
const int N = 100010;
int S[N],B[N];
//S数组是 前缀和数组
// ***** S[i]= B[1]+B[2]+...+B[i] *****
// ***** S[i]= S[i-1]+B[i] *****
//核心操作
void insert(int l,int r,int c) {
B[l] = B[l] + c; // l处+c 对S[1 ~ l-1]无影响
// 对S[l ~ r] 加了c
// 对S[r+1 ~ N]也加了c
B[r+1] = B[r+1] - c; // r+1处-c 对S[1 ~ l-1]无影响
// 对S[l ~ r] 无影响
// 对S[r+1 ~ N]减了c
//整体是只对S【l~r】加了c 达到目的!
}
int main()
{
int n,m,l,r,c;
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>S[i];
//构造差分数组B
for(int i=1;i<=n;i++) insert(i,i,S[i]); //(1)B[1]+=S[1],B[2]-=S[1] (2)B[2]+=S[2] B[3]-=S[2] ......
//总结:构造差分数组的方法:B[i] = S[i] - S[i-1] 等价于 在B[i]处加上S[i]的同时在B[i+1]处减去S[i]
while(m--){
cin>>l>>r>>c;
insert(l,r,c);
}
//再计算一下对于当前数组的前缀和
//为什么求前缀和?因为本来就把S当前缀和 然后对差分数组进行了操作 代替直接对前缀和数组操作 现在根据操作后的差分数组算出操作后的前缀和数组
for(int i=1;i<=n;i++) S[i]=S[i-1]+B[i];
for (int i = 1; i <= n; i ++ ) cout<<S[i]<<" ";
return 0;
}