Prefix sum, difference, two-dimensional prefix sum, two-dimensional difference

Prefix sum

Function: interval query

Definition: prefix and array predix[n], original array a[n], the relationship between them is

Interval query: Find the sum of elements between a[left] to a[right]: p[right] – p[left-1]

template:

#include<iostream>
using namespace std;
#define int long long
const int N = 1e5 + 5;
int a[N];
int prefix[N];
signed main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n;
cin>>n;
for(int i=1;i<=n;i + + )
cin>>a[i];
for(int i=1;i<=n;i + + )
prefix[i] = prefix[i-1] + a[i];
int q;
cin>>q;
while(q--)
{
int l,r;
cin>>l>>r;
cout<<prefix[r] - prefix[l-1]<<'\\
';
}
}

Difference

Function: Interval modification

Definition: The relationship between the difference array d[n] and the original array a[n] is:

d[i] = a[i] – a[i-1];

Interval modification: let the elements between a[left] to a[right] + x: d[left] + =x,d[right + 1]-=x

example:

//Restore to the original array and modify the suffix interval
/*
Enter n 1e5 in the first line
The second line inputs the array a + -1e9
Enter m
In the next m lines, input l, r, x, and add x to the elements in the interval l and r.
Next enter q
Next q queries, input l and r each time
enter
5
1 1 1 1 1
2
1 3 1
2 5 -2
2
1 2
3 4
output
2 
-1 
*/
#include<iostream>
using namespace std;
#define int long long
const int N = 1e5 + 5;
int a[N];
int predix[N];
int diff[N];
signed main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n;
cin>>n;
for(int i=1;i<=n;i + + )
cin>>a[i];
for(int i=1;i<=n;i + + )
diff[i] = a[i] - a[i-1];
int m;
cin>>m;
while(m--)
{
int l,r,x;
cin>>l>>r>>x;
diff[l] + =x;
diff[r + 1]-=x;
}
for(int i=1;i<=n;i + + )
a[i] = a[i-1] + diff[i];
for(int i=1;i<=n;i + + )
predix[i] = predix[i-1] + a[i];
int q;
cin>>q;
while(q--)
{
int l,r;
cin>>l>>r;
cout<<predix[r] - predix[l-1]<<'\\
';
}
}

The relationship between prefix sum, original array and difference

The difference is transformed into the original array by performing the prefix sum operation, and the original array is transformed into the prefix sum array by performing the prefix sum operation.

The prefix sum array is transformed into the original array by differential operation, and the original array is transformed into the differential array by differential operation.

The relationship between the three is similar to derivation, original function and integral

Two-dimensional prefix sum:

Formula derivation

p[3][3] = p[2][3] + p[3][2]-p[2][2] + a[3][2]

It can be inferred from this

p[i][j] = p[i-1][j] + p[i][j-1]-p[i-1][j-1] + a[i][j]

Use two-dimensional prefix and array to perform interval query

as the picture shows

Find the sum of elements between [3,3] to [5,5] ans

ans = p[5][5]-p[2][5]-p[5][2] + p[2][2]

It follows from this

The formula for interval query x1, y1 to x2, y2 is

p[x2][y2]-p[x1-1][y2]-p[x2][y1-1] + p[x1-1][y1-1]

Example questions

/*
The first row n, m, q, n row m column q times query
Next enter the array
Each of the next q lines, x1, y1, x2, y2, represents the coordinates of the upper left corner and the lower right corner respectively.
prefix[i][j] = prefix[i-1][j] + prefix[i][j-1] -prefix[i-1][j-1] + a[i][j]
enter:
7 3 2
3 5 1
6 2 4
7 9 10
4 3 6
3 9 9
6 10 1
9 10 4
2 2 7 3
2 1 4 2
Output:
77
31
*/
#include<iostream>
using namespace std;
#define int long long
const int N = 1e3 + 5;
int a[N][N];
int prefix[N][N];
signed main()
{
int n,m,q;
cin>>n>>m>>q;
for(int i=1;i<=n;i + + )
for(int j=1;j<=m;j + + )
cin>>a[i][j];
for(int i=1;i<=n;i + + )
for(int j=1;j<=m;j + + )
prefix[i][j] = prefix[i-1][j] + prefix[i][j-1] -prefix[i-1][j-1] + a[i][j];
while(q--)
{
int x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
cout<<prefix[x2][y2] - prefix[x1-1][y2] - prefix[x2][y1-1] + prefix[x1-1][y1-1]<<'\\
\ ';
}
}

Two-dimensional difference

Formula derivation:

