Segment Tree

Contents

概要

配列に対し、

  • 区間和
  • ある区間における最大値・最小値

等のクエリをO(log(N))で求める事のできるアルゴリズムです。

セグメント木よりも使用メモリを減らして実装可能な、Binary Indexed Tree (BIT)といったアルゴリズムもあります。

実装

下記リンクの汎用クラスライブラリがとても便利です。

遅延評価セグメント木

単純なセグメント木だと、「一定区間の各値に対して+Aする」といった区間加算処理が頻発する場合、各更新処理ごとにO(logN)の処理時間がかかってしまいます。
遅延評価セグメント木では値の参照をするまで子ノードへの更新処理を行わないことにより、高速化を図ります。

参考

関連問題