Prefix sum and difference

Prefix and introduction

Prefix and strictly speaking, it is not an algorithm , It's a mathematical idea , Its function is to $O(1)$ To find the sum of an interval .

One dimensional prefixes and

Prefixes and definitions :
Let the original sequence be :$a[1],a[2],a[3],a[4]....a[n]$
Prefix and sequence s by
$s[1] = a[1]$
$s[2] = a[1] + a[2]$
$s[3] = a[1] + a[2] + a[3]$
$s[n] = a[1] + a[2] + .... + a[n]$
How to find prefix and array
Direct use for Loop recursion to find

Log in and copy

for (int i = 1; i <= n; i ++)
    s[i] = s[i - 1] + a[i];

     

      
1.
      
2.
     

Pay attention to the boundary ：
In general , The subscript of the prefix and should start from 1 Start , And I will $s[0]$ Defined as 0（ See the next article for the reasons ）
The role of prefixes and arrays
It can quickly find the sum of a section of the original array
Suppose we ask for the original array $[l,r]$ The sum of this paragraph
If violence does for The time complexity of the cycle is $O(n)$
But if you use prefixes and arrays, you can $O(1)$ To find the interval sum within the time complexity of
Through the formula $sum[l,r]=s[r]-s[l-1]$
prove :
$sum[l,r]=a[l]+a[l+1]+...+a[r]$
because $s[l - 1] = a[1] + a[2] + ... + a[l - 1]$
Again because $s[r] = a[1] + a[2] + ... + a[l-1] + a[l] + ... + a[r]$
You can see $s[r] - s[l-1] = a[l] + ....+a[r]$ That is to say $sum$ Value
The reasons for the above boundary problems
If we ask $[1,10]$ And , According to the formula, it should be $s[10]-s[0]$
Because this and should be $a[1] + a[2] + ... + a[10]$ Is precisely $s[10]$ Value
So you get $s[0]=0$
So the prefix and should start from 1 Start counting （ Prevent cross-border subtraction ), And put 0 The position is initialized to 0（ Avoid handling special situations )
One dimensional prefix and template

Log in and copy

#include <iostream>
using namespace std;
const int N = 100010;
int n, m;
int a[N], s[N];
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ )
	cin >> a[i];

    for (int i = 1; i <= n; i ++ ) 
	s[i] = s[i - 1] + a[i]; //  Initialization of prefix and 

    while (m -- )
    {
        int l, r;
        cin >> l >> r;
        cout << s[r] - s[l - 1] << endl; //  Calculation of interval sum 
    }
    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.
     

Two dimensional prefixes and

One dimensional prefix sum is the sum of a range , alike , We can extend this idea to two dimensions , That is, finding the sum of a submatrix .
The two-dimensional prefix and refer to , With (x,y) Is the end of the lower right corner , The sum of all its upper left elements , As shown in the figure below , The sum of all elements in the red line area is $s[x][y]$ Value

How to find the sum of two-dimensional prefixes
Here's the picture

Let the original sequence be $a[][]$, The prefix and sequence are $s[][]$
be $s[i][j]$ The value of is equivalent to , The area enclosed by the red frame plus the area enclosed by the black frame , here , The gray part of the picture , It's been added twice , So subtract the gray area once , Then add $a[i][j]$ This point itself , According to the definition of two-dimensional prefix sum, we can see , The area enclosed by the red box is subscript $(i, j-1)$ The corresponding prefix and , Similarly, the area enclosed by the black frame is subscript $(i-1,j)$ The corresponding prefix and , The gray area is subscript $(i-1,j-1)$ The corresponding prefix and
Therefore, the operation of initializing the two-dimensional prefix sum is

Log in and copy

for (int i = 1; i <= n; i ++)
    for (int j = 1; j <= n; j ++)
        s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];

     

      
1.
      
2.
      
3.
     

How to find the sum of submatrix
The sum of submatrixes refers to , With (x2,y2) Is the lower right coordinate ,(x1,y1) The sum of the matrices circled by the coordinates of the upper left corner
The gray area shown in the figure below is the submatrix to be solved

The sum of submatrix is shown in the figure below

The sum of the grey areas is , With $(x2,y2)$ Is the prefix and of the matrix of coordinates , Subtract the sum enclosed in the green box , Subtract the sum enclosed by the black frame , At this point, the purple area in the figure is subtracted twice , So add the sum of the purple areas in the above figure , This is the sum of the gray areas in the figure . The area corresponding to the green box is $s[x2][y1-1]$ Value , The black area is $s[x1-1][y2]$ Value , The purple area is $s[x1-1][y1-1]$ Corresponding value
So the sum of the two-dimensional prefix and submatrix is

