AntInLoop

Square Root (Sqrt) Decomposition

Square Root Decomposition divides an array of size n into blocks of size sqrt(n), supporting range queries and updates in O(sqrt(n)) time with minimal code complexity.

Difficulty: Medium · Interactive Visualizer · C++ / Python / Java / JS Code

Square Root (Sqrt) Decomposition

Square Root Decomposition splits an array of length $n$ into $\lceil n / B \rceil$ blocks of size $B \approx \lfloor \sqrt{n} \rfloor$ and precomputes an aggregate (sum, min, max, sorted copy, etc.) for each block. Any range query [l, r] visits at most $2B$ edge elements plus $n / B$ complete blocks, giving $O(\sqrt{n})$ per query—with a fraction of the code of a Segment Tree and support for non-mergeable operations like "count elements $\le x$ in [l, r]"!

At a Glance

| Property | Value |

| :--- | :--- |

| Build Time | $O(n)$ (or $O(n \log \sqrt{n})$ if sorting blocks) |

| Point Update | $O(1)$ (for sum) or $O(\sqrt{n})$ (for min/max/sorted block) |

| Range Query / Range Update | $O(\sqrt{n})$ |

| Auxiliary Space | $O(n)$ |

| Best Used When | Range queries/updates up to $n, q \le 10^5$, or queries Segment Trees can't easily merge |

---

How It Works (Range Sum + Point Update)

1. Choose $B = \max(1, \lfloor \sqrt{n} \rfloor)$ and compute blockSum[b] = sum of block b.

2. Point Update (idx, newVal) ($O(1)$): blockSum[idx / B] += newVal - arr[idx]; arr[idx] = newVal;.

3. Range Query [l, r] ($O(\sqrt{n})$):

  • Walk left partial block while l <= r && l % B != 0.
  • Jump complete blocks while l + B - 1 <= r: ans += blockSum[l / B]; l += B;.
  • Walk right partial block while l <= r.

Step-by-Step Trace (arr = [1, 3, 5, 2, 7, 6, 3, 1, 4], $B = 3$)

  • Blocks: B0 = [1, 3, 5] (sum 9), B1 = [2, 7, 6] (sum 15), B2 = [3, 1, 4] (sum 8).
  • Query [1, 7]: left edge arr[1] + arr[2] = 8, full block B1 = 15, right edge arr[6] + arr[7] = 4 → 27.

---

Complexity & Key Insights

  • Why $B = \sqrt{n}$: Edge work is $O(B)$ and whole-block work is $O(n / B)$; balancing $B = n / B$ gives $B = \sqrt{n}$ and $O(\sqrt{n})$ total!
  • Lazy Block Tags: For range-add updates [l, r] += delta, add delta to lazy[b] for full blocks and update individual elements on partial blocks—$O(\sqrt{n})$ range add + $O(\sqrt{n})$ range sum in 25 lines of code!

---

Practice Problems

Easy

1. Dynamic Range Sum Queries (Point Update + Range Sum)

Support update(idx, val) in $O(1)$ and query(l, r) in $O(\sqrt{n})$.

Approach: Maintain blockSum[i / B]. Time: $O(1)$ update, $O(\sqrt{n})$ query. Space: $O(n)$.

<details>

<summary>Show C++ Solution</summary>

#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>

class SqrtSum {
    std::vector<long long> a, block;
    int B;
public:
    explicit SqrtSum(const std::vector<long long>& data) : a(data) {
        int n = static_cast<int>(a.size());
        B = std::max(1, static_cast<int>(std::sqrt(n)));
        block.assign((n + B - 1) / B, 0);
        for (int i = 0; i < n; ++i) block[i / B] += a[i];
    }
    void update(int idx, long long val) {
        block[idx / B] += val - a[idx];
        a[idx] = val;
    }
    long long query(int l, int r) const {
        long long sum = 0;
        while (l <= r && l % B != 0) sum += a[l++];
        while (l + B - 1 <= r) { sum += block[l / B]; l += B; }
        while (l <= r) sum += a[l++];
        return sum;
    }
};

