1. 累積和
1.1 アルゴリズムの原理
いわゆる累積和とは、前方のすべてのデータの和を記録しておくことを指し、所要の中間データを得る際には、o(1)の時間計算量でデータを求めることができる。
- 一次元配列の累積和
1からiまでのすべての項の和を求める。
当運算到第
i位時、前i-1位はすでに運算完了しているため、a[i] = a[i] + a[i-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]。
- 左上端点、右下端点がそれぞれ
(x1,y1)、(x2,y2)の長方形内のデータの和は、a[x2][y2]-a[x2][y1-1]-a[x1-1][y2]+a[x1-1][y1-1]
1.2 例題
参考コード：
void solve(){ cin>>n>>m; for(int i=1;i<=n;i++) cin>>a[i],a[i]+=a[i-1]; while(m--){ cin>>l>>r; cout<<a[r]-a[l-1]<<endl; }}参考コード：
void solve(){ cin>>n>>m>>q; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>a[i][j],a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1]; while(q--){ cin>>x1>>y1>>x2>>y2; cout<<a[x2][y2]-a[x2][y1-1]-a[x1-1][y2]+a[x1-1][y1-1]<<endl; }}2. 差分
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 例题
参考コード：
void solve(){ for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) b[i] = a[i]-a[i-1]; while(m--){ cin>>l>>r>>c; b[l]+=c;b[r+1]-=c; }for(int i=1,t=0;i<=n;i++) t+=b[i],cout<<t<<' ';}参考コード：
void add(){ b[x1][y1] += c;b[x1][y2+1] -=c; b[x2+1][y1] -= c;b[x2+1][y2+1] +=c;}void solve(){ for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>a[i][j],x1=x2=i,y1=y2=j,c=a[i][j],add(); while(q--){ cin>>x1>>y1>>x2>>y2>>c; add(); } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ a[i][j] = b[i][j] + a[i-1][j]+a[i][j-1]-a[i-1][j-1]; cout<<a[i][j]<<' '; }cout<<endl; }}3. 双指针
3.1 アルゴリズムの原理
ダブルポインタ問題は、列の性質に基づき、有効なクエリ範囲を指針 j で記録することにより、計算時間の複雑さを低減します。
ダブルポインタ問題は主に以下の2つに分類されます。
- 一つの列で、二つのポインタが区間を維持する。
- 二つの列で、ある種の順序を維持する
基本テンプレート（AcWing より）
void solve(){ for(int i=0,j=0;i<n;i++){ while(j<i && check(i,j)) j++;
//具体的な問題ロジック }}3.2 例题
解法の逻辑：cnt 配列を用いて [j,i] 区間内のデータの出現回数を記録します。i が a[i] をすでに出現させている場合、[j,i-1] 内で a[i] の出現回数が0になるまで j を前方へ動かします。長さを途中で記録します。
void solve(){ for(int i=1,j=1;i<=n;i++){ if(cnt[a[i]]){ while(cnt[a[i]]) cnt[a[j++]]--; } cnt[a[i]]++; ans = max(i-j+1,ans); }cout<<ans<<endl;}解法の逻辑：数列は昇順なので、a[i]+a[j] > x となると、a[i+1]+a[j] は必ず x より大きくなる。従って判定が必要な境界を j で記録することで探索時間を削減できる。
void solve(){ for(int i=0,j=m-1;i<n,j>0;i++){ while(a[i]+b[j]>x) j--; if(a[i]+b[j]==x){ cout<<i<<' '<<j<<endl; return 0; } }}解法の逻辑：母串中に子文字列は順序通り現れるため、母串中の各位置に対応する位置を順に探すことができます。
void solve(){ for(int i=0,j=0;i<n && j<m;i++,j++){ while(a[i] != b[j] && j<m) j++; if(i==n-1 && j < m) {cout<<"Yes"<<endl;return 0;} }cout<<"No"<<endl;}この記事が役に立ったときは、ぜひ他の人に共有してください!
一部の情報は古い可能性があります