While solving NOV17 SEGPROD I stumbled upon this comment on codeforces. Talking about a Data Structure like Sparse Table that can answer range sum query in \theta(1). But the comment only talked about how to answer query in \theta(\log n).

Though my naive implementation of the \theta(\log n) approach did solve the problem without requiring many optimizations. I was wondering if anyone has heard of this DS before and knows the approach to solve it in \theta(1).

During the competition I had come up with the same solution as the one you have mentioned.
The basic idea of the DS:
Define M to be the midpoint of the array. 1/2 of all possible queries would be such that its Left endpoint is before M and its right endpoint is after M. So it would be efficient to keep prefix products from M to all other indices(even the ones before M). Any query which has a Left endpoint on the left of M and right endpoint on the right of M can be easily answered in O(1) using this prefix. Now the idea is to recursively do the same thing for the left and right half separately. Thatâ€™s why memory and pre-processing takes Nlogn time/mem.

This DS can subsitute anything a segment tree can do but in O(1) time. However, it takes more memory and doesnâ€™t support updates.

If I understood this correctly, then you have to find some index (whose precomputation has already been done)and for any query, you have to find an index which lies inside the query and take the prefix product and also the ("suffix ") product . ?

Exactly what I was looking for! I have couple doubts though. Why did you use size = 2^{\lceil \log n \rceil} and not size = n. Also how did you find required level lev = \lceil \log n \rceil - \lfloor \log l \oplus r \rfloor - 1

No I did not. I donâ€™t think you can optimize segment tree enough to solve this problem.
I used a different data structure which is a bit like segment tree and a bit like sparse table.

I also couldnâ€™t solve it using sparse table. Though by switching index of sparse table from [N][\log N] to [\log N][N], using bit shift instead of dividing, not storing temporary variables and let compiler handle optimizations I saw a significant improvement in running time. Probably with some optimizations around % operator it could pass

@gagan86nagpal and @nilesh3105 you both are right. I think finding the index/level is the hardest part in this technique and it took me the longest time to figure out how to do it in O(1). I rounded the size up to the nearest power of 2, because then all the mid points are like this: Lev 0- 1000, Lev 1- {0100, 1100}, Lev 2- {0010, 0110, 1010, 1110} etc. Now by intuition I came up with a solution which can find the level in O(1). Define A = L XOR R. The most significant bit of A will tell you the level. C++ has a function which hopefully runs in O(1) to find the MSB, which is __builtin_clz()

Yeah its right. operator is too costly. I got 20+ submissions before I realized this fact. When number of queries is too high use mod efficiently. Cost of if<<Cost of .