[C++] 差分 AcWing 797. 差分 Day7

[C++] 差分 AcWing 797. 差分 Day7

这里写目录标题

题目

思路

代码

题目

https://www.acwing.com/problem/content/799/

思路

创建一个原数组a 构造一个数组b
输入数组a 然后将数组a的元素 进行 差分 赋值给 数组b
核心思想：差分

	b[l] =b[l] + value;   //表示数组a[l]以及后面的a[l+1] a[l+2] ... a[end] 全部元素加上一个值value
	b[r+1] -=b[r] - value; //表示数组a[r+1]以及后面的a[l+2] a[l+3] ... a[end] 全部元素减去一个值value

这样就达到了 部分区间元素加值 的效果 时间复杂度O( 1 )

代码

 #include
using namespace std;
const int N = 1e6+5;
int a[N], b[N];
void insert(int l , int r , int value){//将序列中[l, r]之间的每个数都加上c
    b[l] += value;
    b[r + 1] -= value;
}
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 r,l,value;
        scanf("%d%d%d",&r,&l,&value);
        insert (l,r,value);
    }
    for (int i = 1;i <= n; i ++ )  printf("%d ",b[i]);

    return 0;
}