uttom's blog

sparse Table Vs segment tree
By uttom, history, 8 years ago, In English

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.

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (11)
| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Segment tree's preprocessing takes O(N) and sparse table's query takes O(1).

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I have read about sparse table LInk I have found that sparse tables query takes O(log(n)) times.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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).

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        How to achieve O(1) for sparse table RMQ? Don't you need to shift bits?

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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 :)

          → Reply
          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
              Vote: I like it -8 Vote: I do not like it

            Or maybe:

            int myLog2(int x){
    return __builtin_clz(1) - __builtin_clz(x);
}
            → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        You can achieve O(1) for sum query, take a look at this comment, there is a brief description of disjoint sparse table idea.

        → Reply
»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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!

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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)

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      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].

      → Reply