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](sum9),B1 = [2, 7, 6](sum15),B2 = [3, 1, 4](sum8). - Query
[1, 7]: left edgearr[1] + arr[2] = 8, full blockB1 = 15, right edgearr[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, adddeltatolazy[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.