int main() {
    SqrtSum s({1, 3, 5, 2, 7, 6, 3, 1, 4});
    std::cout << s.query(1, 7) << " ";
    s.update(4, 10);
    std::cout << s.query(1, 7) << "\n"; // 27 30
    return 0;
}

</details>

2. Dynamic Range Minimum Queries

Support update(idx, val) and rangeMin(l, r) in $O(\sqrt{n})$.

Approach: Recompute the single affected block's minimum on update; jump whole blocks on query. Time: $O(\sqrt{n})$.

<details>

<summary>Show C++ Solution</summary>

#include <algorithm>
#include <climits>
#include <cmath>
#include <iostream>
#include <vector>

class SqrtMin {
    std::vector<int> a, bMin;
    int n, B;
public:
    explicit SqrtMin(const std::vector<int>& data) : a(data), n(static_cast<int>(data.size())) {
        B = std::max(1, static_cast<int>(std::sqrt(n)));
        bMin.assign((n + B - 1) / B, INT_MAX);
        for (int i = 0; i < n; ++i) bMin[i / B] = std::min(bMin[i / B], a[i]);
    }
    void update(int idx, int val) {
        a[idx] = val;
        int b = idx / B, start = b * B, end = std::min(n, start + B);
        bMin[b] = INT_MAX;
        for (int i = start; i < end; ++i) bMin[b] = std::min(bMin[b], a[i]);
    }
    int query(int l, int r) const {
        int ans = INT_MAX;
        while (l <= r && l % B != 0) ans = std::min(ans, a[l++]);
        while (l + B - 1 <= r) { ans = std::min(ans, bMin[l / B]); l += B; }
        while (l <= r) ans = std::min(ans, a[l++]);
        return ans;
    }
};

int main() {
    SqrtMin rmq({5, 2, 8, 6, 1, 9, 3, 7, 4});
    std::cout << rmq.query(0, 8) << " ";
    rmq.update(4, 10);
    std::cout << rmq.query(0, 8) << "\n"; // 1 2
    return 0;
}

</details>

---

Intermediate

3. Range Add & Range Sum (Lazy Block Propagation)

Support rangeAdd(l, r, delta) and rangeSum(l, r) in $O(\sqrt{n})$ each.

Approach: Store lazy[b] per block; for full blocks, increment lazy[b] += delta and blockSum[b] += delta * blockLen. On partial blocks, update a[i] and blockSum[b] directly, and always add lazy[i / B] when reading a[i].

<details>

<summary>Show C++ Solution</summary>

#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>

class SqrtLazySum {
    std::vector<long long> a, bSum, lazy;
    int n, B;
public:
    explicit SqrtLazySum(const std::vector<long long>& data) : a(data), n(static_cast<int>(data.size())) {
        B = std::max(1, static_cast<int>(std::sqrt(n)));
        int nb = (n + B - 1) / B;
        bSum.assign(nb, 0);
        lazy.assign(nb, 0);
        for (int i = 0; i < n; ++i) bSum[i / B] += a[i];
    }
    void rangeAdd(int l, int r, long long delta) {
        while (l <= r && l % B != 0) { a[l] += delta; bSum[l / B] += delta; ++l; }
        while (l + B - 1 <= r) {
            int b = l / B;
            lazy[b] += delta;
            bSum[b] += delta * B;
            l += B;
        }
        while (l <= r) { a[l] += delta; bSum[l / B] += delta; ++l; }
    }
    long long rangeSum(int l, int r) const {
        long long sum = 0;
        while (l <= r && l % B != 0) { sum += a[l] + lazy[l / B]; ++l; }
        while (l + B - 1 <= r) { sum += bSum[l / B]; l += B; }
        while (l <= r) { sum += a[l] + lazy[l / B]; ++l; }
        return sum;
    }
};

