セグメントツリーについて調べる時間

# Intro
部分和を求める方法はいくつかあります。最初に考えた方法は、for文を使用して条件が合う場合にsum変数に合計を加える方法です。しかし、この方法は時間計算量がO(n)であるため、速度面で非効率的です。これをより速く求める方法は何でしょうか？それはセグメントツリー(Segment Tree)です。

## セグメントツリーは、
二分木構造を活用して部分和を効率的に求めるデータ構造です。他の方法としては、インデックストリー(Index Tree)があります。セグメントツリーが再帰関数で最下層のノードからルートノードまで上がる方式であるのに対し、インデックストリーはルートノードから最下層ノードへ下がる方式です。両方とも同じ問題を解決できますが、私はセグメントツリーの方が理解しやすいため、部分和問題を求める際に使用します。

セグメントツリーを作成する際には、部分和を求めたい配列より約4倍長い配列を宣言する必要があります。そして、leftノードはn*2、rightノードはn*2+1のインデックス番号を持ちます。

部分和を求める時はsum関数を使用し、n番目の数字を変更する時はupdate関数を使用します。

**セグメントツリーの例**
ツリーの生成と部分和の取得

``` java
import java.util.*;
import java.io.*;

class Main{
    static int N, M;
    static int [] arr;

    public static void main(String[] args) throws Exception {
        int [] arr = {1,3,5,7,9,11};
        SegmentTree tree = new SegmentTree(arr);
        tree.print(); // 36, 

        System.out.println(tree.sum(0,2)); // 1 + 3 + 5 = 9, but not using "for" statement
    }
}

class SegmentTree {
    int[] segmentTree;
    int n;

    public SegmentTree(int[] array) {
        n = array.length;
        segmentTree = new int[4 * n];
        build(array, 0, n - 1, 1);
    }

    public void print(){
        System.out.println(Arrays.toString(segmentTree));
    }

    private void build(int[] array, int start, int end, int index) {
        if (start == end) {
            segmentTree[index] = array[start];
        } else {
            int mid = (start + end) / 2;
            build(array, start, mid, 2 * index);
            build(array, mid + 1, end, 2 * index + 1);
            segmentTree[index] = segmentTree[2 * index] + segmentTree[2 * index + 1];
        }
    }

    public int sum(int L, int R) {
        return sum(1, 0, n - 1, L, R);
    }

    private int sum(int index, int start, int end, int L, int R) {
        if (R < start || end < L) {
            return 0;
        }
        if (L <= start && end <= R) {
            return segmentTree[index];
        }
        int mid = (start + end) / 2;
        return sum(2 * index, start, mid, L, R) + sum(2 * index + 1, mid + 1, end, L, R);
    }

    public void update(int pos, int newValue) {
        int diff = newValue - sum(pos, pos);
        update(1, 0, n - 1, pos, diff);
    }

    private void update(int index, int start, int end, int pos, int diff) {
        if (pos < start || pos > end) {
            return;
        }
        segmentTree[index] += diff;
        if (start != end) {
            int mid = (start + end) / 2;
            update(2 * index, start, mid, pos, diff);
            update(2 * index + 1, mid + 1, end, pos, diff);
        }
    }
}


```

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3824062/c6982ef5-8861-f92a-a636-28e0d03a8da9.png)


この例ではSegmentTreeクラスが提供されます。このクラスは、与えられた配列でセグメントツリーを構築し、部分和を求めるsumメソッドと値を更新するupdateメソッドを含んでいます。

- ツリーの生成: buildメソッドは与えられた配列でセグメントツリーを構築します。
- 部分和の取得: sumメソッドは、与えられた範囲 [L, R] の部分和を求めます。
- 値の更新: updateメソッドは、配列の特定の位置の値を更新し、ツリー構造を更新します。

このコードを通じて、セグメントツリーの基本的な使用方法を理解することができます。

### 0番目のインデックスから2番目のインデックスまでの合計を求める

0番目のインデックスから2番目のインデックスまでの総和を求める過程を説明します。配列 [1, 3, 5, 7, 9, 11] を基にセグメントツリーで [0, 2] 範囲の合計を求める過程です。

**セグメントツリーの構成**
配列 [1, 3, 5, 7, 9, 11] を使用したセグメントツリーの構造は次の通りです

``` plainText

               [36]
             /      \
           [9]      [27]
         /   \     /   \
       [4]   [5] [16]  [11]
      / \    / \ / \   / \
    [1] [3][5] [7][9] [11]

```

**sumクエリの実行過程**

0番目のインデックスから2番目のインデックスまでの総和を求めるクエリを実行します。sum(1, 0, 5, 0, 2) メソッドを呼び出すと仮定します。ここで 1 はツリーのルートノードのインデックス、0 と 5 は全体配列の開始と終了インデックス、0 と 2 はクエリの開始と終了インデックスです。

1. ルートノード確認:
- 現在のノード: [36]
- 範囲: [0, 5]
- クエリ範囲 [0, 2] はこのノードの範囲 [0, 5] に含まれるため、子ノードにクエリを進めます。

2. 左子ノードに移動:
- 現在のノード: [9]
- 範囲: [0, 2]
- クエリ範囲 [0, 2] はこのノードの範囲 [0, 2] に完全に含まれるため、 [9] を返します。

3. 右子ノードに移動:
- 現在のノード: [27]
- 範囲: [3, 5]
- クエリ範囲 [0, 2] はこのノードの範囲 [3, 5] と重ならないため、 0 を返します。

**結果の合算**
すべてのクエリ結果を合算すると次の通りです:
- [9] + [0] = 9

したがって、 [0, 2] 範囲の合計は 9 です。

## 全体過程の要約
1. ルートノードから開始: クエリ範囲がノード範囲と重なるため、子ノードに移動します。
2. 左子ノード: クエリ範囲とノード範囲が完全に一致するため、値を返します。
3. 右子ノード: クエリ範囲とノード範囲が重ならないため、 0 を返します。
4. 結果の合算: 返された値を合算して最終結果を得ます。

この過程を通じて、セグメントツリーを利用して部分和を効率的に求めることができます。セグメントツリーを使用することで、計算量が大幅に削減され、より高速な演算が可能となります。