Log in and copy

int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
cout << s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];

     

      
1.
      
2.
      
3.
     

Introduction to difference

Difference is the inverse of prefix sum . Difference is a clever and simple way to process data , It is used to modify intervals and ask questions . Put a given set of data elements A Divided into many sections , Do many operations on these intervals , Each operation is the same addition and subtraction operation for all elements in a certain interval , If you modify each element in this interval one by one , It's very time consuming . The time complexity is $O(nk)$ among $k$ For the number of operations
So we're going to introduce differential arrays B, When modifying an interval , Just do a few operations on the difference group , This will affect the modification of the original interval , And the operation is very easy , yes $O(1)$ Complexity . When all modification operations are completed , Then use the difference array , Calculate the new prefix and array, that is, the sequence after the operation .

One dimensional difference

One dimensional difference definition :
We set the original sequence as $a[]$, The difference sequence is $b[]$
The original sequence :$a[1],a[2],a[3], ...,a[n]$
structure :$b[1],b[2],b[3],....b[n]$
bring
$a[i] = b[1] + b[2] + ... + b[i]$
At this time we call it $b$ by $a$ The difference between ,$a$ by $b$ And
So as long as we have $b$ Array , You can go to $O(n)$ Under the complexity of $a$ Array , That is, find the prefix and operation
So we can easily get
$b[1] = a[1]$
$b[2] = a[2] - a[1]$
$b[3] = a[3] -a[2]$
$b[n] = b[n] - b[n -1]$
One dimensional difference solution to the problem
The topic will give us a lot of operation , Let us in $a[l - r]$ Plus or minus a constant $c$, Ask us the sequence after several operations
If violence does , The time complexity of a single operation is undoubtedly $O(n)$ Of , Then we will construct a group of difference fractions to find , The complexity of the differential operation is $O(1)$
Operation for
$b[l] + c,b[r+1]-c$
Because if $b[l]$ add $c$, When finding prefix and sequence , because $a[l]$, as well as $a[l]$ All subsequent prefixes and must be counted $b[l]$ This point , So it's equivalent to adding the prefix to the array $a[l] + c, a[l + 1] + c ...a[r] + c, a[r + 1] + c.... a[n] + c$
and $b[r + 1] - c$, When finding prefix and sequence , Similarly, from $a[r + 1]$ Every element after is subtracted $c$, namely $a[r + 1] -c,a[r + 2] -c, ..... a[n] - c$.
In this way, these two operations are equivalent to $a[l] + c, a[l + 1] + c ,....., a[r] + c$, That's what the title asks for
Construction of one-dimensional difference
At first we can assume that $a$ The array is all 0, Then the differential array $b$ All for 0, But at this time $a$ Array has value , We can see it as a process $n$ The first modification operation
For the first time $[1,1]$ Interval plus $a[1]$
The second time was in $[2,2]$ Interval plus $a[2]$
All the way to $[n,n]$ Interval plus $a[n]$
prove :
If we assume to give $[1,1]$ Interval plus $a[1]$, amount to $b[1] + a[1], b[2] - a[1]$
to $[2,2]$ Interval plus $a[2]$, amount to $b[2] + a[2], b[3] - a[2]$
to $[3,3]$ Interval plus $a[3]$, amount to $b[3] + a[3], b[4] - a[3]$
After the above operations, we can see
b[1] = a[1]
b[2] = a[2] - a[1]
b[3] = a[3] - a[2]
Conform to the construction of the difference group , So after n After the first operation , You can get the difference array
Differential template

Log in and copy

