一维差分

• 前缀和与差分是逆运算

例如：

数组 a1 , a2，a3，a4，a5 ，…，an
构造 b1，b2，b3，b4，b5，…，bn
使得 ai = b1 + b2 + b3 + b4 + … + bi。
c此时 ai叫做 bi的前缀和，b 叫做 ai的差分.

差分的用途：

前缀和主要是计算数组中的某个区间 [ l, r ]，中间的所有数的和。
而差分主要是为了计算在[ l, r ]这个区间中所有的数全部加上一个常数c。

优点：

正常遍历数组中[ l , r ]区间的话，需要的是o(n)的复杂度，但是使用差分直接是o(1)的复杂度。差分只需要俩步计算。

步骤：

1. 要对数组 a的 [ l , r]区间的所有数全部加 +1，等价于b[ l ] + 1,(因为a数组是b数组的前缀和，bl +1,相当于把数组a中下标 > l 的所有数全部 +1)
2. 但是我们希望的是只对[ l , r] 这个区间数+1，经过上述运算，r后面的数也同时 +1，此时通过b[ r + 1] 进行 -1 操作。

图解

题目

输入一个长度为 n 的整数序列。

接下来输入 m 个操作，每个操作包含三个整数 l,r,c，表示将序列中 [l,r][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
1
2
3
4
5

输出样例：

3 4 5 3 4 2
1

代码

#include <iostream>
using namespace std;
const int N = 100010;

int n, m;
int a[N], b[N], s[N];

void insert(int l, int r, int c)              //核心公式
{
   b[l] += c;
   b[r + 1] -= c;
}
int main()
{
   scanf("%d%d", &n, &m);
   for (int i = 1; i <= n; i ++) scanf("%d", &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] ;        //前缀和公式
   
   for (int i = 1; i <= n; i ++)
   {
       a[i] += b[i];
       cout << a[i] << " ";
   }
   return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32