Square-Root Decomposition: Block-Based Range Queries

1. Introduction & Motivation

Square-root decomposition answers a simple question: what if you don't need the fastest possible range query, just a fast and simple one? The idea is to split an array of $n$ elements into contiguous blocks of size roughly $\sqrt{n}$. Any range operation then touches at most $O(\sqrt{n})$ full blocks, each summarized by a precomputed aggregate, plus at most two partial blocks whose elements are scanned one at a time. Both pieces cost $O(\sqrt{n})$, so the whole operation is $O(\sqrt{n})$.

That is asymptotically worse than the $O(\log n)$ a segment tree or Fenwick tree offers. The tradeoff is implementation simplicity: a block decomposition is a handful of arrays and two nested loops, with no tree recursion, no recursive build, and no subtle merge logic to get wrong. When you are under contest or interview time pressure, when the aggregate operation is unusual or hard to fit into a segment tree's merge function, or when $n$ is small enough that $\sqrt{n}$ versus $\log n$ makes no practical difference, the simpler code is often the better engineering choice. Square-root decomposition is also the foundation for other block-based techniques — most notably Mo's Algorithm for offline range queries — so the block-size intuition you build here reappears elsewhere.

2. Prerequisites

This lesson assumes comfort with basic array operations — indexing, iteration, and in-place updates — covered in Part 3: Arrays & Array ADT Operations. If point updates, linear scans, and 0-indexed slicing aren't second nature yet, that lesson is the right place to start.

You do not need to know segment trees or Fenwick trees to follow this lesson, but they are worth knowing as the $O(\log n)$ alternative to everything built here. Union-Find, Trie, Fenwick Tree & Segment Tree Decision Guide derives those structures in full; this lesson does not re-derive them, it only contrasts against them in the complexity section below.

3. A Concrete Example

4. Core Insight

Nothing about this reasoning is specific to sums. Each block's precomputed aggregate can be the result of any associative operation — minimum, maximum, greatest common divisor, bitwise XOR, or a custom combine function — because associativity is exactly what lets a full block's aggregate stand in for its individual elements without rescanning them. Only the update rule changes: for a sum, updating one element adjusts the block total by the difference; for min or max, an increase might force a full block rescan on a point update, since the previous minimum or maximum could have been the element that changed. Sum, XOR, and GCD are especially convenient because their block aggregates update in $O(1)$ per point update.

5. Block Decomposition: Point Update & Range Query

