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 n. - Partitioning the data into light and heavy sets. - Processing 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 249 / 291 1400
Tree query 232 / 240 1500
Inversions query 145 / 162 1500
Nearest vertex 137 / 148 1600
Dominating color 98 / 115 1700
String occurences 3 91 / 102 1700
Inversions query 2 74 / 83 1700
Pair 58 / 68 1700
Sparse update 55 / 61 1800
Tree 43 / 44 1900
Range query 56 / 64 1900
String concatenation 95 / 133 1900
Subarray distance 16 / 31 2000
Chameleon 44 / 51 2000
Knapsack 82 / 109 2000
Bit counting 12 / 13 2000
Subsequence queries 24 / 30 2100
Sub-subsequence 7 / 12 2100
Delete numbers 15 / 18 2200
Mode 57 / 68 2200
Marisa is happy 14 / 55 2200
Inversions query 3 8 / 12 2300
Upperbound 4 / 6 2300
23 path 11 / 16 2300
Yet another square root decomposition problem 26 / 29 2400
Marisa plays poker 40 / 43 2400
Wonderful world 23 / 27 2400