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.
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.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3757 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 171 |
| 2 | awoo | 165 |
| 3 | adamant | 164 |
| 4 | TheScrasse | 159 |
| 5 | maroonrk | 155 |
| 6 | nor | 154 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
Segment tree's preprocessing takes O(N) and sparse table's query takes O(1).
I have read about sparse table LInk I have found that sparse tables query takes O(log(n)) times.
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).
How to achieve O(1) for sparse table RMQ? Don't you need to shift bits?
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 :)
Or maybe:
You can achieve O(1) for sum query, take a look at this comment, there is a brief description of disjoint sparse table idea.
..
Lets show them with <preprocess , query , update an element>.
sparse table <O(nlgn) , O(1) , O(nlgn)>
segment tree <O(n) , O(lgn) , O(lgn) >
Here you can find something more!
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)
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].