スパーステーブルとセグメント木

セグメント木は各値を更新することでスパーステーブルと同じオーダーで構築できる

まとめて初期化することでO(N)にできる気もする

セグメント木のレンジクエリは確かにスパーステーブルより遅い

が、N回やってようやくスパーステーブルの構築と同程度のオーダーに追いつくぐらい

クエリがQ回として、O(Q)はOKでO(QlogN)だとNGな時間制約の時しかスパーステーブルを使うメリットがない

多様な言語を使えるコンテストでそういう制約を作るのが難しい