Intro
部分和を求める方法はいくつかあります。最初に考えた方法は、for文を使用して条件が合う場合にsum変数に合計を加える方法です。しかし、この方法は時間計算量がO(n)であるため、速度面で非効率的です。これをより速く求める方法は何でしょうか？それはセグメントツリー(Segment Tree)です。
セグメントツリーは、
二分木構造を活用して部分和を効率的に求めるデータ構造です。他の方法としては、インデックストリー(Index Tree)があります。セグメントツリーが再帰関数で最下層のノードからルートノードまで上がる方式であるのに対し、インデックストリーはルートノードから最下層ノードへ下がる方式です。両方とも同じ問題を解決できますが、私はセグメントツリーの方が理解しやすいため、部分和問題を求める際に使用します。
セグメントツリーを作成する際には、部分和を求めたい配列より約4倍長い配列を宣言する必要があります。そして、leftノードはn2、rightノードはn2+1のインデックス番号を持ちます。
部分和を求める時はsum関数を使用し、n番目の数字を変更する時はupdate関数を使用します。
セグメントツリーの例
ツリーの生成と部分和の取得
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);
}
}
}
この例では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] を使用したセグメントツリーの構造は次の通りです
[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 はクエリの開始と終了インデックスです。
- ルートノード確認:
- 現在のノード: [36]
- 範囲: [0, 5]
- クエリ範囲 [0, 2] はこのノードの範囲 [0, 5] に含まれるため、子ノードにクエリを進めます。
- 左子ノードに移動:
- 現在のノード: [9]
- 範囲: [0, 2]
- クエリ範囲 [0, 2] はこのノードの範囲 [0, 2] に完全に含まれるため、 [9] を返します。
- 右子ノードに移動:
- 現在のノード: [27]
- 範囲: [3, 5]
- クエリ範囲 [0, 2] はこのノードの範囲 [3, 5] と重ならないため、 0 を返します。
結果の合算
すべてのクエリ結果を合算すると次の通りです:
- [9] + [0] = 9
したがって、 [0, 2] 範囲の合計は 9 です。
全体過程の要約
- ルートノードから開始: クエリ範囲がノード範囲と重なるため、子ノードに移動します。
- 左子ノード: クエリ範囲とノード範囲が完全に一致するため、値を返します。
- 右子ノード: クエリ範囲とノード範囲が重ならないため、 0 を返します。
- 結果の合算: 返された値を合算して最終結果を得ます。
この過程を通じて、セグメントツリーを利用して部分和を効率的に求めることができます。セグメントツリーを使用することで、計算量が大幅に削減され、より高速な演算が可能となります。