题目描述
输入一个长度为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++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+5;
int n,m;
int a[N]; // 用来存原始数组
int b[N]; // 差分数组
int main()
{
cin >> n >> m;
for(int i=1;i<=n;i++){
cin >> a[i];
b[i]=a[i]-a[i-1]; // 第i项减去前一项
}
while(m--){
int l,r,x;
cin >> l >> r >> x;
b[l]=b[l]+x; // 区间内的+x
b[r+1]=b[r+1]-x; // 区间外的-x
}
for(int i=1;i<=n;i++){
b[i]=b[i]+b[i-1]; // 差分数组还原为原数组
cout << b[i] << " ";
}
cout << endl;
return 0;
}
前缀和
前缀和指一个数组下标i之前的所有元素的和
int a[N]; // 原始元素数组
int sum[N]; // 前缀和数组
前缀和数组中的第i个为 数组a中前i-1个元素相加之和再加上当前这个元素a[i]
sum[i]=sum[i-1]+a[i];
前缀和一般用于查询,当查询次数m很大时,会TLE,此时可以用前缀和进行查询,每次查询给出左右区间l,r
计算区间和 int sum(int l,int r){
return sum[r]-sum[l-1];
}
通过前缀和可以将复杂度从o(m*n)减低为o(m+n)
差分
差分是指相邻两个数之间的差,即第i个数与前一个数之间的差
int a[N]; // 原始元素数组
int sub[N]; // 差分数组
差分数组中的第i个为 数组a中第i个元素与第i-1个元素的差
sub[i]=a[i]-a[i-1];
差分一般用于区间加,将一个区间的数都加上x,每次查询给出左右区间和这个区间内要加上的数x
在此题中数组b即为差分数组
i 1 2 3 4 5 ...... i i+1
a[i] a1 a2 a3 a4 a5 ...... ai ai+1
b[i] a1-0 a2-a1 a3-a2 a4-a3 a5-a4.....ai - ai-1 ai+1 - ai
假设l为1,r为3,区间相加得数为x
对于区间内的数相加x b[l]=b[l]+x;
对于区间外的数不加,所以要减去x b[r+1]=b[r+1]-x;
操作之后差分数组b变为b
i 1 2 3 4 5 ........ i i+1
b[i] a1-0+x a2-a1 a3-a2 a4-a3-x a5-a4.........ai - ai-1 ai+1 - ai
将差分数组还原为元素数组
b[i]=b[i-1]+b[i]
i 1 2 3 4 5.............i i+1
b[i] a1-0+x a2-a1+a1-0+x a3-a2+a2+x a4-a3-x+a3+x a5-a4+a4...ai - ai-1 + ai-1 ai+1 - ai + ai
a1+x a2+x a3+x a4 a5..............ai ai+1
可以看到区间1,3之间的元素都加了x