Intro:
Let say you have given an array of integers and you have to support two operations:
point update in $$$O(1)$$$ and query in $$$O(\sqrt{N})$$$ of range sum.
Example:
$$$N = 10$$$
$$$Array = [7, 10, -2, 6, 12, 8, -10, 6, 5, 11]$$$
Now we have $$$B = \sqrt{N} = 3$$$, so make 3 sized-blocks
Array Blocks $$$= [7,10,-2] [6, 12, 8] [-10, 6, 5] [11, 0, 0]$$$
Append neutral elements to array so that each block is of size $$$B$$$ (For example if the problem is of range sum NEUTRAL = 0 whereas if the problem is range MAX then NEUTRAL = INT_MIN can be taken)
Now,
Array = [7, 10, -2, 6, 12, 8, -10, 6, 5, 11, 0, 0]
Sum = [15, 26, 1, 11]
Here $$$Sum[i]$$$ = sum of elements of $$$i^{th}$$$ block from $$$(i*B)$$$ to $$$(i*B+B-1)$$$
Update: let's say I want to update index $$$k = 4$$$ to $$$newValue = 10$$$
Then, update $$$Sum[k/B]=Sum[k/B]-Array[k]+newValue$$$ and then also update $$$Array[k]=newValue$$$
Applying to the example we have
Array = [7, 10, -2, 6, 10, 8, -10, 6, 5, 11, 0, 0]
Sum = [15, 24, 1, 11]
Query: let's say I want to get the sum from $$$L$$$ to $$$R$$$ where $$$0\le L\le R\le N$$$
Just like prefix sum view this as $$$query(L,R) = query(0,R)-query(0,L)$$$
So, problem reduces to do $$$query(R) := query(0,R)$$$
Find the block of R as $$$B_R=R/B$$$
Then, $$$Ans =$$$ $$$Sum[0...(B_R-1)]+ \sum_{i=B_R*B}^{R}Array[i]$$$
Observe, that the cost of operation is $$$ B_R+(R-B_R*B) = B_R+(R\%B) \le B + (B-1) = O(B) = O(\sqrt{N}) $$$
//C++
int query(int R) {
ll ans = 0;
for(int i = 0; i < R / block_size; i++) ans += Sum[i];
for(int i = (R / block_size) * block_size; i < R; i++) ans += Array[i];
return ans;
}
int query(int L, int R) {
return query(R) - query(L - 1);
}
