分块

概念讲解

什么是分块？

将数组分成 n\sqrt{n} 块，每块大小 n\sqrt{n}，在块上维护信息。

时间复杂度

操作 时间复杂度
单点修改 O(1)
区间修改 O(√n)
区间查询 O(√n)

实现

123456789101112131415161718192021222324252627282930313233343536const int N = 100005;
int a[N], block[N], lazy[N];
int blockSize, n;

void build() {
    blockSize = sqrt(n);
    for (int i = 0; i < n; i++) {
        block[i / blockSize] += a[i];
    }
}

void update(int l, int r, int c) {
    int bl = l / blockSize, br = r / blockSize;
    if (bl == br) {
        for (int i = l; i <= r; i++) {
            a[i] += c;
            block[bl] += c;
        }
    } else {
        for (int i = l; i < (bl+1)*blockSize; i++) a[i] += c, block[bl] += c;
        for (int i = bl+1; i < br; i++) lazy[i] += c;
        for (int i = br*blockSize; i <= r; i++) a[i] += c, block[br] += c;
    }
}

int query(int l, int r) {
    int ans = 0, bl = l / blockSize, br = r / blockSize;
    if (bl == br) {
        for (int i = l; i <= r; i++) ans += a[i] + lazy[bl];
    } else {
        for (int i = l; i < (bl+1)*blockSize; i++) ans += a[i] + lazy[bl];
        for (int i = bl+1; i < br; i++) ans += block[i] + lazy[i] * blockSize;
        for (int i = br*blockSize; i <= r; i++) ans += a[i] + lazy[br];
    }
    return ans;
}

考点分析

初赛考查方式

  1. 程序阅读： 分块程序
  2. 编程题： 区间操作

常见考点

  • 分块思想
  • 区间操作
  • 复杂度分析

练习题

  1. 分块的时间复杂度是多少？
查看答案

分块的时间复杂度：

  • 单点修改：O(1)O(1)
  • 区间修改：O(n)O(\sqrt{n})
  • 区间查询：O(n)O(\sqrt{n})
  1. 分块和线段树的区别？
查看答案
特性 分块 线段树
时间复杂度 O(n)O(\sqrt{n}) O(log⁡n)O(\log n)
实现难度 简单 较复杂
空间复杂度 O(n)O(n) O(n)O(n)
灵活性 高 中等

分块更适合区间修改，线段树更适合单点修改和区间查询。

  1. 什么情况下用分块？
查看答案

分块适用于：

  1. 区间修改：需要对区间进行加、减等操作
  2. 区间查询：需要查询区间的和、最值等
  3. 实现简单：比线段树更容易实现
  4. 数据范围适中：n≤105n \le 10^5 左右

易错点

⚠️ 注意：

  1. 块大小取 sqrt(n)
  2. 散块要暴力处理
  3. lazy 标记要及时下传
  4. 分块比线段树好写