## application

Frequent range modification of an array or matrix results in the output of the operation.

## Method

### One-dimensional difference array

The method of obtaining difference array b from the original array is b[i] = a[i] - a[i-1]. So the prefix and array of difference array b are the original array a.
When we want to modify the value of a range of array a [l,r] plus c, we only need b[l] += c, and then b[r+1] -= c, so we can get the modified a when we prefix and restore the array of b.

#### tricks

The difference arrays of zero arrays are still zero arrays. Assuming that the modified zero array yields an array of z, then a+z yields the same result as our direct operation on the a array.
So we often use the zero array record operation without first finding the difference array. Then the prefix of the difference array and the array z are added to the array a.

### Two-dimensional difference matrix

According to the tricks above, we do not compute the difference matrix. The assumption is to operate on a zero matrix.
If we want to add C to the matrix with (x1,y1) as the upper left corner and (x2, y2) as the lower right corner, we can perform operations B [x1] [y1] += c; B [x1] [y2 + 1] - = c; B [x2 + 1] [y1] - = c; B [x2 + 1] [y1] - = c; B [x2 + 1] [y2 + 1] + c;
Interpretation:
Look at the picture below. Step 1: If we want to add C to the matrix of the shadow part, then we can add C to b[x1][y1] += c, because the prefix of the shadow part and the sum of the prefixes at (x1, y1) are the sum of the prefixes. Step 2: Because the prefix and time of S1 and S2 are also obtained by the prefix and accumulation at (x1, y1), we must subtract C from the boundaries entering them (x2 + 1, y1) and (x1, Y2 + 1), so that the prefix of S1 and S2 and the suffix of adding C subtract C remain unchanged. Step 3: When we calculate the prefix at S3, we will add (x2+1, y1) and (x1, y2+1), so the prefix at S3 is reduced twice by C. We will enter its boundary (x2+1, y2+1) and add C to make up for it. So we add two times C and subtract two times by c, and keep the prefix at S3 unchanged.

## Template

### One-dimensional difference array

```#include<iostream>
#include<vector>

using namespace std;

int main(){
int n, m;
cin >> n >> m;
vector<int> arr(n+1, 0);
for(int i = 1; i <= n; i++){
cin >> arr[i];
}
vector<int> b(n+1, 0);  // Record operation
for(int i = 0; i < m; i++){
int l, r, c;
cin >> l >> r >> c;
b[l] += c;
b[r+1] -= c;
}
int add = 0;    // Here, the prefix and the sum are represented by a variable add.
for(int i = 1; i < n; i++){
cout << add+arr[i] << " ";
}
}
```

### Two-dimensional difference matrix

```#include<iostream>
#include<vector>

using namespace std;

int main(){
int n, m, q;
cin >> n >> m >> q;
vector<vector<int>> matrix(n+1, vector<int>(m+1, 0));
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
cin >> matrix[i][j];
}
}
// Difference matrix, bigger, to prevent cross-border
// The difference matrix of 0 matrix is still 0 matrix.
// Initialization is 0. Operate the 0 matrix to get the result.
// Adding to matrix is equivalent to operating on matrix+0 matrix.
vector<vector<int>> b(n+2, vector<int>(m+2, 0));
while(q--){
int x1, y1, x2, y2, c;
cin >> x1 >> y1 >> x2 >> y2 >> c;
b[x1][y1] += c; //b[x1][y1] is used to compute prefixes of (x1, y1 to (x2, y2) matrices
b[x1][y2+1] -= c;
b[x2+1][y1] -= c;   // Where the prefix is found outside the matrix and the sum is added to b[x1][y1], c needs to be subtracted.
b[x2+1][y2+1] += c;
// When calculating the prefix at the lower right of (x2+1, y2+1), the values of (x1, y2+1) and (x2+1, y1) are used, subtracting two times of c, so we need to make up one time.
}
// Finding Prefixes and Restoration Matrix for Difference Matrix
vector<vector<int>> S(n+1, vector<int>(m+1, 0));
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
S[i][j] = S[i-1][j] + S[i][j-1] + b[i][j] - S[i-1][j-1];
}
}
// Adding the matrix obtained by restoring the difference matrix to the original matrix is the result of our operation on the original matrix.
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m-1; j++){
cout << S[i][j] + matrix[i][j] << " ";
}
cout << S[i][m] + matrix[i][m] << endl;
}
return 0;
}
```