Sqrt Decomposition
Split the array into blocks so point updates and range queries become simple block-level work instead of full rescans.
Sqrt Decomposition
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
Sqrt decomposition is the middle ground between a raw array and a full segment tree. It groups the array into blocks and stores one summary per block, which is often enough to answer queries within the required limits.
When to Use It
Use it when:
the operation is simple enough to summarize per block,
a segment tree would work but feels heavier than necessary,
the constraints are moderate and a \(O(\sqrt{n})\) tradeoff is acceptable.
Core Idea
Partition the array into blocks of size about \(\sqrt{n}\). For a range query:
scan the partial blocks at the ends directly,
use the precomputed summaries for the fully covered middle blocks.
Key Insight
Only \(O(\sqrt{n})\) blocks can be touched by one query. The only expensive work is on the two boundary blocks; the middle is handled by block summaries.
Operations / Main Technique
choose a block size,
precompute one summary per block,
answer queries by mixing direct scans and block summaries,
update one position by fixing both the raw value and its block summary.
Worked example.
For range sum with point updates, each block stores its total. A query over \([l, r]\) scans at most two partial blocks and adds the totals of the whole blocks in between.
Correctness Intuition
The range is partitioned into disjoint pieces: left partial block, some number of full blocks, and right partial block. Each piece contributes exactly once, so the total is correct.
Complexity Analysis
For block size \(B\):
point update: \(O(1)\),
range query: \(O(B + n/B)\).
Choosing \(B \approx \sqrt{n}\) gives the usual \(O(\sqrt{n})\) bound.
Implementation
The sample code implements point update and range-sum query. The same framework can support other mergeable block statistics as long as a whole block can be summarized compactly.
Common Pitfalls
Choosing a block size that is much too small or too large.
Forgetting to update the block summary after a point update.
Using sqrt decomposition when the query/update mix clearly calls for a stronger structure.
Variants / Extensions
Range add with lazy block tags.
Ordered statistics inside blocks after rebuilding.
Mo's algorithm as a different block-based philosophy for offline queries.
Practice Problems
Range sum with point updates.
Range minimum with easy block recomputation.
Frequency or order-statistic queries with sorted blocks.
References
Code
Contest-ready reference implementation for the idea explained above.
struct SqrtDecomposition {
int n;
int block_size;
vector<long long> a;
vector<long long> block_sum;
explicit SqrtDecomposition(const vector<long long>& values) : n((int)values.size()), a(values) {
block_size = max(1, (int)sqrt(n));
int blocks = (n + block_size - 1) / block_size;
block_sum.assign(blocks, 0);
for (int i = 0; i < n; ++i) {
block_sum[i / block_size] += a[i];
}
}
void point_update(int idx, long long value) {
int block = idx / block_size;
block_sum[block] += value - a[idx];
a[idx] = value;
}
long long range_sum(int l, int r) const {
long long result = 0;
while (l <= r && l % block_size != 0) {
result += a[l++];
}
while (l + block_size - 1 <= r) {
result += block_sum[l / block_size];
l += block_size;
}
while (l <= r) {
result += a[l++];
}
return result;
}
};
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.