セグメント木
区間を管理するデータ構造の1つ。区分木、セグ木とも呼ばれる。
特徴としては、各区間に対する更新およびクエリが$ O(\log N)でできることにある。ただし、行える更新やクエリは一定の条件を満たす必要があり、問題によって実装は異なる。
なお、BITはセグメント木の一種であるが、任意の区間ではなく$ [0, i] の区間についてだけクエリ可能などの制約がある点が異なる。 概略
以下のように$ 2の累乗となるサイズ$ Nの配列に対して$ 2N - 1個の節点からなる完全二分木を考える。各区間の代表値（例えば区間の最大値）を保持しておけば、任意の区間における代表値を$ O(\log N)で計算できる。
https://gyazo.com/24f0e751af01b36a59dd1ab1b5b61c48
一点更新・区間の最大値/最小値を求める（Range Minimum Query）
セグメント木の代表的なものにRMQ(Range Minimum Query)がある。これは以下の操作を$ O(\log N)でサポートするデータ構造だ。
整数配列の任意の要素$ a_iを$ xに更新する
整数配列の任意の区間$ a_i, a_{i+1}, \ldots, a_{j}のうち最大もしくは最小の値を返す
具体的にはつぎのようなコードになる。更新のときは葉節点から順に親に向かって更新していき、クエリのときは根節点から左右の子どもの節点に再帰的にクエリをかけていけばよい。
code:RMQ.java
public class SegmentTreeRMQ {
private final int n;
private final int[] dat;
// Retrun the minimum value in the range [left, right).
public int query(int left, int right) {
return query(left, right, 0, 0, n);
}
// Return the minimum value in [a, b) overlapped with the current node, k, with the range [l, r)
private int query(int a, int b, int k, int l, int r) {
if (r <= a || b <= l) return Integer.MAX_VALUE; // no overlap
if (a <= l && r <= b) return datk; // the current node is all covered by [a, b) 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 Math.min(vl, vr);
}
// Update the value at the element located at k
public void update(int k, int value) {
k += n - 1; // the number of non-leaf nodes is 2 * n - 1 - n = n - 1
while (k > 0) {
k = (k - 1) / 2;
}
}
}
更新のときの計算量が$ O(\log N) なのは分かりやすいが、クエリのときの計算量が$ O(\log N) なのは、すこし説明が必要だろう。任意の区間の最小値を求めるとき、子孫をたどる必要があるのは、各節点の区間がクエリ対象の区間と交差し、かつ完全には含まれないときだ。たとえば節点の区間が$ [0, 3] でクエリ対象区間が$ [3, 4] の場合、調べるのは、つぎの網掛けの区間である。任意の区間は$ \log N 個の節点区間の和で表すことができるので、調べる節点の数も$ \log Nの定数倍で収まる。
https://gyazo.com/237d7620449708b5cf56c630f4988cb3
区間更新・区間の総和を求める
TBD