# Square Root Decomposition

Authors: Benjamin Qi, Neo Wang

Splitting up data into smaller chunks to speed up processing.

Focus Problem – read through this problem before continuing!

You should already have done this problem in Point Update Range Sum, but here we'll present two more approaches. Both run in $\mathcal{O}(Q\sqrt N)$ time.

Resources | ||||
---|---|---|---|---|

CPH | ||||

CF | Blocking, Mo's Algo |

## Blocking

We partition the array into blocks of size
$\texttt{blocksz}=\lfloor \sqrt{N} \rfloor$. Each block stores the sum of elements within it, and allows for the creation of
corresponding `update`

and `query`

operations.

**Update Queries:** $\mathcal{O}(1)$

To update an element at location $x$, first find the corresponding block using the formula $\frac{x}{\texttt{blocksz}}$.

Then, apply the corresponding difference between the element currently stored at $x$ and the element we want to change it to.

**Sum Queries:** $\mathcal{O}(\sqrt{N})$

To perform a sum query from $[0\ldots r]$, calculate

where $\texttt{blocks}[i]$ represents the total sum of the $i$-th block, the $i$-th block represents the sum of the elements from the range $[i\cdot \texttt{blocksz},(i + 1)\cdot \texttt{blocksz})$, and $R=\left\lfloor \frac{r}{\texttt{blocksz}} \right\rfloor$.

Finally, $\sum_{i=l}^{r} \texttt{nums}[i]$ is the difference between the two sums $\sum_{i=0}^{r}\texttt{nums}[i]$ and $\sum_{i=0}^{l-1}\texttt{nums}[i]$, which each are calculated in $\mathcal{O}(\sqrt N)$.

C++

Code Snippet: C++ Short Template (Click to expand)ll blocks[450]; // 450^2 > 2e5int nums[(int)(2e5 + 1)];int block_sz;void upd(int x, int v) { // O(1) updateblocks[x / block_sz] -= nums[x];nums[x] = v;blocks[x / block_sz] += nums[x];

## Batching

See the CPH section on batch processing.

Maintain a "buffer" of the latest updates (up to $\sqrt N$). The answer for each sum query can be calculated with prefix sums and by examining each update within the buffer. When the buffer gets too large ($\ge \sqrt N$), clear it and recalculate prefix sums.

C++

Code Snippet: C++ Short Template (Click to expand)int n, q;vi x;vector<long long> cum;void build() {cum = {0};for(const auto &t : x) cum.pb(cum.back() + t);}

## Mo's Algorithm

Resources | ||||
---|---|---|---|---|

CF |
| |||

CPH |

## Additional Notes

Low constraints (ex. $n=5\cdot 10^4$) and/or high time limits (greater than 2s) can be signs that square root decomposition is intended.

In practice, it is not necessary to use the exact value of $\sqrt n$ as a parameter, and instead we may use parameters $k$ and $n/k$ where $k$ is different from $\sqrt n$. The optimal parameter depends on the problem and input. For example, if an algorithm often goes through the blocks but rarely inspects single elements inside the blocks, it may be a good idea to divide the array into $k<\sqrt n$ blocks, each of which contains $n/k > \sqrt n$ elements.

If an update takes time proportional to the size of one block ($\mathcal{O}(n/k)$) while a query takes time proportional to the number of blocks times $\log n$ ($\mathcal{O}(k\log n)$) then we can set $k\approx \sqrt{\frac{n}{\log n}}$ to make both updates and queries take time $\mathcal{O}(\sqrt{n\log n})$.

Solutions with worse complexities are not necessarily slower (at least for problems with reasonable input sizes, ex. $n\le 5\cdot 10^5$). I recall an instance where a fast $\mathcal{O}(n\sqrt n\log n)$ solution passed (where $\log n$ came from a BIT) while an $\mathcal{O}(n\sqrt n)$ solution did not. Constant factors are important!

## On Trees

The techniques mentioned in the blogs below are extremely rare but worth a mention.

Resources | ||||
---|---|---|---|---|

CF | ||||

CF |

Some more discussion about how square root decomposition can be used:

Resources | ||||
---|---|---|---|---|

CF | format isn't great but tree example is ok |

## Problems

### Set A

Problems where the best solution involves square root decomposition.

Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|

CF | Easy | ## Show TagsSqrt | |||

JOI | Easy | ## Show TagsSqrt | |||

POI | Easy | ## Show TagsSqrt | |||

CF | Easy | ## Show TagsSqrt | |||

CF | Easy | ## Show TagsSqrt | |||

YS | Normal | ## Show TagsSqrt | |||

CF | Normal | ## Show TagsMo's Algorithm | |||

APIO | Hard | ## Show TagsSqrt | |||

JOI | Hard | ## Show TagsSOS DP | |||

Plat | Very Hard | ## Show TagsSqrt | |||

DMOJ | Very Hard | ## Show TagsSqrt | |||

DMOJ | Very Hard | ## Show TagsSqrt |

### Set B

Problems that can be solved without it. But you might as well try to use it!

Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|

JOI | Normal | ## Show Tags2DRQ, Mo's Algorithm | |||

IOI | Normal | ## Show TagsSqrt | |||

Plat | Hard | ## Show TagsSqrt | |||

CF | Hard | ## Show TagsSqrt | |||

TLX | Hard | ## Show TagsSqrt | |||

CSA | Hard | ## Show TagsSqrt | |||

Old Gold | Hard | ## Show TagsConvex | |||

CF | Very Hard | ## Show TagsConvex | |||

IOI | Very Hard | ## Show TagsSqrt | |||

Plat | Very Hard | ## Show TagsSqrt | |||

IOI | Very Hard | ## Show Tags2DRQ |

### Module Progress:

### Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!