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)$. asked 14 Nov, 02:26

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 preprocessing 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.
link
This answer is marked "community wiki".
answered 14 Nov, 13:13
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 . ?
(14 Nov, 13:43)
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$
(14 Nov, 15:41)
Do you have link to a tutorial on same?
(14 Nov, 15:54)
1
@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()
(14 Nov, 19:40)
@nilesh3105 I dont think there is any tutorial on this kind of DS. I dont even know what to call it.
(14 Nov, 19:41)
Kudos to you man.
(15 Nov, 00:19)
@adhyyan1252 you can read @hemanth_1's comment here. This technique is a special case of centroid decomposition :D
(15 Nov, 18:18)
2
So I figured out a formal proof for $l \oplus r$ formula. Anyone interested in a full fledged tutorial on this DS?
(yesterday)
@nilesh3105 why not!
(yesterday)
showing 5 of 9
show all
