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 171 / 199 1400
Tree query 163 / 170 1500
Inversions query 96 / 114 1500
Nearest vertex 89 / 95 1600
Dominating color 65 / 76 1700
String occurences 3 63 / 69 1700
Inversions query 2 44 / 48 1700
Pair 39 / 48 1700
Sparse update 28 / 29 1800
Tree 22 / 22 1900
Range query 31 / 38 1900
String concatenation 62 / 85 1900
23 path 6 / 6 1900
Subarray distance 11 / 16 2000
Chameleon 33 / 39 2000
Knapsack 46 / 69 2000
Bit counting 3 / 5 2000
Subsequence queries 22 / 28 2100
Sub-subsequence 5 / 9 2100
Delete numbers 12 / 15 2200
Mode 34 / 43 2200
Inversions query 3 6 / 8 2300
Upperbound 3 / 4 2300
Yet another square root decomposition problem 16 / 19 2400
Marisa plays poker 29 / 30 2400
Wonderful world 15 / 17 2400