Segment Tree - AlgoogleN := 区間の幅 解説 Segment Treeは主に区間に対するクエリを処理するために使われる. 完全二分木で実装されるので各クエリの計算量はO(log N)になる. 自由度が高く, 区間を扱う様々なものに利用される. コードはRMQとその区間足し込みバージョンの実装. この2つの書き方をなんとなくイメージできればある程度柔軟に実装できるようになるでしょう. 区間足し込みはその区間全体に一気に足された数というのを遅延評価することで実現できる. コード struct segtree { int N, dat[2*MAX]; segtree() {} segtree(int n) { N = 1; while(N < n) N *= 2; for(int i = 0; i < 2*N-1; i++) dat[i] = inf; } // update k th element void u
プログラミングコンテストでのデータ構造
