- sparse table Construct O(NlogN), range query O(1), target not updatable
- segment tree update O(logN), range query O(logN)
Segment trees can be constructed on the same order as sparse tables by updating each value
- I feel like I can make it O(N) by initializing them all together.
Segment tree range queries are certainly slower than sparse tables
- but after doing it N times, it finally catches up to the same level of order as the sparse table construction, so much so that
- If the query is Q times, there is no advantage to use sparse table only when the time constraint is OK for O(Q) and NG for O(QlogN).
- It’s hard to create that kind of restriction in a contest where you can use a variety of languages.
This page is auto-translated from /nishio/スパーステーブルとセグメント木 using DeepL. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I’m very happy to spread my thought to non-Japanese readers.