PrevNext
Rare
 0/14

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 O((N+Q)N)O((N+Q)\sqrt N) time.

Blocking

See the first example in CPH.

1int n,q;
2vi x;
3ll block[450];
4int BLOCK;
5
6ll sum(int a) { // sum of first a elements of array in O(sqrt(n)) time
7 ll ans = 0;
8 F0R(i,a/BLOCK) ans += block[i];
9 FOR(i,a/BLOCK*BLOCK,a) ans += x[i];
10 return ans;

Batching

See the CPH section on "batch processing."

Maintain a "buffer" of the latest updates (up to N\sqrt N). 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 (N\ge \sqrt N), clear it and recalculate prefix sums.

1int n,q;
2vi x;
3vl cum;
4
5void build() {
6 cum = {0};
7 trav(t,x) cum.pb(cum.bk+t);
8}
9
10int main() {

Mo's Algorithm

See CPH 27.3 and the CF link above.

Resources
CFvery brief description

Additional Notes

Low constraints (ex. n=5104n=5\cdot 10^4) and/or high time limits (greater than 2s) can be signs that sqrt decomp is intended.

CPH 262:

In practice, it is not necessary to use the exact value of n\sqrt n as a parameter, and instead we may use parameters kk and n/kn/k where kk is different from n\sqrt n. 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 k<nk<\sqrt n blocks, each of which contains n/k>nn/k > \sqrt n elements.

As another example, if an update takes time proportional to the size of one block (O(n/k)O(n/k)) while a query takes time proportional to the number of blocks times logn\log n (O(klogn)O(k\log n)) then we can set knlognk\approx \sqrt{\frac{n}{\log n}} to make both updates and queries take time O(nlogn)O(\sqrt{n\log n}).

Solutions with worse complexities are not necessarily slower (at least for problems with reasonable input sizes, ex. n5105n\le 5\cdot 10^5). I recall an instance where a fast O(nnlogn)O(n\sqrt n\log n) solution passed (where logn\log n came from a BIT) while an O(nn)O(n\sqrt n) solution did not ... So constant factors are important!

On Trees

The techniques mentioned in the blogs below are extremely rare but worth a mention.

Some more discussion about how sqrt decomp can be used:

Resources
CFformat isn't great but tree example is ok

Problems

A

Problems where the best solution I know of involves sqrt decomp.

StatusSourceProblem NameDifficultyTagsSolution
YSNormal
APIOHard
PlatVery HardExternal Sol
DMOJVery Hard
DMOJVery HardCheck DMOJ

B

Problems that can be solved without it. But you might as well try to use it!!

StatusSourceProblem NameDifficultyTagsSolution
PlatHardExternal Sol
CFHardCheck CF
TLXHardCheck TLX
CSAHardCheck CSA
Old GoldHard
Show Tags

Convex Hull

External Sol
CFVery Hard
Show Tags

Convex Hull

Check CF
IOIVery HardExternal Sol
PlatVery HardExternal Sol

Module Progress:

Give Us Feedback on Square Root Decomposition!

PrevNext