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 :)
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.
Well,thanks :) Here,i preprocess the log2 number.But this time .332s ! Help me brother again!And obviously thanks in advance :)
Oh! I have missed! Here is my current submission
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
Umm,
log2is 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.