Prefix and topic training

The prefix and

 

The prefix and 、 Difference _ Xiaoxuecai's blog -CSDN Blog

Quickly find the sum of all numbers in a certain interval of a static array ,( Can only query , Do not modify , A number cannot be modified during query , And then check )

Enter a length of n Integer sequence of , Input m A asked , What is the sum of a certain number in the sequence

Tree array and line segment tree support query while modifying , The time complexity is O( logn ),logn Constant is very large

If we do it directly and violently , In fact, it is relatively slow , If the violence needs to be repeated , Suppose we want to L - R The sum of this paragraph , You need to do the following , The time complexity is O( n )

In the worst case ,l and r Take the starting point and the ending point , If we ask many times , Suppose to ask for 10 w Time , Each cycle 10 w All over , The total time complexity is 100 Billion , Can cause a timeout

Using prefix sum, we can quickly calculate the sum of all numbers in a certain interval

Reprocess a new array s Array ,si = a1 + a2 + a3 + . . . + ai, every last si Represents the front of the original array i The number and , Special provisions ,s0 = 0

Handle si = si-1 + ai, You can get it by cycling si, Preprocessing si The time complexity is O( n )

obtain si after , How to calculate the sum between two paragraphs ？

When we preprocess si after , When calculating the sum of a certain paragraph , You need to calculate the difference between the two numbers , Only one operation is needed , The time complexity of each query can be reduced from O( n ) Optimize to O( 1 )

Be careful s[ 0 ] No initialization required , because s Is a global array , If the variable is defined as a global array , The initial value must be 0, If it's a local array , The initial value is a random value

Is there a problem when taking the boundary ？

When L = 1 When ,s[ L - 1 ] = s[ 1 - 1 ] = s[ 0 ] = 0, That is to take s[ R ], As long as the prefix and subscript are from 1 Start ,s[ 0 ] Express 0, The boundary is no problem , Otherwise, special judgment is required

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 100010;

int n,m;
//a  Represents the original array 
int a[N];
//s  Represents prefixes and arrays 
int s[N];

int main()
{
    // Read in  n  Represents the length of the sequence , Subscript from  1  Start ,m  Number of questions 
    scanf("%d%d", &n, &m);
    // Read in  n  Number 
    for(int i = 1;i <= n;i++ )
    {
        scanf("%d",&a[i]);
        s[i] = s[i - 1] + a[i]; 
    }
    // Handle  m  A asked 
    while(m -- ) 
    {
        // Read the range of the interval at each step 
        int l,r;
        scanf("%d%d", &l, &r);
        printf("%d\n",s[r] - s[l - 1]);
    }
    return 0;
}

The sum of submatrix

 

The last problem is actually in a one-dimensional array , Each time I want to quickly find the sum of a certain one-dimensional continuous interval , Two dimensional prefixes and ideas are for two-dimensional arrays

Enter a n That's ok m The integer matrix of columns , Input again q A asked , Each query contains four integers x1、y1、x2、y2, Now find the sum of some sub matrix of this two-dimensional array

The input scale is relatively large ,n and m yes 1k, So there's a total of 100 w Number

Let's say I have a 3 × 4 Matrix , Each lattice represents a number in the array

inquiry 1、1、2、2        17

The subscript of the array in the upper left corner of the submatrix is ( 1,1 ), The subscript of the array in the lower right corner of the submatrix is ( 2,2 ), Suppose that the array subscripts are all from 1 At the beginning , It is the sum of the colored submatrix

inquiry 2、1、3、4        27

inquiry 1、3、3、4        21

The title gives a two-dimensional matrix , Find the sum of submatrixes in a certain matrix every time

If violence solving requires a double loop , Time complexity is high , Is there a solution similar to the one-dimensional prefix and ？

The answer is yes , First, find the prefix of this matrix and the matrix ,( Like prefixes and arrays in one dimension , every last si Represents the first... In the original array i The number and ) Prefix and matrix each Sxy Represents the sum of all numbers in the upper left corner of the original matrix

 

 

How to calculate prefixes and matrices , How to get the prefix and matrix from the original matrix ？

The sum of all the numbers above plus the sum of all the numbers on the left , All submatrixes in the upper left corner are added twice , To subtract once

You can use the idea of the inclusion exclusion principle

Make sure all the squares except the last one are added exactly once , Then we can add up the number of this grid

Within the linear time complexity, the matrix can be used to calculate Sxy, Because of every Sxy Only constant operations are used

Suppose the upper left corner of this lattice is ( x1,y1 ) and The lower right corner ( x2,y2 )

The input scale is relatively large , Recommend to use scanf Read in

The absolute value of the element value in the matrix is 1000 within , The maximum value of the absolute value of the sum of the whole matrix is 100 × 100 w Less than 10^9, There is no need to consider explosion int The problem of

Remove the sum of all numbers on the top and the sum of all numbers on the left , The submatrix in the upper left corner is removed twice , One more time

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

int n,m,q;
// Original array  a  Prefixes and arrays  s
int a[N][N],s[N][N];

int main()
{
    //n  and  m  Represents the length and width of the original matrix  q  Number of questions 
    scanf("%d%d%d", &n, &m, &q);
    // Read in the original matrix 
    for(int i = 1;i <= n;i++ )
        for(int j = 1;j <= m;j++ )
        {
            scanf("%d", &a[i][j]);
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
        }
    // Handle  q  A asked   Read in the upper left and lower right corners 
    while(q -- )
    {
        int x1,y1,x2,y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        printf("%d\n",s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]); 
    }
    return 0;
}