前回の記事では方法 1 について記述しました。 今回はそれを発展させた方法 2 について記述します。 方針 方法 2 では、方法 1 の状態からさらに、子ノードが 1 個のノードを省略します。 下図は、クエリ (1) によりインデックス の値が更新されたときの例で…

概要 通常のセグメント木では、管理対象の列の項数 を固定して完全二分木を構築するため、初期化に時間計算量および空間計算量 を要し、1 回のクエリあたり時間計算量 を要する。 したがって、 として利用できる値には計算機資源上の制限があり、列のインデ…