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).
nilesh3105 ,did you find range multiplicationn by segment tree ?
Hi nilesh3105, I also tried a sparse table approach but couldn’t able to manage all subtasks. Can you share your optimizations (if any)?
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
Do you have link to a tutorial on same?
@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()
@nilesh3105 I dont think there is any tutorial on this kind of DS. I dont even know what to call it.
Kudos to you man.
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 .
@adhyyan1252 you can read @hemanth_1’s comment here. This technique is a special case of centroid decomposition 
So I figured out a formal proof for l \oplus r formula. Anyone interested in a full fledged tutorial on this DS?