### uttom's blog

By uttom, history, 8 years ago,

For preprocessing in segment tree and sparse table Both takes O(nlogn) times. And in every query both takes O(log(n)) times. But How sparse Table faster than Segment tree? Thanks in Advance.

• 0

| Write comment?
 » 8 years ago, # |   0 Segment tree's preprocessing takes O(N) and sparse table's query takes O(1).
•  » » 8 years ago, # ^ |   0 I have read about sparse table LInk I have found that sparse tables query takes O(log(n)) times.
•  » » » 8 years ago, # ^ |   +3 I haven't seen sparse table for range sum query, maybe that's where you need O(logN) per query but for range minimum/range maximum you can achieve O(1) and for range GCD you can achieve O(GCD_Complexity).
•  » » » » 8 years ago, # ^ |   0 How to achieve O(1) for sparse table RMQ? Don't you need to shift bits?
•  » » » » » 8 years ago, # ^ |   0 Here is my implementation of sparse table — http://ideone.com/Vok0KR. It works if taking a value multiple times doesn't change the result, like min, max, gcd and unlike sum. I guess the tutorial linked by uttom is a bit different from what I use and thus runs slower but works for more types of queries.PS: Note that in my code, the log2() function is slow and it's better to precompute logarithms beforehand :)
•  » » » » » » 8 years ago, # ^ |   -8 Or maybe: int myLog2(int x){ return __builtin_clz(1) - __builtin_clz(x); } 
•  » » » » 8 years ago, # ^ | ← Rev. 2 →   0 You can achieve O(1) for sum query, take a look at this comment, there is a brief description of disjoint sparse table idea.
•  » » » » » 6 years ago, # ^ | ← Rev. 3 →   0 ..
 » 8 years ago, # |   +3 Lets show them with .sparse table segment tree Here you can find something more!
•  » » 8 years ago, # ^ |   0 How, is querying sparse tabke O(1) ? . Let's say I want to query a interval of length n. Then, the number of operations I would have to do will be equal to number of set bits in n right ? In worst case, the number of set bits in n could be log(n)
•  » » » 8 years ago, # ^ |   +5 Let's t[d][i] minimum in range [i; i+2d). Query in range l, r find minimum. Take maximal d that 2d  ≤  r - l + 1. Answer will be minimum t[d][l] and t[d][r - 2d + 1].