セグメント木の基礎

# セグメント木   
データ構造の一種です。   
完全二分木であり、区間に関する処理を扱うのに適しています。   
計算量はO(logN)です。   
データ構造ですが、問題によって複雑なカスタマイズを求めまれます。   

![スクリーンショット 2024-11-29 11.01.14.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/626801/6e3af69a-9742-1423-8505-b46c8a18d5be.png)

- 8の要素数の区間を処理するために必要な配列   
8(n_とします)以上の2^xの中で最小の値nを求めます。   
8の要素数を処理するのに2^4 * 2 - 1の要素数が必要になります。   

```C++:C++
void init(int n_){
    n = 1;
    while(n < n_) n *= 2;
    for(int i=0; i < 2 * n - 1; i++) dat[i] = INF;
}
```

- 親から子へ   

```C++:C++
    dat[k*2+1]    // 左辺
    dat[k*2+2]    // 右辺
```

- 子から親へ   

```C++:C++
    dat[(k-1)/2]    // 親
```

- 値の更新   
今回は例として区間内の最小値を更新する処理になっています。
最大値の場合はminをmaxにする。
初期化時の値を制約上の最小値などに変更してください。

```C++:C++
// name:
//    update
// proc:
//    木の更新の処理
// param: 
//    k = 更新したい区間の要素のindex
//    a = 更新する値
// return:
//    なし
void update(int k, int a){
    // 根の要素数を加算して葉のindexにする
    k += n - 1;
    // 葉の値を更新する
    dat[k] = a;
    // 葉から根の値を更新する
    while(k > 0){
        // 親のindexを求める
        k = (k - 1) / 2;
        // 親の要素を、子の要素の値で更新する
        dat[k] = min(dat[k * 2 + 1], dat[k * 2 + 2]);
    }
}
```

ここからはAOJの問題を通じて見ていきましょう。   

## [DSL_2_A](https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/all/DSL_2_A)

Range Minimum Query (RMQ)   
セグメントツリーの問題です。   

a_0, a_1, a_2, a_3, ......, a_{N-1}   

の時、   
   - a_x = vと値を更新   
   - a_l, ...., a_rの中で最小の値を出力   
という問題です。   

```C++:C++
#include <bits/stdc++.h>

using namespace std;

#define INF 2147483647

int n;
int dat[2*100000 * 3];

void init(int n_){
    n = 1;
    while(n < n_) n *= 2;
    for(int i=0; i < 2 * n - 1; i++) dat[i] = INF;
}

void update(int k, int a){
    k += n - 1;
    dat[k] = a;
    while(k > 0){
        k = (k - 1) / 2;
        dat[k] = min(dat[k * 2 + 1], dat[k * 2 + 2]);
    }
}

// name:
//    query
// proc:
//    クエリの処理
//    dfsを使用して、kから始まる頂点から探索していきます。
// param: 
//    a = 求めたい区間の左端
//    b = 求めたい区間の右端
//    k = 求めたい区間の親の頂点である要素
//    l = 根の要素で最も小さいindex
//    r = 根の要素で最も大きいindex + 1
// return:
//    区間内の要素の最も小さい値
int query(int a, int b, int k, int l, int r){
    // 範囲外か判定
    if (r <= a || b <= l) return INF;
    // 区間内の最小の値を返す
    if (a <= l && r <= b) return dat[k];
    else{
        // 左辺の子を探索
        int vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
        // 右辺の子を探索
        int vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
        // 左辺、右辺で小さい値を返す
        return min(vl, vr);
    }
}

int main(void){
    int N, Q;
    cin >> N >> Q;
    init(N);

    for(int i=0; i<Q; i++){
        int t;
        cin >> t;

        if(t==0){
            int x, v;
            cin >> x >> v;
            update(x, v);
        }
        if(t==1){
            int l, r;
            cin >> l >> r;
            cout << query(l, r+1, 0, 0, n) << endl;
        }
    }
    
    return 0;
}
```

## [DSL_2_B](https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/all/DSL_2_B)

Range Sum Query
区間和の問題です。
前回と異なる箇所は区間和の箇所です。

- 初期値   
dat[i]を0で初期化します。   

```C++:C++
for(int i=0; i < 2 * n - 1; i++) dat[i] = 0;
```

- 更新   

代入でしたが、今回は+演算子でaの値を加算します。  

```C++:C++
dat[k] += a;
```

最小値はmin関数でしたが、今回は+演算子で子の合計を代入します。   

```C++:C++
dat[k] = dat[k * 2 + 1] + dat[k * 2 + 2];
```

- クエリ
`return min(vl, vr);` が `return vl + vr;` になっていますね。

