每日算法 — 使用java实现分块算法：区间查询与修改的平方根分解策略

引言

在处理大规模数组的区间查询与修改问题时，线段树与树状数组是常见的高效数据结构。然而，当操作类型复杂、难以用简单的懒标记维护时，分块算法（Sqrt Decomposition）以其优雅的平方根分解思想，提供了一种代码简洁、逻辑清晰的替代方案。本文将用 Java 实现分块算法，讲解其区间求和、区间修改的核心机制，并分析其时间复杂度。

核心思想

分块算法的核心是将长度为 n 的数组划分为约 √n 个块，每块包含约 √n 个元素。对于任意区间操作：

• 完整块：直接对整块进行批量处理，时间复杂度 O(√n)
• 不完整块：暴力逐个处理边缘元素，时间复杂度 O(√n)

单次操作总时间复杂度为 O(√n)，既避免了纯暴力的 O(n)，又无需线段树复杂的懒标记下传逻辑。

完整 Java 实现

import java.util.Arrays;

/**
 * 分块算法实现：支持区间加法修改与区间求和查询
 */
public class SqrtDecomposition {

    private final int[] arr;      // 原数组
    private final int[] block;    // 每块的和
    private final int[] add;      // 每块的懒标记（待下传增量）
    private final int blockSize;  // 块大小
    private final int blockCount; // 块数量

    public SqrtDecomposition(int[] nums) {
        int n = nums.length;
        this.blockSize = (int) Math.sqrt(n) + 1;
        this.blockCount = (n + blockSize - 1) / blockSize;
        this.arr = Arrays.copyOf(nums, n);
        this.block = new int[blockCount];
        this.add = new int[blockCount];

        // 初始化每块的和
        for (int i = 0; i < n; i++) {
            block[i / blockSize] += arr[i];
        }
    }

    /**
     * 区间加法：将 [l, r] 内每个元素加上 val
     */
    public void rangeAdd(int l, int r, int val) {
        int leftBlock = l / blockSize;
        int rightBlock = r / blockSize;

        if (leftBlock == rightBlock) {
            // 在同一块内，直接暴力修改
            for (int i = l; i <= r; i++) {
                arr[i] += val;
            }
            block[leftBlock] += val * (r - l + 1);
        } else {
            // 左端不完整块
            int leftEnd = (leftBlock + 1) * blockSize - 1;
            for (int i = l; i <= Math.min(leftEnd, arr.length - 1); i++) {
                arr[i] += val;
            }
            block[leftBlock] += val * (Math.min(leftEnd, arr.length - 1) - l + 1);

            // 中间完整块，使用懒标记
            for (int b = leftBlock + 1; b < rightBlock; b++) {
                add[b] += val;
            }

            // 右端不完整块
            int rightStart = rightBlock * blockSize;
            for (int i = rightStart; i <= r; i++) {
                arr[i] += val;
            }
            block[rightBlock] += val * (r - rightStart + 1);
        }
    }

    /**
     * 区间求和：计算 [l, r] 的元素和
     */
    public long rangeSum(int l, int r) {
        long sum = 0;
        int leftBlock = l / blockSize;
        int rightBlock = r / blockSize;

        if (leftBlock == rightBlock) {
            for (int i = l; i <= r; i++) {
                sum += arr[i] + add[leftBlock];
            }
        } else {
            // 左端不完整块
            int leftEnd = (leftBlock + 1) * blockSize - 1;
            for (int i = l; i <= Math.min(leftEnd, arr.length - 1); i++) {
                sum += arr[i] + add[leftBlock];
            }

            // 中间完整块
            for (int b = leftBlock + 1; b < rightBlock; b++) {
                sum += (long) block[b] + (long) add[b] * blockSize;
            }

            // 右端不完整块
            int rightStart = rightBlock * blockSize;
            for (int i = rightStart; i <= r; i++) {
                sum += arr[i] + add[rightBlock];
            }
        }
        return sum;
    }

    /**
     * 单点查询：获取位置 idx 的当前值（下传懒标记）
     */
    public int pointQuery(int idx) {
        return arr[idx] + add[idx / blockSize];
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        SqrtDecomposition sd = new SqrtDecomposition(nums);

        System.out.println("初始区间 [0, 9] 的和: " + sd.rangeSum(0, 9)); // 55

        sd.rangeAdd(2, 7, 5);
        System.out.println("[2,7] 加 5 后 [0, 9] 的和: " + sd.rangeSum(0, 9)); // 85

        System.out.println("位置 5 的值: " + sd.pointQuery(5)); // 11
        System.out.println("位置 1 的值: " + sd.pointQuery(1)); // 2
    }
}

复杂度分析

分块算法单次操作的时间复杂度为 O(√n)，当 n = 10^5 时约为 316 次运算，在大多数场景下均可接受。其核心优势在于代码简洁、易于扩展，可轻松支持区间最值、区间赋值、区间开方等复杂操作。

应用场景

• 不支持线段树懒标记的复杂操作（如区间模运算、区间开方）
• 需要 O(1) 单点查询的场景
• 作为莫队算法的预处理结构
• 离线查询中配合其他算法使用

总结

分块算法以平方根为界，在完整块与零散块之间取得了完美的平衡。它虽不如线段树在对数时间上的极致效率，却以极简的实现成本和极强的扩展性，成为算法竞赛与工程实践中的利器。掌握分块思想，将为你打开区间问题处理的另一扇大门。