# Square Root Decomposition

Authors: Benjamin Qi, Neo Wang

Splitting up data into smaller chunks to speed up processing.

Focus Problem – try your best to solve 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 | |||

CF | Hard | ## Show TagsHLD | |||

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!