Блог пользователя uttom

sparse Table Vs segment tree
Автор uttom, история, 8 лет назад, По-английски

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
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +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 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        → Ответить
        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
            Проголосовать: нравится 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 лет назад, # ^ |
              Проголосовать: нравится -8 Проголосовать: не нравится

            Or maybe:

            int myLog2(int x){
    return __builtin_clz(1) - __builtin_clz(x);
}
            → Ответить
      • »
        »
        »
        »
        8 лет назад, # ^ |
        ← 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.

        → Ответить
»
8 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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!

→ Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 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 лет назад, # ^ |
        Проголосовать: нравится +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].

      → Ответить