Square Root Decomposition

Revision en8, by ParshuParishram, 2021-09-12 19:31:19

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);
}

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en8 English ParshuParishram 2021-09-12 19:31:19 1
en7 English ParshuParishram 2021-09-11 16:44:22 1 Tiny change: 'locks<br/>/\n\n\n**Ar' -> 'locks<br/>\n\n\n**Ar'
en6 English ParshuParishram 2021-09-11 16:43:32 45 Tiny change: '*B+B-1)$\n\n**Update' -> '*B+B-1)$\n<hr/>\n**Update'
en5 English ParshuParishram 2021-09-11 16:41:21 11 Tiny change: 'locks<br/>\nSo,<br/>\n**Array ' -> 'locks<br/>/\n\n\n**Array '
en4 English ParshuParishram 2021-09-11 16:40:26 151
en3 English ParshuParishram 2021-09-11 16:35:19 12
en2 English ParshuParishram 2021-09-11 16:34:37 16
en1 English ParshuParishram 2021-09-11 16:32:35 1696 Initial revision (published)