The implementation below builds block sums in $O(n)$, supports a point update in $O(1)$ (adjust one block's total by the difference between the new and old value), and a range-sum query in $O(\sqrt{n})$ (partial scan of the two boundary blocks, plus a sum over the precomputed totals of the full blocks in between). All three languages use the same 9-element array from the worked example and reproduce the same range-sum result of 34.

import math


class SqrtDecomposition:
    def __init__(self, values):
        self.n = len(values)
        self.block_size = math.isqrt(self.n) or 1
        self.data = list(values)
        num_blocks = (self.n + self.block_size - 1) // self.block_size
        self.block_sum = [0] * num_blocks
        for i, v in enumerate(self.data):
            self.block_sum[i // self.block_size] += v

    def update(self, index, new_value):
        block = index // self.block_size
        self.block_sum[block] += new_value - self.data[index]
        self.data[index] = new_value

    def range_sum(self, left, right):  # inclusive, 0-indexed
        total = 0
        start_block = left // self.block_size
        end_block = right // self.block_size
        if start_block == end_block:
            for i in range(left, right + 1):
                total += self.data[i]
            return total
        first_block_end = (start_block + 1) * self.block_size - 1
        for i in range(left, first_block_end + 1):
            total += self.data[i]
        for b in range(start_block + 1, end_block):
            total += self.block_sum[b]
        last_block_start = end_block * self.block_size
        for i in range(last_block_start, right + 1):
            total += self.data[i]
        return total


sample = [5, 2, 8, 1, 9, 3, 7, 4, 6]
sd = SqrtDecomposition(sample)
print("range_sum(1, 7):", sd.range_sum(1, 7))  # range_sum(1, 7): 34
sd.update(4, 20)
print("range_sum(1, 7) after update(4, 20):", sd.range_sum(1, 7))  # 45

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

class SqrtDecomposition {
public:
    explicit SqrtDecomposition(const std::vector<long long>& values)
        : data(values), n(static_cast<int>(values.size())) {
        block_size = std::max(1, static_cast<int>(std::sqrt(n)));
        int num_blocks = (n + block_size - 1) / block_size;
        block_sum.assign(num_blocks, 0);
        for (int i = 0; i < n; ++i) {
            block_sum[i / block_size] += data[i];
        }
    }

    void update(int index, long long new_value) {
        int block = index / block_size;
        block_sum[block] += new_value - data[index];
        data[index] = new_value;
    }

    long long rangeSum(int left, int right) const {  // inclusive, 0-indexed
        long long total = 0;
        int start_block = left / block_size;
        int end_block = right / block_size;
        if (start_block == end_block) {
            for (int i = left; i <= right; ++i) total += data[i];
            return total;
        }
        int first_block_end = (start_block + 1) * block_size - 1;
        for (int i = left; i <= first_block_end; ++i) total += data[i];
        for (int b = start_block + 1; b < end_block; ++b) total += block_sum[b];
        int last_block_start = end_block * block_size;
        for (int i = last_block_start; i <= right; ++i) total += data[i];
        return total;
    }

private:
    std::vector<long long> data;
    std::vector<long long> block_sum;
    int n;
    int block_size;
};

int main() {
    std::vector<long long> values{5, 2, 8, 1, 9, 3, 7, 4, 6};
    SqrtDecomposition sd(values);
    std::cout << "range_sum(1,7): " << sd.rangeSum(1, 7) << '\n';  // 34
    sd.update(4, 20);
    std::cout << "range_sum(1,7) after update(4,20): " << sd.rangeSum(1, 7) << '\n';  // 45
}

import java.util.Arrays;

public class SqrtDecomposition {
    private final long[] data;
    private final long[] blockSum;
    private final int n;
    private final int blockSize;

    public SqrtDecomposition(long[] values) {
        this.n = values.length;
        this.data = Arrays.copyOf(values, n);
        this.blockSize = Math.max(1, (int) Math.sqrt(n));
        int numBlocks = (n + blockSize - 1) / blockSize;
        this.blockSum = new long[numBlocks];
        for (int i = 0; i < n; i++) {
            blockSum[i / blockSize] += data[i];
        }
    }

    public void update(int index, long newValue) {
        int block = index / blockSize;
        blockSum[block] += newValue - data[index];
        data[index] = newValue;
    }

    public long rangeSum(int left, int right) { // inclusive, 0-indexed
        long total = 0;
        int startBlock = left / blockSize;
        int endBlock = right / blockSize;
        if (startBlock == endBlock) {
            for (int i = left; i <= right; i++) total += data[i];
            return total;
        }
        int firstBlockEnd = (startBlock + 1) * blockSize - 1;
        for (int i = left; i <= firstBlockEnd; i++) total += data[i];
        for (int b = startBlock + 1; b < endBlock; b++) total += blockSum[b];
        int lastBlockStart = endBlock * blockSize;
        for (int i = lastBlockStart; i <= right; i++) total += data[i];
        return total;
    }

    public static void main(String[] args) {
        long[] values = {5, 2, 8, 1, 9, 3, 7, 4, 6};
        SqrtDecomposition sd = new SqrtDecomposition(values);
        System.out.println("range_sum(1,7): " + sd.rangeSum(1, 7)); // 34
        sd.update(4, 20);
        System.out.println("range_sum(1,7) after update(4,20): " + sd.rangeSum(1, 7)); // 45
    }
}

6. Range Update Variants

The mirror-image problem is adding a delta across a whole range and reading back a single element. Rescanning every touched element on every range update would cost $O(n)$ per update, so instead each block keeps a pending value: a delta owed to every element of that block that hasn't been written into the underlying array yet. A range update that fully covers a block just increments that block's pending value in $O(1)$; only the two boundary blocks, which are partially covered, get their individual elements updated directly. A point query then simply adds the stored value to its block's pending delta.

import math


class RangeAddPointQuery:
    def __init__(self, values):
        self.n = len(values)
        self.block_size = math.isqrt(self.n) or 1
        self.data = list(values)  # committed values; partial-block updates land here
        num_blocks = (self.n + self.block_size - 1) // self.block_size
        self.pending = [0] * num_blocks  # delta owed to every element of a full block

    def range_add(self, left, right, delta):  # inclusive, 0-indexed
        start_block = left // self.block_size
        end_block = right // self.block_size
        if start_block == end_block:
            for i in range(left, right + 1):
                self.data[i] += delta
            return
        first_block_end = (start_block + 1) * self.block_size - 1
        for i in range(left, first_block_end + 1):
            self.data[i] += delta
        for b in range(start_block + 1, end_block):
            self.pending[b] += delta
        last_block_start = end_block * self.block_size
        for i in range(last_block_start, right + 1):
            self.data[i] += delta

    def point_query(self, index):
        return self.data[index] + self.pending[index // self.block_size]


sample = [5, 2, 8, 1, 9, 3, 7, 4, 6]
ra = RangeAddPointQuery(sample)
ra.range_add(1, 7, 10)
print("point_query(3):", ra.point_query(3))  # point_query(3): 11 (full block, via pending)
print("point_query(6):", ra.point_query(6))  # point_query(6): 17 (partial block, direct add)

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

class RangeAddPointQuery {
public:
    explicit RangeAddPointQuery(const std::vector<long long>& values)
        : data(values), n(static_cast<int>(values.size())) {
        block_size = std::max(1, static_cast<int>(std::sqrt(n)));
        int num_blocks = (n + block_size - 1) / block_size;
        pending.assign(num_blocks, 0);
    }

    void rangeAdd(int left, int right, long long delta) {  // inclusive, 0-indexed
        int start_block = left / block_size;
        int end_block = right / block_size;
        if (start_block == end_block) {
            for (int i = left; i <= right; ++i) data[i] += delta;
            return;
        }
        int first_block_end = (start_block + 1) * block_size - 1;
        for (int i = left; i <= first_block_end; ++i) data[i] += delta;
        for (int b = start_block + 1; b < end_block; ++b) pending[b] += delta;
        int last_block_start = end_block * block_size;
        for (int i = last_block_start; i <= right; ++i) data[i] += delta;
    }

    long long pointQuery(int index) const {
        return data[index] + pending[index / block_size];
    }

private:
    std::vector<long long> data;
    std::vector<long long> pending;
    int n;
    int block_size;
};

int main() {
    std::vector<long long> values{5, 2, 8, 1, 9, 3, 7, 4, 6};
    RangeAddPointQuery ra(values);
    ra.rangeAdd(1, 7, 10);
    std::cout << "point_query(3): " << ra.pointQuery(3) << '\n';  // 11
    std::cout << "point_query(6): " << ra.pointQuery(6) << '\n';  // 17
}

import java.util.Arrays;

public class RangeAddPointQuery {
    private final long[] data;
    private final long[] pending;
    private final int n;
    private final int blockSize;

    public RangeAddPointQuery(long[] values) {
        this.n = values.length;
        this.data = Arrays.copyOf(values, n);
        this.blockSize = Math.max(1, (int) Math.sqrt(n));
        int numBlocks = (n + blockSize - 1) / blockSize;
        this.pending = new long[numBlocks];
    }

    public void rangeAdd(int left, int right, long delta) { // inclusive, 0-indexed
        int startBlock = left / blockSize;
        int endBlock = right / blockSize;
        if (startBlock == endBlock) {
            for (int i = left; i <= right; i++) data[i] += delta;
            return;
        }
        int firstBlockEnd = (startBlock + 1) * blockSize - 1;
        for (int i = left; i <= firstBlockEnd; i++) data[i] += delta;
        for (int b = startBlock + 1; b < endBlock; b++) pending[b] += delta;
        int lastBlockStart = endBlock * blockSize;
        for (int i = lastBlockStart; i <= right; i++) data[i] += delta;
    }

    public long pointQuery(int index) {
        return data[index] + pending[index / blockSize];
    }

    public static void main(String[] args) {
        long[] values = {5, 2, 8, 1, 9, 3, 7, 4, 6};
        RangeAddPointQuery ra = new RangeAddPointQuery(values);
        ra.rangeAdd(1, 7, 10);
        System.out.println("point_query(3): " + ra.pointQuery(3)); // 11
        System.out.println("point_query(6): " + ra.pointQuery(6)); // 17
    }
}

7. Complexity Analysis

A segment tree answers both point updates and range queries, and both range updates (with lazy propagation) and range queries, in $O(\log n)$ — asymptotically better than $O(\sqrt{n})$ at every input size, and the gap widens as $n$ grows. This lesson does not re-derive that structure; see the linked guide for its build, update, and lazy-propagation logic.

What square-root decomposition buys instead is code you can write correctly in a few minutes: no recursive tree, no merge function to generalize, no lazy-propagation push-down order to get backwards. For competitive programming under time pressure, for a one-off script, for an unusual aggregate that doesn't compose cleanly in a segment tree's merge step, or for $n$ small enough that $\sqrt{n}$ and $\log n$ are both negligible next to constant factors, the simpler $O(\sqrt{n})$ structure is often the pragmatic choice. Reach for a segment tree when $n$ is large, when queries are frequent enough that the constant-factor difference between $\sqrt{n}$ and $\log n$ actually matters, or when you need to compose multiple range operations in one structure.

8. Applications & Alternatives

9. Exercises

Easy

1. Implement range-sum query with point updates using block decomposition, and verify it against a brute-force $O(n)$ scan on random inputs.
2. For $n = 1{,}000{,}000$, compute the block size $\sqrt{n}$ and state how many full blocks a worst-case query would scan.

Medium

1. Implement range-minimum query with point updates. Explain why a point update that increases a value may force a full block rescan, while a decrease never does.
2. Extend the range-minimum structure to also return the index of the minimum, not just its value.

Hard

1. Support both range updates and range queries (not just point queries) using block decomposition: combine the lazy per-block pending value from section 6 with a partial-block correction step so that a range-sum query over a mix of touched and untouched blocks still returns the right total.
2. Analyze the combined structure's complexity for both operations and compare it against a segment tree with lazy propagation.

Review rhythm: tomorrow, rebuild the point-update/range-query structure from memory and re-derive why $\sqrt{n}$ is the optimal block size; next week, implement the range-update/point-query lazy variant without looking at this page; a few weeks later, combine both into the Hard exercise's range-update/range-query structure and compare its constant factors against a segment tree on the same workload.

10. Summary Cheat Sheet

• Split an array of $n$ elements into blocks of size $b \approx \sqrt{n}$; a range operation costs $O(n/b + b)$, minimized at $b = \sqrt{n}$ for $O(\sqrt{n})$ total.
• Point update / range query: $O(1)$ update (adjust one block's aggregate), $O(\sqrt{n})$ query (full blocks via precomputed aggregate, partial blocks via direct scan).
• Range update / point query: $O(\sqrt{n})$ update (partial blocks direct, full blocks via a pending delta), $O(1)$ query (stored value plus pending delta).
• The block aggregate can be any associative operation — sum, min, max, gcd, xor — not just sum.
• Segment trees and Fenwick trees give $O(\log n)$ for the same operations at the cost of more implementation complexity; choose square-root decomposition when simplicity matters more than the asymptotic gap.
• Mo's Algorithm reuses this same block-size idea to batch-process offline range queries.