Ehsan_sShuvo's blog

Why Segment Tree here is fast?
By Ehsan_sShuvo, history, 7 years ago, In English

Here is two implementation of this problem

Using Sparse Table: Submission Using Segment Tree: Submission

Time took by Sparse Table is 0.336 s ,where Segment Tree took 0.324 s. Memory took by Sparse Table is 8732 KB ,where Segment Tree took 3640 KB.

Problem is static,thats why Sparse Table should be fast!But here i couldn't see this..Where is the problem?Could anyone please find that out ?

Thanks in advance :)

  • Vote: I like it
  • -11
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
7 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Well, the construction of the segment tree is in O(N) and solve every query in O(logN), in the sparse table the construction is in O(NlogN) and every query in O(1) supposing that you find the log2 in constant time but the complexity of the function log2 of C++ is not constant, so in your code every query is solved in O(logN), you can try to use :
__builtin_clz(1) — __builtin_clz(len)
Or preprocess the log2 of every number.

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

    Well,thanks :) Here,i preprocess the log2 number.But this time .332s ! Help me brother again!And obviously thanks in advance :)

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

      Oh! I have missed! Here is my current submission

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

        You can speed up your sparse table construction as well as queries by changing the order of the arguments. This has been discussed many times on Codeforces. Search for locality of reference, cache hits, etc

        244ms

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

    Umm, log2 is a constant-time operation. You might want to look at glibc sources: float version, double version, long double version. (There might be more implementations of each of these, but these are what I found first.)

    Of course, it's still a quite time-consuming operation.

    → Reply