COLLECT alternative

My bad. Put the n in there by mistake.

please provide any link to learn this new method

Pls provide a good link !!

Square root decomposition can be thought of as follows. Arrange your numbers in a (square) grid. So thats a ceil(rootN) x ceil(rootN) grid. Now fill in the numbers in row major order, and maintain rowsums. When you need to find sum of range (i…j), divide the range into : i’s row, j’s row, and all rows inbetween. You can find the sum now in time O(length of i’s row) + O(number of rows between i and j) + O(length of j’s row). If your grid is of the rootN x rootN type, all these three will be O(rootN). Thus, such solutions use time complexity O(rootN) per query.

4 Likes

This is new, and fascinating!! Lets get everything (LHS and RHS) “modulo moD” and try to understand it.

The above is basically saying something like, if you write “moD = i * q + r”, then take modulo moD, you get something like 0 = i * q + r => 1/i = -q * 1/r (modulo moD). Since r < i, we would have already computing “1/r” earlier.

Wow, this is amazing - thanks for pointing out!

2 Likes