---
tags: 競プロ
---
# お手軽非再帰 Segment Tree の書き方

注意 : ここに書いたコードの verify はしていません

### 長さ $2n$ のセグ木にする

> 
>
> [非再帰セグ木サイコー！ 一番すきなセグ木です p.35](https://hcpc-hokudai.github.io/archive/structure_segtree_001.pdf)

struct SegmentTree {
    int n;
    vector<T> seg;
    SegmentTree(int n): n(n), seg(n * 2) {}
}

* $\text{seg}[n], …, \text{seg}[2n - 1]$ が区間 $[0, 1), …, [n - 1, n)$ に対応します。
* $\text{seg}[i]$ は $\text{seg}[2i]$ と $\text{seg}[2i + 1]$ をくっつけたものです。
* $\text{seg}[0]$ は使いません。
* $2$ 冪のときと違って、$\text{seg}[1] = a_5 \otimes \dots \otimes a_{n-1} \otimes a_0 \otimes \dots \otimes a_4$ のようになるので、$a_0 \otimes \dots \otimes a_{n-1}$ が欲しい場合は $\Theta(\log n)$ 時間かける必要があります。(可換なら $\text{seg}[1]$ で良い)

### 1 点取得

T operator[](int i) const {
    return seg[n + i];
}

- $\text{seg}[n + i]$ が $a_i$ に対応するので、$\text{seg}[n + i]$ を返します。
- 短いので、混乱を避けるために複数回 1 点取得するなら書いておきましょう。
- `const` は `const SegmentTree` 型のときにも使えるように書きます。(JOI なら要らないかも)

### 1 点代入

void set(int i, T x) {
    i += n;
    seg[i] = x;
    while(i >>= 1) seg[i] = op(seg[i << 1], seg[i << 1 | 1]);
}

- $\text{seg}[n + i]$ が $a_i$ に対応するので、$\text{seg}[n + i]$ に代入して上を更新します。

void add(int i, T x) {
    i += n;
    do seg[i] += x; while(i >>= 1);
}
void set(int i, T x) {
    add(i, x - seg[n + i]);
}

- 区間和を持つセグ木なら、1 点代入より 1 点加算の方が簡単です。

### 区間取得

void prod(int l, int r) const {
    T ansL = e(), ansR = e();
    for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
        if(l & 1) ansL = op(ansL, seg[l++]);
        if(r & 1) ansR = op(seg[--r], ansR);
    }
    return op(ansL, ansR);
}

- 初めに $n$ を足し、上がりながら区間を狭めていきます。
- 上がるときは $2$ で割れないといけないので、$2$ で割れないときに狭めます。
- 非可換な場合は、左右に気をつける必要があります。

void prod(int l, int r) const {
    T ans = e();
    for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
        if(l & 1) ans = op(ans, seg[l++]);
        if(r & 1) ans = op(ans, seg[--r]);
    }
    return ans;
}

- 可換な場合は、実家のような安心感

### max-right

template<class F> int max_right(int L, F f) const {
    int l = n + L, w = 1, ansL = e();
    for(; L + w <= n; l >>= 1, w <<= 1) if(l & 1) {
        if(not f(op(ansL, seg[l]))) break;
        ansL = op(ansL, seg[l++]);
        L += w;
    }
    while(l <<= 1, w >>= 1){
        if(L + w <= n && f(op(ans, seg[l]))){
            ansL = op(ansL, seg[l++]);
            L += w;
        }
    }
    return L;
}

- `template<class F> F f` でラムダ式など全てを受け取れます。
- セグ木上の位置 `l` と列上の位置 `L` を両方持ちます。
- 現在のセグ木上の位置で $1$ 動かすと列上の位置がどれだけ動くかがわからないので、その変数 `w` を持ちます。
- 上がりながら動かし、ダメになったら下がりながら動かします。
- `L` が `n` を超えないように常に気をつけます。
- `w` が $0$ になったらおわりです。

### min-left

template<class F> int min_left(int R, F f) const {
    int r = n + R, w = 1, ansR = e();
    for(; R - w >= 0; r >>= 1, w <<= 1) if(r & 1) {
        if(not f(op(seg[r - 1], ansR))) break;
        ansR = op(seg[--r], ansR);
        R -= w;
    }
    while(r <<= 1, w >>= 1){
        if(R - w >= 0 && f(op(seg[r - 1], ansR))){
            ansR = op(seg[--r], ansR);
            R -= w;
        }
    }
    return R;
}

- 対称な実装で OK！
- `R` が `0` を超えないように常に気をつけます。
- `w` を持っているので `r = 2` から `r = 1` へ **上がって** 困ることはありません。(上がってもすぐキャンセルされる)