Module Square root decomposition

Square root decomposition

**Frequency: 7/10** In square root decomposition, there are generally four types of techniques that are commonly used: - Mo's algorithm. - Dividing the array into smaller blocks of size $\sqrt{n}$. - Partitioning the data into light and heavy sets. - Processing $\sqrt{q}$ queries at a time. If these concepts are not clear to you, don't worry! By completing the problems below, you will gain a thorough understanding of what each of these techniques entails. In some OI-style data structure problems, you may find that the second-to-last subtask can be efficiently solved using square root decomposition.

Resources

- [CP Algorithms: Sqrt decomposition](https://cp-algorithms.com/data_structures/sqrt_decomposition.html#:~:text=Sqrt%20Decomposition%20is%20a%20method,%2Fmaximal%20element%2C%20etc.)

Problems

Frequency 391 / 445 1400
Tree query 356 / 364 1500
Inversions query 239 / 267 1500
Nearest vertex 218 / 239 1600
Dominating color 163 / 186 1700
String occurences 3 140 / 157 1700
Inversions query 2 114 / 129 1700
Pair 99 / 120 1700
Sparse update 81 / 91 1800
Tree 72 / 74 1900
Range query 93 / 107 1900
String concatenation 139 / 193 1900
Subarray distance 25 / 67 2000
Chameleon 70 / 80 2000
Knapsack 127 / 166 2000
Bit counting 24 / 27 2000
Subsequence queries 28 / 38 2100
Sub-subsequence 15 / 23 2100
Delete numbers 19 / 26 2200
Mode 81 / 106 2200
Marisa is happy 20 / 64 2200
Inversions query 3 12 / 21 2300
Upperbound 6 / 12 2300
23 path 13 / 19 2300
Yet another square root decomposition problem 33 / 39 2400
Marisa plays poker 53 / 62 2400
Wonderful world 29 / 35 2400