Square Root Decomposition

Block partitioning, range queries, range updates, Mo's algorithm connection, and choosing block size.

Block partitioning, range queries, range updates, Mo's algorithm connection, and choosing block size. Explain the trade-off rather than presenting sqrt(n) as universally optimal.

Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):

Each operation costs about 2B element steps plus n/B block steps; B = √n minimises the sum (about 2√n + √n). If updates are rarer than queries, or block work is cheaper than element work, a different B wins — measure. The run shows every block size is *correct*; only the cost changes.

#include <bits/stdc++.h>
using namespace std;

struct SqrtSum {
    int n, B; vector<long long> a, block, lazy;
    SqrtSum(const vector<long long>& v, int blockSize) : n((int)v.size()), B(blockSize), a(v), block((n + B - 1) / B, 0), lazy((n + B - 1) / B, 0) {
        for (int i = 0; i < n; ++i) block[i / B] += a[i];
    }
    void add(int l, int r, long long v) {                                // [l, r)
        while (l < r && l % B) { a[l] += v; block[l / B] += v; ++l; }      // partial block on the left
        while (l + B <= r) { lazy[l / B] += v; block[l / B] += v * B; l += B; }   // whole blocks: O(1) each
        while (l < r) { a[l] += v; block[l / B] += v; ++l; }               // partial block on the right
    }
    long long sum(int l, int r) const {
        long long s = 0;
        while (l < r && l % B) s += a[l] + lazy[l / B], ++l;
        while (l + B <= r) s += block[l / B], l += B;
        while (l < r) s += a[l] + lazy[l / B], ++l;
        return s;
    }
};

int main() {
    mt19937 rng(21); int n = 1000;
    vector<long long> v(n); for (auto& x : v) x = rng() % 100;
    for (int B : {4, 32, 250}) {
        SqrtSum s(v, B); vector<long long> brute = v;
        fo
…

block size 4: correct on 5000 operations; worst-case cost per op about 258 steps
block size 32: correct on 5000 operations; worst-case cost per op about 95 steps
block size 250: correct on 5000 operations; worst-case cost per op about 504 steps

Quiz

? Why is B = √n a common block size?
+ It balances the per-element work (≈ 2B) against the per-block work (≈ n/B). :: Minimises B + n/B.
- It is required for correctness. :: All block sizes gave correct answers in the run.
- It uses the least memory. :: Memory differs little.
- It makes queries O(1). :: No.

? With n = 1000 and B = 32, a range operation touches roughly…
+ 2·32 elements and 1000/32 ≈ 31 blocks :: About 95 steps, as printed.
- 1000 elements :: Only partial blocks are visited element by element.
- log₂ 1000 nodes :: That is a segment tree.
- 32 elements :: Plus the blocks in between.

? When might a block size other than √n be better?
+ When updates and queries have different frequencies or costs :: Tune to the workload.
- Never :: It is a heuristic, not a law.
- Only when n is prime :: Unrelated.
- Only with Mo's algorithm :: Applies generally.