PROBLEM LINK:Author: Denis Anischenko DIFFICULTY:MEDIUMHARD PREREQUISITES:None (though knowledge of sparse table may be helpful for understanding) PROBLEM:Given a nonchanging array, answer queries of the form "? l r: what is $\prod\limits_{i=l}^{r} a_i$ modulo $P$ ($P$ is not necessarily prime)?" (subarray product query). The queries are online, and the constraints are so tight that an $O(1)$ per query solution is required. QUICK EXPLANATION:The intended solution does not utilize the fact that the query operation is product modulo $P$. The proposed data structure is capable of handling any associative operation query on subarray in $O(1)$ (online, provided that the array is not changing). The idea of the intended data structured is somewhat similar to the idea of a sparse table: we will precompute the operation results on some subarrays of the array so that every input query subarray can be represented as a union of constant (at most 2) number of subarrays we already know the answer for. However, the difference with the classic sparse table (used for static RMQ problem) is that the given operation $\bigoplus$ is not idemptotent: $a\bigoplus a\neq a$ for the most of $a$'s, so the union we will use must be disjoint. The operation is also not invertible, so we can't use the prefixsums approach. For each $k=1,\ldots,\lceil \log_2 N\rceil$ consider all indices of the array that are divisible by $2^k$ as "pivots". Precompute the product on subarrays whose left or right bound is a "pivot", and that do not contain any other pivots. Claim: for each $[l,r]$ query we can choose pivot element $2^k\cdot x$ in such way that we already precomputed the operation for some subarray with indices $[l, 2^k\cdot x)$, $[2^k\cdot x, r]$. EXPLANATION:Build the following data structure: for each $k=1,\ldots,\lceil \log_2 N\rceil$, for each $i=0,1,\ldots,N1$ (we use $0$indexation of the array) compute (we omit modulo $P$ for simplicity; assume that all integers are members of the ring $\mathbb{Z}_P$, with multiplication defined accordingly): $A_{k,i}=\prod\limits_j a_j\text{ for }\left\lfloor\dfrac{i}{2^k}\right\rfloor\cdot 2^k\le j\le i$ $B_{k,i}=\prod\limits_j a_j \text{ for }i\le j \le \left\lceil\dfrac{i+1}{2^k}\right\rceil\cdot 2^k1$ Here $\text{~}$ denotes bitwise negation, $\&$ denotes bitwise AND operation. The meaning of the expressions is the following:
Let's notice the following: suppose we have a query $[L, R], L\neq R$, and for selected $k$ the range of indices $[L+1, R]$ contains unique index $I$ divisible by $2^k$. Then $$B_{k,L}\cdot A_{k,R}=\prod_{i=L}^R a_i$$ Indeed, if that index of the form $I=2^k\cdot x\in[L+1, R]$ exists and is unique, then, by the meaning of the corresponding expressions above: $I=\left\lfloor\dfrac{R}{2^k}\right\rfloor\cdot 2^k$ $I=\left\lceil\dfrac{L+1}{2^k}\right\rceil\cdot 2^k$ And by definition of $B_{k,L}$ and $A_{k,R}$: $$B_{k,L}\cdot A_{k,R}=\prod_{j=L}^I a_j \cdot \prod_{j=I1}^R a_j=\prod_{j=L}^R a_j$$ Can we find the $k$ for which $I$ is unique? Surely, such $k$ exists because if for some $k$ there are $X>1$ indices divisible by $2^k$ in the range $[L+1,R]$, for $k+1$ there are $\dfrac{X}{2}$ such indices if $X$ is even and either $\left\lfloor\dfrac{X}{2}\right\rfloor$ or $\left\lceil\dfrac{X}{2}\right\rceil$ if $X$ is odd. Incrementing $k$ sufficient number of times we arrive to $X=1$. It remains to notice that $k$ can be chosen as $k=\max\limits_l: 2^l\le L\oplus R$ ($\oplus$ denotes bitwise XOR). AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here. Tester's solution can be found here. RELATED PROBLEMS:
This question is marked "community wiki".
asked 13 Nov '17, 14:09

