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 295 / 344 1400
Tree query 272 / 279 1500
Inversions query 177 / 200 1500
Nearest vertex 163 / 181 1600
Dominating color 123 / 144 1700
String occurences 3 104 / 118 1700
Inversions query 2 89 / 100 1700
Pair 75 / 88 1700
Sparse update 63 / 70 1800
Tree 51 / 53 1900
Range query 67 / 79 1900
String concatenation 116 / 161 1900
Subarray distance 20 / 42 2000
Chameleon 54 / 62 2000
Knapsack 101 / 130 2000
Bit counting 14 / 17 2000
Subsequence queries 26 / 35 2100
Sub-subsequence 8 / 15 2100
Delete numbers 15 / 20 2200
Mode 64 / 84 2200
Marisa is happy 18 / 62 2200
Inversions query 3 8 / 13 2300
Upperbound 4 / 7 2300
23 path 11 / 16 2300
Yet another square root decomposition problem 27 / 32 2400
Marisa plays poker 46 / 51 2400
Wonderful world 25 / 30 2400