Chapter 92

Home

Sqrt Decomposition

Divide an array into blocks of size √N. Precompute an aggregate (sum, min, max) for each block. Range queries: sum whole blocks in O(√N), handle partial edges directly. Point updates: recompute one block in O(√N).

Range Sum with Sqrt Decomposition

C++ — sqrt decomposition for range sum

struct SqrtDecomp {
    vector arr, block;
    int B;

    SqrtDecomp(vector& a) {
        arr = a;
        int n = a.size();
        B = sqrt(n) + 1;
        block.assign(B, 0);
        for (int i = 0; i < n; i++)
            block[i / B] += arr[i];
    }

    long long query(int l, int r) {
        long long sum = 0;
        int bl = l / B, br = r / B;
        if (bl == br) {
            for (int i = l; i <= r; i++) sum += arr[i];
        } else {
            for (int i = l; i < (bl + 1) * B; i++) sum += arr[i];
            for (int i = bl + 1; i < br; i++) sum += block[i];
            for (int i = br * B; i <= r; i++) sum += arr[i];
        }
        return sum;
    }

    void update(int idx, long long val) {
        int b = idx / B;
        block[b] += val - arr[idx];
        arr[idx] = val;
    }
};

// Query: O(√N). Update: O(√N). Memory: O(N + √N).

💡 When to use sqrt decomposition

When segment tree is overkill, or you need a balance between query and update speed. Also useful when the operation isn't easily composed (like "mode of range").

Key Takeaways