Sqrt Decomposition and Mo's Algorithm
Split the array into blocks of about sqrt(n) to balance update and query costs, and reorder offline range queries so two moving pointers do little work in total.
The problem
You have an array of numbers and queries. Two shapes appear again and again.
- Online with updates. "Change one element" and "sum of ", mixed in any order.
- Offline, no updates. "How many distinct values are in ?" You may read all queries first.
1 of 7