背景
最近のAtCoder Beginner Contest（ABC339-ABC343）で立て続けにセグ木関連の問題が出て敗北し続けたためです．
基礎からアルゴリズムを理解すべきなのは本当にそうなのですが，まずは具体例ベースで概観を掴むのも時には重要だと思うので，具体例を通してセグ木のお気持ちを理解しようとおもいます．
取り敢えず記事にしましたが、どんどん加筆していけたらと思います。
前提
この記事では，Atcoder Libraryのsegtreeを使用します．
セグメント木とは
長さ$N$の配列$S$に対し，以下を$O(logN)$で行うことができる．
- 要素の1点変更
- 区間の集約値の取得
「集約値」とは，身近な例では総和や最小値などが当てはまる．
AtCoder Libraryのつかいかた
セグメント木の宣言
セグメント木は以下のようにして宣言できる．
// 長さ n の数列 a を作る． 初期値は全部 e() となる．
segtree<S, op, e> seg(int n)
// 長さ n=v.size() の数列 a を作る． vの内容が初期値となる．
segtree<S, op, e> seg(vector<S> v)
ここで，宣言の際には以下を定義する必要がある．
- 型
S - 二項演算
S op(S a, S b) - 単位元
S e()
セグメント木が扱える演算
モノイドの性質を満たす演算を扱うことができる．
つまり，以下の性質を満たす代数構造に対してセグメント木は使用できる．
- 結合律：$(a⋅b)⋅c = a⋅(b⋅c)$ for all $a,b,c∈S$
- 単位元の存在：$a⋅e = e⋅a = a$ for all $a∈S$
| 型 | 演算 | 単位元 |
|---|---|---|
| 整数 | 和+
|
0 |
| 整数 | 積*
|
1 |
| 実数 | 最小値 | +INF |
| 実数 | 最大値 | -INF |
| bool | AND | 1 |
| bool | OR | 0 |
| bool | XOR | 0 |
| 整数 | GCD | 0 |
| 整数 | LCM | 1 |
| 文字列 | 連結+
|
空文字列 |
segtreeメソッド
set
void seg.set(int p, S x)
a[p]にxを代入する．
計算量
- $O(\log n)$
get
S seg.get(int p)
a[p]を返す．
計算量
- $O(1)$
prod
S seg.prod(int l, int r)
op(a[l], ..., a[r - 1])を，モノイドの性質を満たしていると仮定して計算する．$l=r$のとき，e()を返す．
計算量
- $O(\log n)$
all_prod
S seg.all_prod()
op(a[0], ..., a[n - 1])を計算する．$n=0$のときはe()を返す．
計算量
- $O(1)$
max_right
(1) int seg.max_right<f>(int l)
(2) int seg.max_right<F>(int l, F f)
(1) segtree上で二分探索をする．関数bool f(S x)を定義する必要がある．
(2) Sを引数にとりboolを返す関数オブジェクトを渡して使用する．
以下の条件を両方満たすrを（いずれか１つ）返す．
-
r=lもしくはf(op(a[l], a[l + 1], ..., a[r - 1])) = true -
r=nもしくはf(op(a[l], a[l + 1], ..., a[r])) = false
fが単調だとすれば，f(op(a[l], a[l + 1], ..., a[r - 1])) = trueとなる最大のrと解釈することが可能．
制約
-
fを同じ引数で呼んだとき，返り値は等しい（=副作用はない） f(e()) = true- $0 \leq l \leq n$
計算量
- $O(\log n)$
min_left
(1) int seg.min_left<f>(int r)
(2) int seg.min_left<F>(int r, F f)
(1) segtree上で二分探索をする．関数bool f(S x)を定義する必要がある．
(2) Sを引数にとりboolを返す関数オブジェクトを渡して使用する．
以下の条件を両方満たすlを（いずれか１つ）返す．
-
l=rもしくはf(op(a[l], a[l + 1], ..., a[r - 1])) = true -
l=0もしくはf(op(a[l - 1], a[l], ..., a[r - 1])) = false
fが単調だとすれば，f(op(a[l], a[l + 1], ..., a[r - 1])) = trueとなる最小のlと解釈することが可能．
制約
-
fを同じ引数で呼んだとき，返り値は等しい（=副作用はない） f(e()) = true- $0 \leq r \leq n$
計算量
- $O(\log n)$
具体例
一点更新・区間MAX取得
A58 - RMQ (Range Maximum Queries)
やること
- クエリ１：数列の１つの値を更新
- クエリ２：指定区間の最大値を求める
// モノイド
int op(int a, int b) { return max(a, b); }
// 単位元
int e() { return -1; }
int main() {
int n, q; cin>>n>>q;
vector<int> a(n, 0);
segtree<int, op, e> seg(a);
for (int i=0; i<q; i++) {
int t; cin>>t;
if (t == 1) {
int p,x; cin>>p>>x;
p--;
seg.set(p, x);
} else if (t == 2) {
int l, r; cin>>l>>r;
l--;r--;
cout<<seg.prod(l, r)<<endl;
}
}
return 0;
}
E - Smooth Subsequence
やること
- 長さ$N$の数列$A$が与えられる
- $A$の部分列であって、隣接する2項の差の絶対値が$D$以下であるようなものの長さの最大値を求める
- LISや似た形のDPは一点更新・区間MAX取得のセグ木で解くことができる
int op(int a, int b) { return max(a, b); }
int e() { return 0; }
const int A = 500010;
int main() {
int n, d; cin>>n>>d;
vector<int> a(n);
for (int i=0; i<n; i++){
cin >> a[i];
}
segtree<int, op, e> seg(A);
for (int i=0; i<n; i++) {
int l=max(0, a[i]-d);
int r=min(A-1, a[i]+d);
int mx=seg.prod(l, r+1);
seg.set(a[i], mx+1);
}
cout << seg.all_prod() << endl;
return 0;
}
一点更新・区間GCD取得
C - GCD on Blackboard
やること
- 数列の１つの値を自由に書き換える
- 書き換えたあとの数列の値全体の最大公約数の最大値を求める
int op(int a, int b) { return gcd(a, b); }
int e() { return 0; }
int main() {
int n, ans=0; cin>>n;
vector<int> a(n);
for (int i=0; i<n; i++){
cin >> a[i];
}
segtree<int, op, e> seg(a);
for (int i=0; i<n; i++) {
int tmp;
if(i==0){
tmp=a[i+1];
} else{
tmp=a[i-1];
}
seg.set(i, tmp);
if(ans<seg.prod(0, n)){
ans=seg.prod(0, n);
}
seg.set(i, a[i]);
}
cout << ans << endl;
return 0;
}
一点更新・区間XOR取得
F - Range Xor Query
やること
- $A_{X_i}$を$A_{X_i}⊕Y_i$に書き換える
- $A_{X_i}⊕A_{X_{i+1}}⊕A_{X_{i+2}}⊕...⊕A_{Y_i}$を求める
int op(int a, int b) { return a^b; }
int e() { return 0; }
int main() {
int n, q; cin >> n >> q;
vector<int> a(n);
for(int i=0; i<n; i++) cin >> a[i];
segtree<int, op, e> seg(a);
for(int i=0; i<q; i++){
int t, x, y; cin >> t >> x >> y;
x--;
if(t==1){
int tmp=seg.get(x);
seg.set(x, tmp^y);
} else{
cout << seg.prod(x, y) << endl;
}
}
}