1.1 算法原理#

所谓前缀和，就是记录下前方所有数据之和，当所需中间数据时，可以通过o(1)的时间复杂度将数据求出。

• 一维数组前缀和

求出1~i的所有项之和。

由于当运算到第i位时，前i-1位已经运算完成，故a[i] = a[i] + a[i-1]。

1. 当需要[l,r]之和时，可以通过a[r]-a[l-1]求出

• 二维数组前缀和

求出左上端点、右下端点分别为(1,1)，(i,j)的长方形内的数据之和

当运算到(i,j)时，前i-1排、第i排前j-1位均已运算完成，故a[i][j] = a[i][j]+a[i-1][j]+a[i-1]-a[i-1][j-1]。

1. 当需要左上端点、右下端点分别为(x1,y1)，(x2,y2)的长方形内的数据之和时，a[x2][y2]-a[x2][y1-1]-a[x1-1][y2]+a[x1-1][y1-1]

1.2 例题#

• 795. 前缀和

参考代码：

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. 子矩阵的和

参考代码：

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 算法原理#

所谓差分，就是记录每位数据与前一位数据之间的差，当需要对区间进行操作时，可以通过o(1)的时间复杂度完成操作。

同时我们可以发现差分数组的前缀和就是原数组。

• 一维数组差分

求出与前一项之差。当需要对[l,r]范围内的数进行加减操作时时，可以通过b[l]+c、b[r+1]-c实现

• 二维数组差分

二维差分数组的构建可以由其前缀和的结果来逆向考虑。

当对(x1,y1)，(x2,y2)的长方形内的数据都加上c时，即a[x1,y1]~a[x2,y2]均加c。故当b[x1,y1]+=c，b[x1,y2+1]-=c，b[x2+1,y1]-=c，b[x2+1,y2+1]+=c，即可实现仅区间内的数据加c。

当构建差分数组时，可以发现其为对长宽为1的长方形加a[i,j]，由此实现二维差分数组。

2.2 例题#

• 797. 差分

参考代码：

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. 差分矩阵

参考代码：

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 算法原理#

双指针问题主要是依据序列性质，使用指针j对有效查询范围进行记录，从而减少运算的时间复杂度。

双指针问题主要分为下面两类：

1. 在一个序列中，两个指针维护一段区间。
2. 在两个序列中，维护某种次序

基本模板(来自AcWing)

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

5
        //具体问题逻辑
6
    }
7
}

3.2 例题#

• 799. 最长连续不重复子序列

解决逻辑：设置cnt数组记录[j,i]区间内的数据出现次数，当i指向数a[i]已经出现时，让j向前移动，直到[j,i-1]中a[i]出现次数为0。过程中记录长度。

参考代码：

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. 数组元素的目标和

解决逻辑：由序列升序，可以直到当a[i]+a[j]>x时，a[i+1]+a[j]必然大于x。所以可以使用j来记录需要判断的边界，从而减少搜索时间。

参考代码：

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. 最长连续不重复子序列

解决逻辑：由子串是在母串中按次序出现，我们可以按位寻找子串每位在母串中对应的位置。

参考代码：

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
}

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
}

1.1 アルゴリズムの原理#

いわゆる累積和とは、前方のすべてのデータの和を記録しておくことを指し、所要の中間データを得る際には、o(1)の時間計算量でデータを求めることができる。

• 一次元配列の累積和

1からiまでのすべての項の和を求める。

1. 当運算到第i位時、前i-1位はすでに運算完了しているため、a[i] = a[i] + a[i-1]。

2. 当需要[l,r]の和時は、a[r]-a[l-1]で求められる

• 二次元配列の累積和

左上端点、右下端点がそれぞれ(1,1)、(i,j)の長方形内のデータの和を求める

i,jへ到達した時、前i-1排目と、第i排目の前j-1位はすべて計算済みであるため、a[i][j] = a[i][j]+a[i-1][j]+a[i-1]-a[i-1][j-1]。

1. 左上端点、右下端点がそれぞれ(x1,y1)、(x2,y2)の長方形内のデータの和は、a[x2][y2]-a[x2][y1-1]-a[x1-1][y2]+a[x1-1][y1-1]

1.2 例題#

• 795. 累積和

参考コード：

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. 部分行列の和

参考コード：

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 アルゴリズムの原理#

差分とは、各データと前のデータとの差を記録することで、区間に対して操作を行う際にo(1)の時間計算量で処理を完了できる。

また、差分配列の前縁の和は元の配列そのものになることが分かる。

• 一次元配列の差分

前項との差を求める。 [l,r] 範囲の数を加減する必要がある場合、b[l]+=c、b[r+1]-=c で実現

• 二次元配列の差分

二次元差分配列の構築は、その前縁和の結果から逆算して考えることができる。

(x1,y1)、(x2,y2) の長方形内のデータをすべて c 加えるとき、すなわち a[x1,y1]~a[x2,y2] がすべて c となるようにします。したがって b[x1,y1]+=c、b[x1,y2+1]-=c、b[x2+1,y1]-=c、b[x2+1,y2+1]+=c とすれば、区間内のデータのみを加えることができます。

差分配列を構築する際、それは長さ1の長方形に対して a[i,j] を加えることになるため、2次元差分配列を実現できる。

2.2 例题#

• 797. 差分

参考コード：

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. 差分矩阵

参考コード：

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 アルゴリズムの原理#

ダブルポインタ問題は、列の性質に基づき、有効なクエリ範囲を指針 j で記録することにより、計算時間の複雑さを低減します。

ダブルポインタ問題は主に以下の2つに分類されます。

1. 一つの列で、二つのポインタが区間を維持する。
2. 二つの列で、ある種の順序を維持する

基本テンプレート（AcWing より）

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

5
        //具体的な問題ロジック
6
    }
7
}

3.2 例题#

• 799. 最長連続不重複部分列

解法の逻辑：cnt 配列を用いて [j,i] 区間内のデータの出現回数を記録します。i が a[i] をすでに出現させている場合、[j,i-1] 内で a[i] の出現回数が0になるまで j を前方へ動かします。長さを途中で記録します。

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. 配列の要素の和を x に等しくする問題

解法の逻辑：数列は昇順なので、a[i]+a[j] > x となると、a[i+1]+a[j] は必ず x より大きくなる。従って判定が必要な境界を j で記録することで探索時間を削減できる。

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. 最長連続不重複部分列

解法の逻辑：母串中に子文字列は順序通り現れるため、母串中の各位置に対応する位置を順に探すことができます。

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
}