【競技プログラミング】セグ木まとめ【AtCoder Library】

## 背景
最近の**AtCoder Beginner Contest**（ABC339-ABC343）で立て続けにセグ木関連の問題が出て敗北し続けたためです．

基礎からアルゴリズムを理解すべきなのは本当にそうなのですが，まずは具体例ベースで概観を掴むのも時には重要だと思うので，具体例を通してセグ木のお気持ちを理解しようとおもいます．

取り敢えず記事にしましたが、どんどん加筆していけたらと思います。

# 前提
この記事では，[Atcoder Library](https://github.com/atcoder/ac-library?tab=readme-ov-file)の`segtree`を使用します．

# セグメント木とは

長さ$N$の配列$S$に対し，以下を$O(logN)$で行うことができる．

* 要素の1点変更
* 区間の**集約値**の取得

「集約値」とは，身近な例では総和や最小値などが当てはまる．

# AtCoder Libraryのつかいかた

## セグメント木の宣言

セグメント木は以下のようにして宣言できる．

```c++:コンストラクタ
// 長さ 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()`

## セグメント木が扱える演算

[モノイド](https://ja.wikipedia.org/wiki/%E3%83%A2%E3%83%8E%E3%82%A4%E3%83%89)の性質を満たす演算を扱うことができる．
つまり，以下の性質を満たす代数構造に対してセグメント木は使用できる．
* 結合律：$(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
```c++
void seg.set(int p, S x)
```
`a[p]`に`x`を代入する．

**計算量**
* $O(\log n)$

### get
```c++
S seg.get(int p)
```
`a[p]`を返す．

**計算量**
* $O(1)$

### prod
```c++
S seg.prod(int l, int r)
```
`op(a[l], ..., a[r - 1])`を，モノイドの性質を満たしていると仮定して計算する．$l=r$のとき，`e()`を返す．

**計算量**
* $O(\log n)$

### all_prod
```c++
S seg.all_prod()
```
`op(a[0], ..., a[n - 1])`を計算する．$n=0$のときは`e()`を返す．

**計算量**
* $O(1)$

### max_right
```c++
(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
```c++
(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)](https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_bf)

#### やること
* クエリ１：数列の１つの値を更新
* クエリ２：指定区間の最大値を求める

```c++
// モノイド
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](https://atcoder.jp/contests/abc339/tasks/abc339_e)
#### やること
* 長さ$N$の数列$A$が与えられる
* $A$の部分列であって、隣接する2項の差の絶対値が$D$以下であるようなものの長さの最大値を求める
* LISや似た形のDPは一点更新・区間MAX取得のセグ木で解くことができる
    * 参考：[LIS でも大活躍！ DP の配列使いまわしテクニックを特集](https://qiita.com/drken/items/68b8503ad4ffb469624c#4-lis-%E3%81%AE%E8%A7%A3%E6%B3%952-%E3%82%BB%E3%82%B0%E6%9C%A8-ver)

```c++
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](https://atcoder.jp/contests/abc125/tasks/abc125_c)
#### やること
* 数列の１つの値を自由に書き換える
* 書き換えたあとの数列の値全体の最大公約数の最大値を求める

```c++
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](https://atcoder.jp/contests/abc185/tasks/abc185_f)
#### やること
* $A_{X_i}$を$A_{X_i}​⊕Y_i​$に書き換える
* $A_{X_i}​⊕A_{X_{i+1}}​⊕A_{X_{i+2}}​⊕...⊕A_{Y_i}​$を求める

```c++
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;
        }
    }
}
```