Acwing 797 differential

Enter a length of n Integer sequence of .

Next input m Operations , Each operation contains three integers l,r,c, Indicates that... Will be in the sequence [l,r] Add... To each number between c.

Please output the sequence after all operations .

Input format
The first line contains two integers n and m.

The second line contains n It's an integer , Represents a sequence of integers .

Next m That's ok , Each line contains three integers l,r,c, Represents an operation .

Output format
All in one line , contain n It's an integer , Represents the final sequence .

Data range
1≤n,m≤100000,
1≤l≤r≤n,
−1000≤c≤1000,
−1000≤ The value of an element in an integer sequence ≤1000
sample input ：
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

Difference principle ：

In the array a1、a2、a3 .... On , Construct a new array , bring ai = b1 + b2 + ..... + bi, At this time, the array a Prefix and array , Array b It's a differential array

effect 1 ： If you have constructed a differential array , You can be in O(n) Get the original array in the time of （ Find... Directly from the prefix and ）

effect 2 ： stay O(1) In time , Add a value to all the ranges of an array
In an interval 【 l, r】 Inside , All numbers plus c, If you use the common method , You need to traverse , The time complexity is O(n), If differential is used , Can be reduced to O(1).

step ：

1. to b[l] add c, because a An array is b The prefix of the array and , here a[l] All the following numbers are added c
2. In addition, you need to give b[r + 1] subtract c, such a[r + 1] The latter will offset the former c 了 , This makes it possible to [l,r] All of the arrays in are added with c

Interval means ：

How to construct a differential array

The whole prefix and array can be regarded as all 0, So the difference array is all 0, After that, the prefix and array each come to a number , The difference is to add a number to the interval . In this way, the differential array is successfully constructed .

#include <iostream>

using namespace std;

const int N = 100010;

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

//  Analog insert construction difference array 
void insert(int l, int r, int c)
{
    
    b[l] += c, b[r + 1] -= c;
}

int main()
{
    
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ ) cin >> a[i];  //  Read in the original array 
    for(int i = 1; i <= n; i ++ ) insert(i, i, a[i]); //  Insert each value , Construct differential arrays 
    
    while(m --)
    {
    
        int x, y, z;
        cin >> x >> y >> z;
        //  Add value in the interval 
        insert(x, y , z);
    }
    
    //  Find the prefix sum of the difference fraction group , Get the final value of the original array in the interval sum 
    for(int i = 1; i <= n; i ++) b[i] += b[i - 1];  
    
    for(int i = 1; i <= n; i ++) cout << b[i] << ' ';
    
}