セグ木と似たようなことが出来るアルゴリズムまとめ

セグ木(区分木 / Segment tree)は前処理と引き換えにある種の区間クエリが O(N) ではなく O(logN) で出来る競プロ界隈でよく見かけるアルゴリズムである. 似たようなことが出来るアルゴリズムがいくつかあるので、違いをまとめてみた.

Segment tree

O(N²) は通らないけど、O(NlogN) は通るという制約の問題は多いので、何かと頼りになる.

• 対応している操作: 結合則が成り立つ操作、+, Min/Max, GCD, Bitwise Xor/Or 等
• 必要なメモリ量: O(2N)～O(4N)
• 前計算の計算量: O(N)
• 更新の計算量: O(logN)
• クエリの計算量: O(logN)

BIT (Binary indexed tree) / Fenwick tree

制約がきついが実装は簡単で、定数倍も軽め.

• 対応している操作: + のみ
• 必要なメモリ量: O(N)
• 前計算の計算量: O(0)
• 更新の計算量: O(logN)、加算のみで指定の値に更新とかは出来ない
• クエリの計算量: O(logN)

Sparse table

更新ができず、操作に冪等性が必要と制約が厳しいが、クエリの計算量 O(1) は魅力.

• 対応している操作: 結合則が成り立ち冪等性を持つ操作、Min/Max, GCD, Bitwise Or 等
• 必要なメモリ量: O(NlogN)
• 前計算の計算量: O(NlogN)
• 更新の計算量: 更新は不可能
• クエリの計算量: O(1)

Disjoint sparse table

Sparse table の上位互換? まだ調査/実装してないのでよく分からない.

• 対応している操作: 結合則が成り立つ操作、+, Min/Max, GCD, Bitwise Xor/Or 等
• 必要なメモリ量: O(NlogN)
• 前計算の計算量: O(NlogN)
• 更新の計算量: 更新は不可能
• クエリの計算量: O(1)

Sqrt tree

今見つけたところなのでほとんど分からないけど、今まで聞いたことなかったということは有名ではない?

• 対応している操作: 結合則が成り立つ操作、+, Min/Max, GCD, Bitwise Xor/Or 等
• 必要なメモリ量: O(NloglogN)
• 前計算の計算量: O(NloglogN)
• 更新の計算量: O(√N)
• クエリの計算量: O(1)