スパーステーブル 構築O(NlogN)、レンジクエリO(1)、対象の更新不可 セグメント木 更新O(logN)、レンジクエリO(logN)
セグメント木は各値を更新することでスパーステーブルと同じオーダーで構築できる
- まとめて初期化することでO(N)にできる気もする
セグメント木のレンジクエリは確かにスパーステーブルより遅い
- が、N回やってようやくスパーステーブルの構築と同程度のオーダーに追いつくぐらい
- クエリがQ回として、O(Q)はOKでO(QlogN)だとNGな時間制約の時しかスパーステーブルを使うメリットがない
- 多様な言語を使えるコンテストでそういう制約を作るのが難しい