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 203 / 238 1400
Tree query 196 / 203 1500
Inversions query 117 / 134 1500
Nearest vertex 110 / 117 1600
Dominating color 81 / 95 1700
String occurences 3 76 / 83 1700
Inversions query 2 58 / 62 1700
Pair 48 / 57 1700
Sparse update 45 / 47 1800
Tree 33 / 33 1900
Range query 43 / 50 1900
String concatenation 74 / 104 1900
23 path 8 / 10 1900
Subarray distance 12 / 23 2000
Chameleon 40 / 47 2000
Knapsack 66 / 88 2000
Bit counting 6 / 8 2000
Subsequence queries 23 / 29 2100
Sub-subsequence 7 / 11 2100
Delete numbers 14 / 17 2200
Mode 47 / 59 2200
Marisa is happy 13 / 52 2200
Inversions query 3 7 / 10 2300
Upperbound 4 / 5 2300
Yet another square root decomposition problem 22 / 25 2400
Marisa plays poker 35 / 37 2400
Wonderful world 20 / 23 2400