# Square Root Decomposition

Author: Benjamin Qi

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 $O((N+Q)N )$ time.

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

CPH | |||

CF | Blocking, Mo's Algo |

## Blocking

See the first example in CPH.

int n,q;vi x;ll block[450];int BLOCK;ll sum(int a) { // sum of first a elements of array in O(sqrt(n)) timell ans = 0;F0R(i,a/BLOCK) ans += block[i];FOR(i,a/BLOCK*BLOCK,a) ans += x[i];return ans;

## Batching

See the CPH section on "batch processing."

Maintain a "buffer" of the latest updates (up to $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 ($≥N $), clear it and recalculate prefix sums.

int n,q;vi x;vl cum;void build() {cum = {0};trav(t,x) cum.pb(cum.bk+t);}int main() {

## Mo's Algorithm

See CPH 27.3 and the CF link above.

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

CF | very brief description |

## Additional Notes

Low constraints (ex. $n=5⋅10_{4}$) and/or high time limits (greater than 2s) can be signs that sqrt decomp is intended.

In practice, it is not necessary to use the exact value of $n $ as a parameter, and instead we may use parameters $k$ and $n/k$ where $k$ is different from $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<n $ blocks, each of which contains $n/k>n $ elements.

As another example, if an update takes time proportional to the size of one block ($O(n/k)$) while a query takes time proportional to the number of blocks times $gn$ ($O(kgn)$) then we can set $k≈lognn $ to make both updates and queries take time $O(ngn )$.

Solutions with worse complexities are not necessarily slower (at least for problems with reasonable input sizes, ex. $n≤5⋅10_{5}$). I recall an instance where a fast $O(nn gn)$ solution passed (where $gn$ came from a BIT) while an $O(nn )$ solution did not ... So 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 sqrt decomp can be used:

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

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

## Problems

### A

Problems where the best solution I know of involves sqrt decomp.

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

JOI | Easy | View Solution | ||||

POI | Easy | |||||

YS | Normal | |||||

APIO | Hard | |||||

JOI | Hard | ## Show TagsSOS DP | View Solution | |||

Plat | Very Hard | External Sol | ||||

DMOJ | Very Hard | |||||

DMOJ | Very Hard | Check DMOJ |

### B

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

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

JOI | Normal | ## Show TagsMo's algorithm, 2D SRQ | View Solution | |||

IOI | Normal | External Sol | ||||

Plat | Hard | External Sol | ||||

CF | Hard | Check CF | ||||

TLX | Hard | Check TLX | ||||

CSA | Hard | Check CSA | ||||

Old Gold | Hard | ## Show TagsConvex Hull | External Sol | |||

CF | Very Hard | ## Show TagsConvex Hull | Check CF | |||

IOI | Very Hard | External Sol | ||||

Plat | Very Hard | External Sol | ||||

IOI | Very Hard | ## Show Tags2D SRQ | External Sol |

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

## Give Us Feedback on Square Root Decomposition!

Leave suggestions for us by making a post on the USACO Forum! Ex: Unclear sections, mislabeled problems, etc.