Square Root Decomposition
Author: Benjamin Qi
Splitting up data into smaller chunks to speed up processing.
Focus Problem – read through this problem before continuing!
You should already have done this problem in Point Update Range Sum, but here we'll present two more approaches. Both run in time.
Resources | |||
---|---|---|---|
CPH | |||
CF | Blocking, Mo's Algo |
Blocking
See the first example in CPH.
int n,q;vi x;ll block[450];int BLOCK;ll sum(int a) { // sum of first a elements of array in O(sqrt(n)) timell ans = 0;F0R(i,a/BLOCK) ans += block[i];FOR(i,a/BLOCK*BLOCK,a) ans += x[i];return ans;
Batching
See the CPH section on "batch processing."
Maintain a "buffer" of the latest updates (up to ). The answer for each sum query can be calculated with prefix sums and by examining each update within the buffer. When the buffer gets too large (), clear it and recalculate prefix sums.
int n,q;vi x;vl cum;void build() {cum = {0};trav(t,x) cum.pb(cum.bk+t);}int main() {
Mo's Algorithm
See CPH 27.3 and the CF link above.
Resources | |||
---|---|---|---|
CF | very brief description |
Additional Notes
Low constraints (ex. ) and/or high time limits (greater than 2s) can be signs that sqrt decomp is intended.
In practice, it is not necessary to use the exact value of as a parameter, and instead we may use parameters and where is different from . The optimal parameter depends on the problem and input. For example, if an algorithm often goes through the blocks but rarely inspects single elements inside the blocks, it may be a good idea to divide the array into blocks, each of which contains elements.
As another example, if an update takes time proportional to the size of one block () while a query takes time proportional to the number of blocks times () then we can set to make both updates and queries take time .
Solutions with worse complexities are not necessarily slower (at least for problems with reasonable input sizes, ex. ). I recall an instance where a fast solution passed (where came from a BIT) while an solution did not ... So constant factors are important!
On Trees
The techniques mentioned in the blogs below are extremely rare but worth a mention.
Resources | |||
---|---|---|---|
CF | |||
CF |
Some more discussion about how sqrt decomp can be used:
Resources | |||
---|---|---|---|
CF | format isn't great but tree example is ok |
Problems
A
Problems where the best solution I know of involves sqrt decomp.
Status | Source | Problem Name | Difficulty | Tags | |||||
---|---|---|---|---|---|---|---|---|---|
CF | Easy | Show TagsSqrt | |||||||
JOI | Easy | Show TagsSqrt | |||||||
POI | Easy | Show TagsSqrt | |||||||
YS | Normal | Show TagsSqrt | |||||||
APIO | Hard | Show TagsSqrt | |||||||
JOI | Hard | Show TagsSOS DP | |||||||
Plat | Very Hard | Show TagsSqrt | |||||||
DMOJ | Very Hard | Show TagsSqrt | |||||||
DMOJ | Very Hard | Show TagsSqrt | |||||||
B
Problems that can be solved without it. But you might as well try to use it!!
Status | Source | Problem Name | Difficulty | Tags | |||||
---|---|---|---|---|---|---|---|---|---|
JOI | Normal | Show Tags2DRQ, Mo's Algorithm | |||||||
IOI | Normal | Show TagsSqrt | |||||||
Plat | Hard | Show TagsSqrt | |||||||
CF | Hard | Show TagsSqrt | |||||||
TLX | Hard | Show TagsSqrt | |||||||
CSA | Hard | Show TagsSqrt | |||||||
Old Gold | Hard | Show TagsConvex Hull | |||||||
CF | Very Hard | Show TagsConvex Hull | |||||||
IOI | Very Hard | Show TagsSqrt | |||||||
Plat | Very Hard | Show TagsSqrt | |||||||
IOI | Very Hard | Show Tags2DRQ | |||||||
Module Progress:
Join the USACO Forum!
Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!