@soumik33 See here,we precompute the prefix product for all indices which are divisible by 2^k where k=1....logN So We calulate prefix product for all subarrays from prevPivot+1 to currPrivot1. And prefix product from currPivot to nextpivot  1 So lets say for k=2: Indices:4,8,12,16,20,... So we calculate for following ranges: (1,3),(2,3),(3,3) (4,4),(4,5),(4,6),(4,7) (5,7),(6,7),(7,7) (8,8),(8,9),(8,10),(8,11) We do this for k=1..logN Now suppose a query: 16 (Here pivot are 2,4) So it can be (11)(23)(46) (Here pivot is 4) Or (13)*(46) The second one takes only 1 multiplication Consider another eg: Range 17:22 So (17:19)*(20:22) Since we have precalculated for these results for all multiples of power of 2 it can be done in O(1). note 20=4 * 5=(2^2)*5So it means we have to choose such a number in the range which is multiple of some 2^k and k is maximum(as if not we have to do more than 1 multiplication) So lets express 17:0b10001 22:10110 Exor result=111 So last set bit is 2 So pivot is multiple of 2^2 (Also note that there is only 1 multiple x for x*2^k as for x1 it is less than L and for x+1 it is greater than R) Proof for xor: See @hemanth_1 comment.Really nice explaination. Hope this helps. Plz correct me if i am wrong. answered 15 Nov '17, 22:32
Hi vivek_1998299, I want to make this clear enough. Let's say we want to find I for (14,17) 14: 0b001110 17: 0b010001 XOR: 0b011111, HEre last bit set is at 4, hence 2^4 i.e. 16. Am i correct ?
(16 Nov '17, 08:09)
Yes correct
(16 Nov '17, 10:10)

It is same as i discussed in my comment. They have used to arrays A,B(2d arrays) A(k,i) denotes product of all elements from largest value of 2^k * x (less than or equal to i) to i.So that value is floor(i/(2^k)) * 2^k (consider for i=5 ,k=2 so val=4, for i=8,k=2. Val=8) B(k,i) denotes product of all elements from i to (smallest value of 2^k * x which is just greater than i)  1.That value is ceil((i+1)/2^k)*2^k (Consider i=5 k=2 so val=8  1=7 Consider i=8,k=2. So val=12  1 =11) So as i said in prev comment : For k=2 and for i=4...N //for sake of confusion not considering from 1 (as 0 doesnt comes(1 based)) A(k,i)= [ (4,4), (4,5) , (4,6) , (4,7) , (8,8) , (8,9) ,.....] B(k,i)= [ (4,7) , (5,7) , (6,7) , (7,7) , (8,11) , (9,11) ,...] Hope this helps. Plz correct me if i am wrong. answered 16 Nov '17, 12:27

@dheeraj21 I dont think any dp solution is required for this since k is only logN Even with bruteforce you can do precomputation with complexity NlogN Just travese array logN times. (Note: for constructing A traverse from left to right , and for B right to left) Hope this helps.Correct me if i am wrong. I had a question. Do we require some awards for replying a comment? As there's no option for replying to a particular comment.Due to this ,I always have to tag/mention that person. Plz if some1 could explain this. answered 18 Nov '17, 16:34
I can reply and I have 66 reputations while you have 12. Maybe you are not under some "threshold" mate.
(18 Nov '17, 18:59)
Minimum reputation to comment is 50. I just gave you 30 to help.
(18 Nov '17, 19:32)
Thanx mate
(18 Nov '17, 22:04)

In the editorial, there have been defined two numbers I and J with the properties: I&(2^k) =0 and j&(2^k) = 2^k1 , can anyone give some examples by taking values of I , J and k to illustrate this property. Also in the Author's solution , Some different property is being used which seems to be fine answered 16 Nov '17, 08:52

Can somebody explain me how to do the pre computation (calculating A[][] and B[][]) . In sparse tables we have do simple dP to pre compute values . What can be done in this case . Is there any DP solution. Please Help? answered 18 Nov '17, 15:44
Along with brute force, Properties mentioned in "Explanation" section are heavily used. See the tester solution for more details. Also, you can go through my code which is quite similar to Tester's solution and have comments in it. Link :https://www.codechef.com/viewsolution/16283242
(18 Nov '17, 19:02)

can anyone please explain me a bit more how we are choosing k and x here ? answered 21 Nov '17, 08:17

Is there any video tutorial for the same ? answered 13 Dec '17, 14:30
Not that I know of, but this is a good tutorial for the data structure used here by @nilesh3105: Disjoint Sparse Table
(13 Dec '17, 15:49)

I was just recently readed quite well about SPARSE TABLE OPTIMIZATIONS In which we first solve the queries regarding the subarrays only of size 2^j where j varies from 0.1....log2(n). Then for every corresponding subarray size starting from 1.2..4..8..16... we build our SPARSE TABLE in an bottom up dp approach within a O(nlogn) time. Then for every query we check two things:
Can anyone please tell me that can we apply this approach here as i know this approach works well for the range min, range max, range gcd type queries etc but for the range prod queries how to handle the ans for the 2 subarrays as discussed above when the size of query is not an power of 2. answered 13 Dec '17, 23:06
