引言
分块（Sqrt Decomposition / Blocking）是一种重要的数据结构思想，通过对数据进行平方级别的分块处理，将区间操作的时间复杂度从线性优化到接近根号级别。它在区间查询、区间修改问题中有着广泛的应用，尤其适用于线段树难以处理的复杂区间操作场景。本文使用Java实现分块数据结构，讲解平方分割的核心思想，并应用于区间最值查询与区间加法更新问题。
核心思想
将长度为 n 的数组分成约 √n 个块，每个块包含约 √n 个元素。对于区间操作：
– 完整块：整块使用预处理信息直接计算，O(1)
– 不完整块：两端零散元素逐个处理，O(√n)
单次操作时间复杂度为 O(√n)，在 n = 10^5 时，√n ≈ 316，远优于 O(n) 的暴力方法。
基础分块：区间求和与单点修改
import java.util.*;
/**
* 分块数据结构：平方分割实现区间查询与修改
*/
public class SqrtDecomposition {
private int[] arr; // 原数组
private int n; // 数组长度
private int blockSize; // 块大小
private int blockCount; // 块数量
private long[] blockSum; // 每块的和
private int[] blockMax; // 每块的最大值
private int[] blockMin; // 每块的最小值
private long[] lazyAdd; // 懒标记：整块加法
public SqrtDecomposition(int[] input) {
this.n = input.length;
this.arr = Arrays.copyOf(input, n);
this.blockSize = (int) Math.sqrt(n) + 1;
this.blockCount = (n + blockSize - 1) / blockSize;
this.blockSum = new long[blockCount];
this.blockMax = new int[blockCount];
this.blockMin = new int[blockCount];
this.lazyAdd = new long[blockCount];
Arrays.fill(blockMax, Integer.MIN_VALUE);
Arrays.fill(blockMin, Integer.MAX_VALUE);
// 初始化块信息
for (int i = 0; i < n; i++) {
int b = i / blockSize;
blockSum[b] += arr[i];
blockMax[b] = Math.max(blockMax[b], arr[i]);
blockMin[b] = Math.min(blockMin[b], arr[i]);
}
}
/**
* 区间加法：将 [l, r] 内每个元素加上 val
*/
public void rangeAdd(int l, int r, int val) {
int bl = l / blockSize;
int br = r / blockSize;
if (bl == br) {
// 同一块内，直接逐个修改
for (int i = l; i <= r; i++) {
arr[i] += val;
}
rebuildBlock(bl);
} else {
// 左端不完整块
for (int i = l; i < (bl + 1) * blockSize && i < n; i++) {
arr[i] += val;
}
rebuildBlock(bl);
// 右端不完整块
for (int i = br * blockSize; i <= r; i++) {
arr[i] += val;
}
rebuildBlock(br);
// 中间完整块，使用懒标记
for (int b = bl + 1; b < br; b++) {
lazyAdd[b] += val;
blockSum[b] += (long) val * blockSize;
blockMax[b] += val;
blockMin[b] += val;
}
}
}
/**
* 区间求和查询
*/
public long rangeSum(int l, int r) {
int bl = l / blockSize;
int br = r / blockSize;
long sum = 0;
if (bl == br) {
for (int i = l; i <= r; i++) {
sum += arr[i] + lazyAdd[bl];
}
} else {
for (int i = l; i < (bl + 1) * blockSize && i < n; i++) {
sum += arr[i] + lazyAdd[bl];
}
for (int i = br * blockSize; i <= r; i++) {
sum += arr[i] + lazyAdd[br];
}
for (int b = bl + 1; b < br; b++) {
sum += blockSum[b];
}
}
return sum;
}
/**
* 区间最大值查询
*/
public int rangeMax(int l, int r) {
int bl = l / blockSize;
int br = r / blockSize;
int max = Integer.MIN_VALUE;
if (bl == br) {
for (int i = l; i <= r; i++) {
max = Math.max(max, arr[i] + (int) lazyAdd[bl]);
}
} else {
for (int i = l; i < (bl + 1) * blockSize && i < n; i++) {
max = Math.max(max, arr[i] + (int) lazyAdd[bl]);
}
for (int i = br * blockSize; i <= r; i++) {
max = Math.max(max, arr[i] + (int) lazyAdd[br]);
}
for (int b = bl + 1; b < br; b++) {
max = Math.max(max, blockMax[b]);
}
}
return max;
}
/**
* 单点查询：获取下标 i 的实际值
*/
public long pointQuery(int i) {
return arr[i] + lazyAdd[i / blockSize];
}
/**
* 重建指定块的信息
*/
private void rebuildBlock(int b) {
int start = b * blockSize;
int end = Math.min(start + blockSize, n);
blockSum[b] = 0;
blockMax[b] = Integer.MIN_VALUE;
blockMin[b] = Integer.MAX_VALUE;
for (int i = start; i < end; i++) {
blockSum[b] += arr[i];
blockMax[b] = Math.max(blockMax[b], arr[i]);
blockMin[b] = Math.min(blockMin[b], arr[i]);
}
// 注意：这里arr已经是实际值，所以不需要再加lazyAdd
}
莫队算法：离线区间查询优化
/**
* 莫队算法：通过调整查询顺序减少指针移动次数
* 适用于离线区间查询问题，时间复杂度 O((n+q)*√n)
*/
static class MoAlgorithm {
int[] arr;
int blockSize;
MoAlgorithm(int[] arr) {
this.arr = arr;
this.blockSize = (int) Math.sqrt(arr.length) + 1;
}
/**
* 对查询区间按莫队顺序排序
*/
List<Query> sortQueries(List<Query> queries) {
queries.sort((a, b) -> {
int ba = a.l / blockSize;
int bb = b.l / blockSize;
if (ba != bb) return ba - bb;
return (ba % 2 == 0) ? a.r - b.r : b.r - a.r; // 奇偶优化
});
return queries;
}
/**
* 处理查询：示例为区间不同数字个数
*/
int[] processQueries(int[] arr, List<Query> queries) {
List<Query> sorted = sortQueries(queries);
int[] ans = new int[sorted.size()];
int[] freq = new int[1000005]; // 假设数值范围
int currentL = 0, currentR = -1;
int distinctCount = 0;
for (Query q : sorted) {
// 扩展/收缩左指针
while (currentL > q.l) {
currentL--;
if (freq[arr[currentL]] == 0) distinctCount++;
freq[arr[currentL]]++;
}
while (currentL < q.l) {
freq[arr[currentL]]--;
if (freq[arr[currentL]] == 0) distinctCount--;
currentL++;
}
// 扩展/收缩右指针
while (currentR < q.r) {
currentR++;
if (freq[arr[currentR]] == 0) distinctCount++;
freq[arr[currentR]]++;
}
while (currentR > q.r) {
freq[arr[currentR]]--;
if (freq[arr[currentR]] == 0) distinctCount--;
currentR--;
}
ans[q.id] = distinctCount;
}
return ans;
}
}
static class Query {
int l, r, id;
Query(int l, int r, int id) { this.l = l; this.r = r; this.id = id; }
}
分块 vs 线段树对比
/**
* 性能对比测试
*/
public static void main(String[] args) {
int n = 100000;
int[] arr = new int[n];
Random rand = new Random(42);
for (int i = 0; i < n; i++) {
arr[i] = rand.nextInt(1000);
}
SqrtDecomposition sd = new SqrtDecomposition(arr);
System.out.println("=== 分块数据结构测试 ===\n");
// 区间加法
long t1 = System.currentTimeMillis();
for (int i = 0; i < 10000; i++) {
int l = rand.nextInt(n);
int r = l + rand.nextInt(Math.min(1000, n - l));
sd.rangeAdd(l, r, rand.nextInt(100));
}
System.out.println("10000次区间加法耗时: " + (System.currentTimeMillis() - t1) + "ms");
// 区间求和查询
t1 = System.currentTimeMillis();
long totalSum = 0;
for (int i = 0; i < 10000; i++) {
int l = rand.nextInt(n);
int r = l + rand.nextInt(Math.min(1000, n - l));
totalSum += sd.rangeSum(l, r);
}
System.out.println("10000次区间求和耗时: " + (System.currentTimeMillis() - t1) + "ms");
// 区间最大值查询
t1 = System.currentTimeMillis();
int totalMax = 0;
for (int i = 0; i < 10000; i++) {
int l = rand.nextInt(n);
int r = l + rand.nextInt(Math.min(1000, n - l));
totalMax ^= sd.rangeMax(l, r);
}
System.out.println("10000次区间最大值耗时: " + (System.currentTimeMillis() - t1) + "ms");
System.out.println("\n校验值: sum=" + totalSum + ", maxXor=" + totalMax);
}
}
复杂度分析
| 操作 | 分块 | 线段树 | 暴力 |
|---|---|---|---|
| 单点修改 | O(√n) | O(log n) | O(1) |
| 区间修改 | O(√n) | O(log n) | O(n) |
| 区间查询 | O(√n) | O(log n) | O(n) |
| 实现难度 | 低 | 中 | 极低 |
| 代码量 | 少 | 多 | 极少 |
分块的优势在于实现简单、代码量小、灵活性高，特别适合线段树难以处理的复杂操作。
总结
本文通过分块数据结构实现了区间加法、区间求和、区间最值等操作，并介绍了莫队算法的离线查询优化技巧。读者可以掌握平方分割的核心思想，在竞赛和工程实践中根据问题特点灵活选择分块、线段树或其他数据结构。
