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