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 445 / 507 1400
Tree query 399 / 408 1500
Inversions query 277 / 306 1500
Nearest vertex 242 / 270 1600
Dominating color 184 / 209 1700
String occurences 3 159 / 179 1700
Inversions query 2 132 / 149 1700
Pair 116 / 138 1700
Sparse update 98 / 109 1800
Tree 84 / 86 1900
Range query 110 / 127 1900
String concatenation 160 / 215 1900
Subarray distance 31 / 76 2000
Chameleon 78 / 89 2000
Knapsack 145 / 189 2000
Bit counting 29 / 32 2000
Subsequence queries 36 / 45 2100
Sub-subsequence 18 / 26 2100
Delete numbers 20 / 27 2200
Mode 89 / 115 2200
Marisa is happy 27 / 72 2200
Inversions query 3 14 / 28 2300
Upperbound 8 / 13 2300
23 path 14 / 19 2300
Yet another square root decomposition problem 34 / 40 2400
Marisa plays poker 57 / 66 2400
Wonderful world 32 / 38 2400