Segment Tree
作成日：2019.04.05
最終更新日：2019.04.05
目次
計算量
要素数が$N$、モノイドの演算に$O(T)$かかるとすると、計算量は$O(T \log N)$である。
空間計算量は$O(N)$である。
原理・計算量解析
区間更新や区間取得を高速に行うために、二分探索を念頭に置いて区間を分割する。
これは、半開区間$[0,N)$を二分探索する時に現れ得る区間それぞれを頂点とみなし、半分に分割した区間に対応する頂点が子となるようにした二分木を用意するということである。
そして、クエリの区間の両端の位置をそれぞれ二分探索するイメージでその木を下っていく。
下っていく途中、クエリの区間に覆われる区間に対応する頂点が子にあれば、その子においてクエリを処理する。
訪れる頂点は境界をまたぐ区間に対応する頂点であり、その数は高々$2\log N$個であるから計算量は$O(\log N)$となる。
より詳しくは動画を参照のこと。
要素数$N$は原理的にはいくつでも良いのだが、完全二分木になり実装が楽などの利点があるので2の冪にされることがほとんどである。