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.

# | User | Rating |
---|---|---|

1 | ecnerwala | 3649 |

2 | Benq | 3581 |

3 | orzdevinwang | 3570 |

4 | Geothermal | 3569 |

4 | cnnfls_csy | 3569 |

6 | tourist | 3565 |

7 | maroonrk | 3531 |

8 | Radewoosh | 3521 |

9 | Um_nik | 3482 |

10 | jiangly | 3468 |

# | User | Contrib. |
---|---|---|

1 | maomao90 | 174 |

2 | awoo | 164 |

3 | adamant | 162 |

4 | TheScrasse | 159 |

5 | nor | 158 |

6 | maroonrk | 156 |

7 | -is-this-fft- | 151 |

8 | SecondThread | 147 |

9 | orz | 146 |

10 | pajenegod | 145 |

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.

↑

↓

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/24/2024 23:06:47 (k2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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+2^{d}). Query in range l, r find minimum. Take maximal d that 2^{d}≤r-l+ 1. Answer will be minimumt[d][l] andt[d][r- 2^{d}+ 1].