1.1 Algorithm Principle#

The prefix sum is defined as recording the sum of all data to the left; when intermediate data is needed, it can be obtained in O(1) time.

• One-dimensional prefix sum

The sum of all terms from 1 to i.

Since when processing the i-th position, the first i-1 positions have already been computed, thus a[i] = a[i] + a[i-1].

1. When the sum of [l,r] is needed, it can be obtained by a[r]-a[l-1]

• Two-dimensional prefix sum

Find the sum of data within the rectangle whose top-left corner is (1,1) and bottom-right corner is (i,j)

When processing (i,j), the first i-1 rows and the first j-1 elements in row i have been computed, so a[i][j] = a[i][j] + a[i-1][j] + a[i][j-1] - a[i-1][j-1].

1. When the sum of data inside the rectangle with top-left corner (x1,y1) and bottom-right corner (x2,y2) is needed, it is a[x2][y2]-a[x2][y1-1]-a[x1-1][y2]+a[x1-1][y1-1]

1.2 Examples#

• 795. Prefix Sum

Reference code：

1
void solve(){
2
    cin>>n>>m;
3
    for(int i=1;i<=n;i++) cin>>a[i],a[i]+=a[i-1];
4
    while(m--){
5
        cin>>l>>r;
6
        cout<<a[r]-a[l-1]<<endl;
7
    }
8
}

• 796. Sum of Submatrices

Reference code：

1
void solve(){
2
    cin>>n>>m>>q;
3
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)
4
        cin>>a[i][j],a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
5
    while(q--){
6
        cin>>x1>>y1>>x2>>y2;
7
        cout<<a[x2][y2]-a[x2][y1-1]-a[x1-1][y2]+a[x1-1][y1-1]<<endl;
8
    }
9
}

2.1 Algorithm Principle#

The so-called difference array records the difference between each value and the previous value; when needing to operate on a range, the operation can be completed in O(1) time.

At the same time, we can see that the prefix sum of the difference array is the original array.

• One-dimensional difference

Compute the difference from the previous term. When needing to add or subtract to numbers in the range [l,r], it can be achieved by b[l]+=c and b[r+1]-=c

• Two-dimensional difference

The construction of the two-dimensional difference array can be reasoned backwards from its prefix sum.

When all data inside the rectangle defined by (x1,y1) and (x2,y2) is increased by c, i.e., a[x1,y1]~a[x2,y2] are all increased by c. Therefore by doing b[x1,y1]+=c, b[x1,y2+1]-=c, b[x2+1,y1]-=c, b[x2+1,y2+1]+=c, we can achieve adding c only to the region.

When constructing the difference array, one can see that it is adding a rectangle of width and height 1 with a[i,j], thus realizing a two-dimensional difference array.

2.2 Examples#

• 797. Difference

Reference code：

1
void solve(){
2
    for(int i=1;i<=n;i++) cin>>a[i];
3
    for(int i=1;i<=n;i++) b[i] = a[i]-a[i-1];
4
    while(m--){
5
        cin>>l>>r>>c;
6
        b[l]+=c;b[r+1]-=c;
7
    }for(int i=1,t=0;i<=n;i++) t+=b[i],cout<<t<<' ';
8
}

• 798. Difference Matrix

Reference code：

1
void add(){
2
    b[x1][y1] += c;b[x1][y2+1] -=c;
3
    b[x2+1][y1] -= c;b[x2+1][y2+1] +=c;
4
}
5
void solve(){
6
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)
7
        cin>>a[i][j],x1=x2=i,y1=y2=j,c=a[i][j],add();
8
    while(q--){
9
        cin>>x1>>y1>>x2>>y2>>c;
10
        add();
11
    }
12
    for(int i=1;i<=n;i++){
13
        for(int j=1;j<=m;j++){
14
            a[i][j] = b[i][j] + a[i-1][j]+a[i][j-1]-a[i-1][j-1];
15
            cout<<a[i][j]<<' ';
16
        }cout<<endl;
17
    }
18
}

3.1 Algorithm Principle#

Two-pointer problems are mainly based on the properties of the sequence, using pointer j to record the valid query range, thereby reducing the time complexity of computations.

Two-pointer problems are mainly divided into the following two categories:

1. In a single sequence, two pointers maintain a segment.
2. In two sequences, maintain some order

Basic template (from AcWing)

1
void solve(){
2
    for(int i=0,j=0;i<n;i++){
3
        while(j<i && check(i,j)) j++;
4

5
        // Specific problem logic
6
    }
7
}

3.2 Examples#

• 799. Longest continuous non-repeating subsequence

Solution idea: set a cnt array to record the occurrence count of data in the [j,i] interval; when i points to a[i] that has already appeared, move j forward until the count of a[i] in [j,i-1] becomes 0. Track the length along the way.

Reference code：

1
void solve(){
2
    for(int i=1,j=1;i<=n;i++){
3
        if(cnt[a[i]]){
4
            while(cnt[a[i]]) cnt[a[j++]]--;
5
        }
6
        cnt[a[i]]++;
7
        ans = max(i-j+1,ans);
8
    }cout<<ans<<endl;
9
}

• 800. Target Sum of Array Elements

Solution idea: Since the sequence is sorted in ascending order, you can stop when a[i]+a[j]>x; then a[i+1]+a[j] will also be greater than x. Therefore you can use j to record the boundary that needs to be checked, reducing search time.

Reference code：

1
void solve(){
2
    for(int i=0,j=m-1;i<n,j>0;i++){
3
        while(a[i]+b[j]>x) j--;
4
        if(a[i]+b[j]==x){
5
            cout<<i<<' '<<j<<endl;
6
            return 0;
7
        }
8
    }
9
}

• 799. Longest continuous non-repeating subsequence

Solution idea: Since the substring appears in the source string in order, we can locate each character of the substring in the source string sequentially.

Reference code：

1
void solve(){
2
    for(int i=0,j=0;i<n && j<m;i++,j++){
3
        while(a[i] != b[j] && j<m) j++;
4
        if(i==n-1 && j < m) {cout<<"Yes"<<endl;return 0;}
5
    }cout<<"No"<<endl;
6
}