# AcWing 797. Diff

## 1. Description of the topic

Enter a length of n n nsequence of integers.

Next enter m m moperations, each containing three integers l , r , c l,r,c l,r,c, indicating that the sequence will be [ l , r ] [l,r] [l,r]each number between plus c c c。

Please output the sequence after all operations are performed.

Input format
The first line contains two integers n n nand m m m。

The second line contains n n nintegers, representing a sequence of integers.

next m m mlines, each containing three integers l l l， r r r， c c c, which represents an operation.

Output format
A total of one line, including n n nan integer representing the final sequence.

data range
1 ≤ n , m ≤ 100000 , 1≤ n, m ≤ 100000, 1≤n,m≤100000,
1 ≤ l ≤ r ≤ n , 1 ≤ l ≤ r ≤ n, 1≤l≤r≤n,
− 1000 ≤ c ≤ 1000 , −1000 ≤ c ≤ 1000, −1000≤c≤1000,
− 1000 ≤ −1000 ≤ −1000≤the value of an element in a sequence of integers ≤ 1000 ≤ 1000 ≤1000

Input sample:

```6 3
1 2 2 1 2 1
1 3 1
3 5 1
1 6 1```

Sample output:

`3 4 5 3 4 2`

## Second, the algorithm idea

### Definition of Difference

Difference is the inverse of prefix sum .

Suppose there is a sequence a 1 , a 2 , . . . , a n a_{1},a_{2},…,a_{n} a1​,a2​,…,an​, now we need to construct a sequence b 1 , b 2 , . . . , b n b_{1},b_{2},…,b_{n} b1​,b2​,…,bn​, use a i = b 1 + b 2 + . . . + b i a_{i}=b_{1}+b_{2}+…+b_{i} ai​=b1​+b2​+…+bi​, immediately a [ ] a[ ] a [ ] is b[ ] b[ ] the prefix sum of b[ ], then b [ ] b[ ] b [ ] is called a [ ] a[ ] Differenceof a [ ] .

### The role of difference

1. Only O(n) O(n) O ( n ) time complexity, by comparing b[ ] b[ ] b [ ] is the prefix sum, and the original array a [ ] a[ ] a[]
2. Free O(1) O(1) O ( 1 ) time to complete the operation: given an interval [ l , r ] [l, r] [l,r ] , add a constant c c each elementthis intervalc。

in a a a sequence [ l , r ] [l, r] [l,r ] interval plus constant c c c   <=> <=> <=>   b l + c , b r + 1 − c b_l+c,b_{r+1}-c bl​+c,br+1​−c

In other words : if an array needs to frequently add or subtract a constant to one of its intervals , I can convert to constructing the difference of the array , and then use O(1) O(1) The addition and subtraction of the difference array is completed in O ( 1 ) time, and finallyafter frequent interval addition and subtraction is obtained byprefix sum of the difference

### difference construction

There is a very simple construction: we can assume the sequence a 1 , a 2 , . . . , a n a_{1},a_{2},…,a_{n} a1​,a2​,…,an​Every number is 0 0 0 (not actually 0 0 0 ), then its difference sequence b 1 , b 2 , . . . , b n b_{1},b_{2},…,b_{n} b1​,b2​,…,bn​Also all 0 0 0 . then put the real a a a sequence as in [ 1 , 1 ] [1,1] [1,1 ] insert constant a 1 a_{1} a1​, in [ 2 , 2 ] [2,2] [2,2 ] insert constant a 2 a_{2} a2​, and so on.

## 3. Code

```#include <iostream>
using namespace std;

const int N = 1e5 + 10;
int b[N], n, m;

void insert(int l, int r, int c)
{
b[l] += c;
b[r + 1] -= c;
}

int main()
{
scanf("%d%d", &n, &m);

// Construct the initial difference sequence b from sequence a
for ( int i = 1 ; i <= n; i++)
{
int x;
scanf("%d", &x);
insert(i, i, x);
}

// Perform interval insertion
while (m--)
{
int l, r, c;
scanf("%d%d%d", &l, &r, &c);
insert(l, r, c);
}

// prefix and sum the difference sequence to get a sequence
for ( int i = 1 ; i <= n; i++)
{
b[i] += b[i - 1];
printf("%d ", b[i]);
}
puts("");

return 0;
}```