Square Root Decomposition
Divide array into blocks of size ~√n to answer queries faster.
data-structuresdecompositionUpdated 2025-09-01
Complexity
- Query O(√n)
- Update O(1) or O(√n)
Use Cases
- Range sum
- Frequency queries
Divide array into blocks of size ~√n to answer queries faster.