for(int i=1;i<=n;i + + )
{
for(int j=1;j<=m;j + + )
{
diff[i][j] + = a[i][j];
diff[i + 1][j] -= a[i][j];
diff[i][j + 1] -= a[i][j];
diff[i + 1][j + 1] + = a[i][j];
}
}

Interval modification

As shown below

diff[x1][y1] + =c;
diff[x1][y2 + 1]-=c;
diff[x2 + 1][y1]-=c;
diff[x2 + 1][y2 + 1] + =c;

Example questions

/*
Given a matrix with n rows and m columns
There are q operations, each operation inputs x1, y1, x2, y2, c, which means the corresponding sub-matrix plus c
Output the matrix after the operation is completed
enter:
4 3 3
1 5 1
3 3 2
5 3 4
4 4 2
1 2 1 2 2
2 1 2 3 2
4 2 4 3 1
output
1 7 1
5 5 4
5 3 4
4 5 3
*/
#include
using namespace std;
const int N = 1e3 + 5;
int a[N][N];
int diff[N][N];
int main()
{
int n,m,q;
cin>>n>>m>>q;
for(int i=1;i<=n;i + + )
for(int j=1;j<=m;j + + )
cin>>a[i][j];
for(int i=1;i<=n;i + + )
{
for(int j=1;j<=m;j + + )
{
diff[i][j] + = a[i][j];
diff[i + 1][j] -= a[i][j];
diff[i][j + 1] -= a[i][j];
diff[i + 1][j + 1] + = a[i][j];
}
}
while(q--)
{
int x1,y1,x2,y2,c;
cin>>x1>>y1>>x2>>y2>>c;
diff[x1][y1] + =c;
diff[x1][y2 + 1]-=c;
diff[x2 + 1][y1]-=c;
diff[x2 + 1][y2 + 1] + =c;
}
for(int i=1;i<=n;i + + )
for(int j=1;j<=m;j + + )
a[i][j] = a[i-1][j] + a[i][j-1] - a[i-1][j-1] + diff[i][j];
for(int i=1;i<=n;i + + )
{
for(int j=1;j<=m;j + + )
cout<
Example: Rat, rat, duck
Problem overview:
There are n animals on the farm, either rats or ducks, numbered from 1 to n, and each animal has a weight ai
 You can use magic at most once to turn the rats numbered in [l,r] into ducks and ducks, and the ducks and ducks into rats.
 What is the maximum total weight of a duck?
 Enter T in the first line, indicating the number of samples 1~10
 for each sample
 Enter n 1e5 in the first line
 The second line contains n integers, indicating the type of the i-th small animal. 0 is rat, 1 is duck.
 The third line contains n integers, representing the weight of the i-th small animal 1e9
 enter
 2
 3
 0 0 0
 1 2 3
 4
 0 1 0 0
 2 5 6 5
 output
 6
 16
Ideas:
Use ESS to record the weight of ducks without magic.
Then use prefix[] to record the prefix sum of the weight offset
The so-called weight offset is how much the total weight of a duck will increase or decrease if magic is used on a certain animal.
For example, if a rat weighs 10kg, use magic on it and turn it into a duck. In this way, the total weight of the duck will increase by 10kg, so the weight offset of the rat is + 10
For another example, a duck weighs 9kg. Use magic on it to turn it into a rat. In this way, the total weight of the duck will be reduced by 9kg, so the weight offset of the duck is -9
In the end, you only need to find the maximum sub-segment sum of the weight offset prefix sum, that is, find a left and a right so that the value of prefix[right]-prefix[left-1] is the largest (enumerate right, one-level loop can be )

Code:
#include<iostream>
using namespace std;
const int N = 1e5 + 5;
int a[N],b[N];//Type, weight
int prefix[N];//The prefix sum of the offset
void solve()
{
int n;
cin>>n;
int ess=0;//If you don’t do magic, the duck’s weight
for(int i=1;i<=n;i + + )
cin>>a[i];
for(int i=1;i<=n;i + + )
{
cin>>b[i];
prefix[i] = prefix[i-1] + (a[i]?-1:1)*b[i];//If it is a rat, add the weight, otherwise subtract
ess + = a[i]*b[i];
}
int maxa=0,mina=0;//The maximum sub-segment sum of prefix, the smallest prefix[] before i
for(int i=1;i<=n;i + + )
{
maxa = max(maxa,prefix[i]-mina);
mina = min(mina,prefix[i]);
}
cout<<ess + maxa<<'\\
';
}
int main()
{
int t;
cin>>t;
while(t--)
solve();
}