int main() {
    SqrtLazySum s({1, 2, 3, 4, 5, 6, 7, 8, 9});
    s.rangeAdd(1, 7, 10);
    std::cout << s.rangeSum(0, 8) << " " << s.rangeSum(2, 5) << "\n"; // 115 58
    return 0;
}

</details>

4. Count Elements $\le X$ in Range $[l, r]$ (Sorted Blocks)

Answer queries: how many elements in a[l..r] are $\le X$?

Approach: Keep a sorted copy of every $\sqrt{n}$-sized block. For partial blocks, scan elements directly; for full blocks, use std::upper_bound in $O(\log \sqrt{n})$! Time: $O(\sqrt{n} \log n)$ per query.

<details>

<summary>Show C++ Solution</summary>

#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>

class SqrtOrderStat {
    std::vector<int> a;
    std::vector<std::vector<int>> sortedBlocks;
    int n, B;
public:
    explicit SqrtOrderStat(const std::vector<int>& data) : a(data), n(static_cast<int>(data.size())) {
        B = std::max(1, static_cast<int>(std::sqrt(n)));
        sortedBlocks.resize((n + B - 1) / B);
        for (int i = 0; i < n; ++i) sortedBlocks[i / B].push_back(a[i]);
        for (auto& blk : sortedBlocks) std::sort(blk.begin(), blk.end());
    }
    int countLE(int l, int r, int x) const {
        int cnt = 0;
        while (l <= r && l % B != 0) { if (a[l++] <= x) ++cnt; }
        while (l + B - 1 <= r) {
            const auto& blk = sortedBlocks[l / B];
            cnt += static_cast<int>(std::upper_bound(blk.begin(), blk.end(), x) - blk.begin());
            l += B;
        }
        while (l <= r) { if (a[l++] <= x) ++cnt; }
        return cnt;
    }
};

int main() {
    SqrtOrderStat ds({7, 2, 5, 1, 9, 3, 8, 4, 6});
    std::cout << ds.countLE(1, 7, 4) << "\n"; // {2, 1, 3, 4} -> 4
    return 0;
}

</details>

---

Hard

5. Heavy-Light Value Trick: Count Triangles in an Undirected Graph in $O(E \sqrt{E})$

Given a simple undirected graph with $E$ edges, count the number of triangles $(u, v, w)$ in $O(E \sqrt{E})$ time!

Approach: Orient every edge from lower degree to higher degree (breaking ties by node ID). Every vertex now has out-degree $\le \sqrt{2E}$! For each node u, mark all out-neighbors of u, then for every out-neighbor v of u, count marked out-neighbors w of v. Time: $O(E \sqrt{E})$!

<details>

<summary>Show C++ Solution</summary>

#include <iostream>
#include <utility>
#include <vector>

long long countTriangles(int n, const std::vector<std::pair<int, int>>& edges) {
    std::vector<int> deg(n, 0);
    for (const auto& [u, v] : edges) { ++deg[u]; ++deg[v]; }

    std::vector<std::vector<int>> dag(n);
    for (const auto& [u, v] : edges) {
        if (deg[u] < deg[v] || (deg[u] == deg[v] && u < v)) dag[u].push_back(v);
        else dag[v].push_back(u);
    }

    std::vector<int> mark(n, -1);
    long long triangles = 0;
    for (int u = 0; u < n; ++u) {
        for (int v : dag[u]) mark[v] = u;
        for (int v : dag[u]) {
            for (int w : dag[v]) {
                if (mark[w] == u) ++triangles;
            }
        }
    }
    return triangles;
}

int main() {
    std::cout << countTriangles(4, {{0, 1}, {1, 2}, {2, 0}, {1, 3}, {2, 3}}) << "\n"; // 2
    return 0;
}

</details>

---

Related Algorithms

  • Mo's Algorithm — offline query-sorting companion to Sqrt Decomposition.
  • Segment Tree — $O(\log n)$ alternative for associative range operations.
  • Jump Search — applies the same $\sqrt{n}$ block sizing to searching.