SEGPROD - Editorial

In the editorial, there have been defined two numbers I and J with the properties:
I&(2^k) =0 and j&(2^k) = 2^k-1 , 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

@gagan86nagpal

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.

1 Like

If anyone is finding the explanation a bit difficult to comprehend try this one

1 Like

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?

@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.

1 Like

can anyone please explain me a bit more how we are choosing k and x here ?

Is there any video tutorial for the same ?

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:

  • First if the query size is divisible by 2 we can just look up from our sparse table
  • otherwise we have to calculate the highest closest power of 2 to our query size by using int j = floor(log2(Ri-Li+1)). And then for the last subarray of size 2^j starting from R-(2^j)+1 till R we check our ans and also for the first subarray from L to (L+(2^j)-1) we find our answer …

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.

nice explanation!

1 Like

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 ?

What a great explanation man , thanks a ton!!

1 Like

Yes correct

https://discuss.codechef.com/questions/116992/disjoint-sparse-table

Thanks for helping mate.I got the logic now , seems trivial now :stuck_out_tongue:

I can reply and I have 66 reputations while you have 12.
Maybe you are not under some “threshold” mate.

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 :CodeChef: Practical coding for everyone

Minimum reputation to comment is 50. I just gave you 30 to help.

Thanx mate

Not that I know of, but this is a good tutorial for the data structure used here by @nilesh3105: Disjoint Sparse Table

thanks for your code. i understood everything from your code.