```C++:C++
int query(int a, int b, int k, int l, int r){
    if (r <= a || b <= l) return 0;
    if (a <= l && r <= b) return dat[k];
    else{
        int vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
        int vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
        return vl + vr;
    }
}
```

実装したコードです。

```C++:C++
#include <bits/stdc++.h>

using namespace std;

int n;
int dat[2*100000 * 3];

void init(int n_){
    n = 1;
    while(n < n_) n *= 2;
    for(int i=0; i < 2 * n - 1; i++) dat[i] = 0;
}

void update(int k, int a){
    k += n - 1;
    dat[k] += a;
    while(k > 0){
        k = (k - 1) / 2;
        dat[k] = dat[k * 2 + 1] + dat[k * 2 + 2];
    }
}

int query(int a, int b, int k, int l, int r){
    if (r <= a || b <= l) return 0;
    if (a <= l && r <= b) return dat[k];
    else{
        int vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
        int vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
        return vl + vr;
    }
}

int main(void){
    // cout << __cplusplus << endl;
    int N, Q;
    cin >> N >> Q;
    init(N);

    for(int i=0; i<Q; i++){
        int t;
        cin >> t;

        if(t==0){
            int x, v;
            cin >> x >> v;
            x--;
            update(x, v);
        }
        if(t==1){
            int l, r;
            cin >> l >> r;
            l--;
            cout << query(l, r, 0, 0, n) << endl;
        }
    }
    
    return 0;
}
```

# 練習問題
- [B - Fenwick Tree](https://atcoder.jp/contests/practice2/tasks/practice2_b)   
- [F - Range Xor Query](https://atcoder.jp/contests/abc185/tasks/abc185_f)   

## [B - Fenwick Tree](https://atcoder.jp/contests/practice2/tasks/practice2_b)

Range Sum Query
区間和の問題です。

```C++:C++
#include <bits/stdc++.h>

using namespace std;

long long n;
vector<long long> dat;

void init(long long  n_){
    n = 1;
    while(n < n_) n *= 2;
    dat.resize(2 * n, 0);
    for(long long  i=0; i < 2 * n - 1; i++) dat[i] = 0;
}

void update(long long  k, long long a){
    k += n - 1;
    dat[k] += a;
    while(k > 0){
        k = (k - 1) / 2;
        dat[k] = dat[k * 2 + 1] + dat[k * 2 + 2];
    }
}

long long query(long long a, long long b, long long k, long long l, long long r){
    if (r <= a || b <= l) return 0;
    if (a <= l && r <= b) return dat[k];
    else{
        long long vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
        long long vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
        return vl + vr;
    }
}

int main(void){
    // cout << __cplusplus << endl;
    int N, Q;
    cin >> N >> Q;
    
    init(N);
    
    for(int i=0; i<N; i++){
        long long a;
        cin >> a;
        update(i, a);
    }

    for(int i=0; i<Q; i++){
        long long t;
        cin >> t;

        if(t==0){
            long long x, v;
            cin >> x >> v;
            update(x, v);
        }
        if(t==1){
            long long l, r;
            cin >> l >> r;
            cout << query(l, r, 0, 0, n) << endl;
        }
    }
    
    return 0;
}
```

## [F - Range Xor Query](https://atcoder.jp/contests/abc185/tasks/abc185_f)

xorのセグメントツリーです。

```C++:C++
#include <bits/stdc++.h>

using namespace std;

int n;
int dat[5*100000 * 3];

void init(int n_){
    n = 1;
    while(n < n_) n *= 2;
    for(int  i=0; i < 2 * n - 1; i++) dat[i] = 0;
}

void update(int k, int a){
    k += n - 1;
    dat[k] ^= a;
    while(k > 0){
        k = (k - 1) / 2;
        dat[k] = dat[k * 2 + 1] ^ dat[k * 2 + 2];
    }
}

int query(int a, int b, int k, int l, int r){
    if (r <= a || b <= l) return 0;
    if (a <= l && r <= b) return dat[k];
    else{
        int vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
        int vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
        return vl ^ vr;
    }
}

int main(void){
    // cout << __cplusplus << endl;
    int N, Q;
    cin >> N >> Q;
    
    init(N);
    
    for(int i=0; i<N; i++){
        int a;
        cin >> a;
        update(i, a);
    }

    for(int i=0; i<Q; i++){
        int t;
        cin >> t;

        if(t==1){
            int x, v;
            cin >> x >> v;
            x--;
            update(x, v);
        }
        if(t==2){
            int l, r;
            cin >> l >> r;
            l--;
            cout << query(l, r, 0, 0, n) << endl;
        }
    }
    
    return 0;
}
```