背景

最近の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取得のセグ木で解くことができる
- 参考：LIS でも大活躍！ DP の配列使いまわしテクニックを特集

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;
        }
    }
}