#include <iostream>
using namespace std;
const int N = 100010;
int n, m;
int a[N], b[N];
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];
    for (int i = 1; i <= n; i ++ ) 
        insert(i, i, a[i]);
    while (m -- )
    {
        int l, r, c;
        cin >> 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 ++ )
         cout << b[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.
     

Two dimensional difference

alike , The two-dimensional difference here can be compared with the two-dimensional prefix and , Is to know a matrix $a[][]$, We are going to construct a difference matrix $b[][]$, bring $a[i][j]$, Save all $b[i][j]$ Sum of all elements in the upper left matrix . namely $a$ Matrix is $b$ Matrix prefix and matrix . Similarly, the construction of two-dimensional difference can also be compared with one-dimensional difference , First assume that it can be seen as a The elements in the matrix are all 0, be b The elements in the matrix are all 0, So if a The elements in the matrix are not 0 了 , It can be seen as $(i, j, i, j)$ Insert an element $a[i][j]$, It is too troublesome to prove the two-dimensional difference structure , It is proved that one can write by analogy with the structure of one-dimensional difference .
The problem solved by two-dimensional difference
Give $(x1,y1)$ Is the coordinate of the upper left corner , With $(x2,y2)$ Add or subtract a constant for each element in the submatrix of the coordinates of the lower right corner $c$.
If violence does it , Because you have to cycle through the elements of the entire matrix , So the time complexity is zero $O(n^2)$.
But if we construct a difference matrix to do it , You can go to $O(1)$ Add a constant to the submatrix within the time complexity of . Then we can find out the original matrix ( Do two-dimensional prefix and operation ).
Operation for

Log in and copy

  // among x1,y1 Is the coordinate of the upper left corner ,x2,y2 Is the coordinate of the lower right corner 
  b[x1][y1] += c;
  b[x2 + 1][y1] -= c;
  b[x1][y2 + 1] -= c;
  b[x2 + 1][y2 + 1] += c;

     

      
1.
      
2.
      
3.
      
4.
      
5.
     

prove
As shown in the figure below

If we give $b[x1][y1]$ Plus a constant $c$ Words , So all the elements in the lower right corner of this point , That is, all elements in the area enclosed by the red line in the figure will be added with a constant $c$, But we just need to add a constant to the gray area of the graph $c$, therefore , We can see , Subtract the area enclosed by the yellow line and the area enclosed by the dark blue line in the figure , The pink area in the picture has been subtracted once more , So add the pink area in the above figure , At this point, the result is that all the elements in the grey matrix are added with constants $c$. According to the difference definition , We can easily see , The area enclosed by the yellow line is affected by the difference matrix $(x1,y2+1)$ influence , Dark blue areas are affected by $(x2+1,y1)$ Influence , The pink area is affected by $(x2+1,y2+1)$ influence , Therefore, the above operation can be obtained
Two dimensional difference template

Log in and copy

#include <iostream>
using namespace std;
const int N = 1010;
int n, m, q;
int a[N][N], b[N][N];
void insert(int x1, int y1, int x2, int y2, int c)
{
    b[x1][y1] += c;
    b[x2 + 1][y1] -= c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y2 + 1] += c;
}
int main()
{
    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 ++ )
            insert(i, j, i, j, a[i][j]);
    while (q -- )
    {
        int x1, y1, x2, y2, c;
        cin >> x1 >> y1 >> x2 >> y2 >> c;
        insert(x1, y1, x2, y2, c);
    }
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];
    for (int i = 1; i <= n; i ++ )
    {
        for (int j = 1; j <= m; j ++ ) 
            cout << b[i][j] << " ";
        cout << endl;
    }
    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.
      
33.
      
34.
      
35.
      
36.
      
37.
      
38.
      
39.
     

Three dimensional difference

Three dimensional difference template code is relatively rare . Three dimensional difference is complex , And it will not appear in the general written examination or competition , Therefore, we are here only as an understanding content , You don't have to care . If you encounter , It can be generalized according to two-dimensional difference .
The value of the element is a three-dimensional array $a[][][]$ To define , Difference array $b[][][]$ It's also three-dimensional . Imagine three-dimensional difference as an operation in three-dimensional space . A one-dimensional interval is a line segment , Two dimensions are rectangles , So three-dimensional is a three-dimensional block . A small solid block has $8$ vertices , So three-dimensional interval modification , Need modification $8$ individual $b[][][]$​ value . It can be seen by analogy with the following figure （ The picture is from csdn）

Analogy to two-dimensional difference , The operation of three-dimensional difference is to add or subtract a constant to all elements in a cube $c$
We give the operation directly

Log in and copy

b[x1][y1][z1]       += c;   // front ： The lower left vertex , That is, the starting point of the interval 
b[x2+1][y1][z1]     -= c;   // front ： A point to the right of the lower right vertex 
b[x1][y1][z2+1]     -= c;   // front ： The upper point of the upper left vertex 
b[x2+1][y1][z2+1]   += c;   // front ： A point diagonally above the top right vertex 
b[x1][y2+1][z1]     -= c;   // Back ： A point behind the lower left vertex 
b[x2+1][y2+1][z1]   += c;   // Back ： A point diagonally behind the lower right vertex 
b[x1][y2+1][z2+1]   += c;   // Back ： A point diagonally behind the top left vertex 
b[x2+1][y2+1][z2+1] -= c;   // Back ： A point diagonally above and behind the top right vertex , That is, the last point at the end of the interval 

     

      
1.
      
2.
      
3.
      
4.
      
5.
      
6.
      
7.
      
8.
     

Note reference

Acwing Basic algorithm course