CC++ & Algorithm

分块思想与莫队算法简介

极难3
语言版本：通用
概述：把数据分成若干块，块内暴力，块间预处理，平衡复杂度；莫队算法则通过离线排序让区间移动总距离最小。

分块思想与莫队算法：让区间查询变快的两个好方法

你有没有遇到过这样的问题：你有一排同学的成绩表（数组），老师经常问“第5号到第20号同学的总分是多少？”或者“这期间有多少个同学考了90分以上？”最简单的办法是一个一个数，但次数多了太慢。另一种办法是提前把所有可能的区间结果都算好存起来，可是如果成绩经常变动（比如有人改分），维护起来就很麻烦。

分块思想和莫队算法就是两种聪明的折中方法：分块就像把一堆零食分成几袋，每次只拆一袋，零头单独处理；莫队算法则像你有一堆家务要干，先计划好顺序，避免来回跑冤枉路。它们都能让处理速度从O(n)变成O(√n)，非常实用。

下面我们就一步一步来学习这两种方法。

一、分块思想：把大问题切成小块来搞定

1. 原理：平衡预处理和暴力

假设你有一排玩具（数组），共n个，每个玩具都有颜色（数字表示）。你要经常问某段区间里有多少个红色玩具。

  • 全暴力：每次查询都从l到r逐个检查，复杂度O(n)，太慢。
  • 全预处理：提前为所有可能区间建立统计表，但玩具颜色会变化，维护表非常麻烦。

分块的做法是：把玩具平均分成若干组，每组大概√n个（比如n=100，就分10组，每组10个）。每组事先整理出一个“统计表”（比如每种颜色有几个）。查询时，如果区间包含了完整的组，直接查表；两头的零头（不在整组内的部分）才挨个数。这样查询复杂度大约是O(√n)，修改单个玩具时也只需要更新它所在组的统计表，复杂度O(1)。

为什么选√n？
因为块数≈n/B，块内大小=B。查询时要处理零头最多2B个元素，和最多n/B个整块。总时间≈B + n/B。当B=√n时，B和n/B相等，得到最小值2√n。所以B取√n最平衡。

2. 生活中的例子

  • 班级分组：你和同学排成一排，要统计某段位置里有多少人戴眼镜。先按学号分成10组，每组5人。每组记下戴眼镜人数。查询时，先看哪些组完全包含在区间内，直接加它们的统计数；区间两头可能跨过组边界，就只挨个问那几个人。
  • 超市货架：超市有100排货架，每排有相同数量的商品。要统计某几排里有多少种零食，管理员可以提前记下每排的零食种类数量，查询时只看整排的记录，再检查头尾两排的部分商品。

3. 分块的核心操作

我们需要三个数据结构：

  • 原始数组 a[]（存储每个位置的值）
  • 块编号数组 block_id[]（每个位置属于哪个块）
  • 块统计数组 block_sum[]（每个块的汇总信息，比如和、最值、出现次数等）

查询区间 [l, r]：

  1. 如果 l 和 r 在同一块内，直接暴力扫描 l~r。
  2. 否则：
    • 处理左边零头：从 l 到 l所在块的末尾，逐个获取。
    • 处理中间完整块：从 l所在块的下一个块到 r所在块的上一个块，直接加上块统计信息。
    • 处理右边零头：从 r所在块的开头到 r，逐个获取。

单点修改 (pos, newVal)：

  • 先计算差值 = newVal - a[pos]。
  • 更新块统计：block_sum[block_id[pos]] += 差值。
  • 更新原数组：a[pos] = newVal。

4. C++完整代码：区间和查询与单点修改

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;

const int MAXN = 100005;
int a[MAXN];                // 原始数组，下标从1开始
int block_sum[320];        // 每个块的和，块大小约√n，最多约320块
int block_id[MAXN];        // 每个位置所属的块编号
int block_size;            // 块大小
int n, q;                  // n个元素，q次操作

// 初始化：建立分块
void build() {
    block_size = sqrt(n);                // 取√n作为块大小（下取整）
    for (int i = 1; i <= n; i++) {
        block_id[i] = (i - 1) / block_size;  // 计算位置i的块编号
        block_sum[block_id[i]] += a[i];      // 累加到对应块的和中
    }
}

// 单点修改：将位置pos的值改为val
void update(int pos, int val) {
    int idx = block_id[pos];                // 找到pos所在的块
    block_sum[idx] += val - a[pos];        // 更新块的和（差值）
    a[pos] = val;                          // 更新原数组
}

// 区间求和查询：返回区间[l, r]的和
int query(int l, int r) {
    int sum = 0;
    // 情况1：l和r在同一个块内，直接暴力
    if (block_id[l] == block_id[r]) {
        for (int i = l; i <= r; i++) sum += a[i];
        return sum;
    }
    // 左边零头：从l到l所在块的末尾
    for (int i = l; block_id[i] == block_id[l]; i++) sum += a[i];
    // 中间完整块：从块编号block_id[l]+1到block_id[r]-1
    for (int b = block_id[l] + 1; b < block_id[r]; b++) sum += block_sum[b];
    // 右边零头：从r所在块的开头到r
    for (int i = r; block_id[i] == block_id[r]; i--) sum += a[i];
    return sum;
}

int main() {
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    build();                       // 建立分块
    while (q--) {
        int op, x, y;
        cin >> op >> x >> y;
        if (op == 1) {
            update(x, y);          // 修改：把a[x]改为y
        } else {
            cout << query(x, y) << endl;  // 查询区间[x,y]的和
        }
    }
    return 0;
}

Python版本（同样功能）：

import math

def main():
    n, q = map(int, input().split())
    a = [0] + list(map(int, input().split()))  # a[1..n]有效
    block_size = int(math.sqrt(n)) + 1         # 块大小（上取整）
    num_blocks = (n + block_size - 1) // block_size
    block_id = [0] * (n + 1)
    block_sum = [0] * num_blocks

    for i in range(1, n + 1):
        block_id[i] = (i - 1) // block_size
        block_sum[block_id[i]] += a[i]

    for _ in range(q):
        op, x, y = map(int, input().split())
        if op == 1:
            # 修改：把a[x]变为y
            idx = block_id[x]
            block_sum[idx] += y - a[x]
            a[x] = y
        else:
            l, r = x, y
            res = 0
            # 同一块内直接暴力
            if block_id[l] == block_id[r]:
                for i in range(l, r + 1):
                    res += a[i]
                print(res)
                continue
            # 左边零头
            i = l
            while block_id[i] == block_id[l]:
                res += a[i]
                i += 1
            # 中间完整块
            for b in range(block_id[l] + 1, block_id[r]):
                res += block_sum[b]
            # 右边零头
            i = r
            while block_id[i] == block_id[r]:
                res += a[i]
                i -= 1
            print(res)

if __name__ == "__main__":
    main()

二、莫队算法：离线排序，滑动窗口

1. 为什么要离线？

分块能解决单次查询，但如果有一大堆区间查询（比如老师问了1000个区间），每次都用分块查询，总时间可能是O(q√n)。莫队算法更聪明：它先把所有查询收集起来（离线），然后按一种聪明的顺序重新排列，再像滑动窗口一样移动左右指针，让指针移动的总次数最少，从而把总时间优化到O((n+q)√n)左右。

核心思想：

  • 把区间按左端点所在块排序，块内按右端点排序（类似图书馆按书架号、再按书号找书）。
  • 维护两个指针curL和curR，以及一个当前答案。
  • 对于每个查询[l, r]，通过移动curL和curR到达该区间，同时维护更新答案。
  • 因为排序后指针来回移动的次数可控，总复杂度与n√n同阶。

2. 生活中的例子

  • 图书馆找书：你要借10本书，每本书在书架上都有位置（类似区间）。如果按书架顺序一本一本地查，会来回跑很多路。莫队算法就像你先把要借的书按书架号排好序，同一书架上的书再按位置排，然后推着车子从左到右一次拿完，避免折返。
  • 批改作业：老师要批改不同学号段的学生作业，聪明的老师会按学号顺序依次翻看，而不是跳来跳去。

3. 排序的细节

设块大小为block_size = sqrt(n)。排序规则：

bool cmp(Query a, Query b) {
    if (a.l / block_size != b.l / block_size)
        return a.l / block_size < b.l / block_size;  // 按左端点所在块排序
    // 块内按右端点排序，利用奇偶优化：
    // 如果左块是偶数，右端点从小到大；奇数则从大到小，减少来回移动。
    return (a.r < b.r) ^ ((a.l / block_size) & 1);
}

奇偶优化：左块编号为偶数时，右端点递增；奇数时右端点递减。这样指针不会在块边界处反复横跳，能减少大约一半的移动。

4. 指针移动与答案更新

我们需要两个函数：

  • add(pos)：将位置pos的元素加入当前窗口，更新答案。
  • remove(pos)：将位置pos的元素移出当前窗口，更新答案。

例如，统计区间内不同数字的个数（经典问题）：

void add(int pos) {
    if (++freq[a[pos]] == 1) ans++;  // 该数字首次出现，不同数字个数+1
}
void remove(int pos) {
    if (--freq[a[pos]] == 0) ans--;  // 该数字消失，不同数字个数-1
}

移动指针的顺序要小心：

while (curL > l) add(--curL);   // 左指针向左移动，加入新元素
while (curR < r) add(++curR);   // 右指针向右移动，加入新元素
while (curL < l) remove(curL++); // 左指针向右移动，移除旧元素
while (curR > r) remove(curR--); // 右指针向左移动，移除旧元素

注意：add和remove操作要对称，确保窗口始终是[l, r]。

5. C++完整代码：求区间不同元素个数

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

const int MAXN = 100005;
int a[MAXN];               // 原始数组，a[1..n]
int freq[MAXN];            // 频率数组，记录每种元素在当前窗口中出现的次数
int ans;                   // 当前窗口中不同元素的个数
int result[MAXN];          // 存储每个查询的答案
int block_size;

struct Query {
    int l, r, id;          // 区间左右端点，查询编号
} q[MAXN];

// 排序规则：先按左块，块内按右端点，奇偶优化
bool cmp(Query &a, Query &b) {
    if (a.l / block_size != b.l / block_size)
        return a.l / block_size < b.l / block_size;
    return (a.r < b.r) ^ ((a.l / block_size) & 1);
}

// 添加位置pos的元素到窗口
void add(int pos) {
    if (++freq[a[pos]] == 1) ans++;
}

// 移除位置pos的元素从窗口
void remove(int pos) {
    if (--freq[a[pos]] == 0) ans--;
}

int main() {
    int n, Q;
    cin >> n >> Q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    block_size = sqrt(n);                 // 块大小取√n
    for (int i = 0; i < Q; i++) {
        cin >> q[i].l >> q[i].r;
        q[i].id = i;
    }
    sort(q, q + Q, cmp);                 // 按最优顺序排序

    int curL = 1, curR = 0;              // 初始空窗口
    for (int i = 0; i < Q; i++) {
        int l = q[i].l, r = q[i].r;
        while (curL > l) add(--curL);    // 左端点左移，加入元素
        while (curR < r) add(++curR);    // 右端点右移，加入元素
        while (curL < l) remove(curL++); // 左端点右移，移除元素
        while (curR > r) remove(curR--); // 右端点左移，移除元素
        result[q[i].id] = ans;           // 记录答案
    }
    for (int i = 0; i < Q; i++) cout << result[i] << endl;
    return 0;
}

Python版本（同样功能）：

import math

def main():
    n, q = map(int, input().split())
    a = [0] + list(map(int, input().split()))  # a[1..n]
    queries = []
    for i in range(q):
        l, r = map(int, input().split())
        queries.append((l, r, i))

    block_size = int(math.sqrt(n)) + 1
    # 排序：按左块正序，块内右端点按奇偶调整
    queries.sort(key=lambda x: (x[0] // block_size, 
                                x[1] if (x[0] // block_size) % 2 == 0 else -x[1]))

    max_val = max(a)  # 假设元素值范围不大
    freq = [0] * (max_val + 1)
    ans = 0
    curL, curR = 1, 0
    result = [0] * q

    def add(pos):
        nonlocal ans
        freq[a[pos]] += 1
        if freq[a[pos]] == 1:
            ans += 1

    def remove(pos):
        nonlocal ans
        freq[a[pos]] -= 1
        if freq[a[pos]] == 0:
            ans -= 1

    for l, r, idx in queries:
        while curL > l:
            curL -= 1
            add(curL)
        while curR < r:
            curR += 1
            add(curR)
        while curL < l:
            remove(curL)
            curL += 1
        while curR > r:
            remove(curR)
            curR -= 1
        result[idx] = ans

    for v in result:
        print(v)

if __name__ == "__main__":
    main()

三、常见错误与调试技巧

1. 分块常见错误

  • 块大小没取√n：如果块太大（比如n/2），零头部分变多，退化成暴力；块太小（比如1），整块数量太多，预处理和查询都变慢。
  • 块编号从0开始还是从1开始？：注意下标对齐。通常位置1~n，块编号从0开始。用(i-1)/block_size。
  • 零头处理边界：左零头循环条件是block_id[i] == block_id[l]，但要注意i不能越界；右零头同理。
  • 修改时忘记更新原数组：只更新块和，没更新a[pos]，导致下次查询使用旧值。

2. 莫队算法常见错误

  • 排序错误：忘了先按左块排序，或者块内直接按右端点（没加奇偶优化）会导致指针来回移动过多，可能超时。
  • 指针移动顺序错误：比如先remove后add，导致窗口内元素计数混乱。正确顺序是：先扩大范围（左移左指针或右移右指针），再缩小范围。
  • add和remove不匹配：例如add时判断条件为if (freq==1) ans++，但remove时忘了减。最好写成对称结构。
  • 频率数组大小不够：如果元素值范围大（比如1e9），不能用静态数组，要用map或unordered_map。但排序时注意map的常数较大。
  • 忽略奇偶优化：虽然不加也能过，但加上后能明显提升速度（尤其大数据）。

3. 调试小技巧

  • 对于小规模数据，可以用暴力方法验证结果。
  • 在代码中加入打印语句，输出指针移动过程中窗口内容和答案，观察是否正确。
  • 测试极端情况：n=1, q=1；所有查询都是相同的区间；元素全相同；元素互不相同。

四、完整应用实例：统计区间内颜色种类

题目：小明有n个玩具，每个玩具都有一个颜色编号。老师会问q个问题，每个问题给出区间[l, r]，问这个区间里有多少种不同的颜色。玩具颜色有时会变化（单点修改）。要求在线处理（实时回答）。

分析：如果带修改，可以用带修莫队（增加时间维度），也可以直接用分块维护每个块内颜色的频率。这里我们展示一个分块实现不同颜色数统计（带修改）的简化版思路：

每个块内维护一个频率数组（每种颜色出现的次数），以及块内不同颜色的数量。查询时，对于整块直接拿块的不同颜色数，但要注意整块内的颜色可能和零头部分的颜色重叠，需要额外处理（最方便的方法是：查询时把整块的频率合并到一个全局频率中，再扫描零头）。但更常用的方法是：莫队更适合离线查询，分块适合在线但有修改。

我们用一个简单的莫队示例（不带修）来解决：就是上面给出的代码。假设输入：

10 5
1 2 3 2 1 1 3 4 5 2
1 5
3 7
2 8
4 9
1 10

输出应为：

区间[1,5]：1,2,3,2,1 → 不同颜色：1,2,3 → 3种
区间[3,7]：3,2,1,1,3 → 不同：1,2,3 → 3种
区间[2,8]：2,3,2,1,1,3,4 → 不同：1,2,3,4 → 4种
区间[4,9]：2,1,1,3,4,5 → 不同：1,2,3,4,5 → 5种
区间[1,10]：全部 → 不同：1,2,3,4,5 → 5种

运行莫队代码即可得到正确结果。

五、相关知识点指引

  • 树状数组与线段树：也能解决区间和、最值等问题，但树状数组不支持复杂统计（如不同元素个数），线段树可以但代码量较大。分块是这两者的简易替代方案。
  • 带修莫队：如果查询之间夹杂着修改操作，可以在莫队中加入时间维度，排序时左块、右块、时间三关键字，能处理带修改的区间查询。
  • 树上莫队：把树上的路径问题转化为欧拉序上的区间问题，再用莫队处理。
  • 分块与莫队的对比：分块支持在线、修改简单，但查询速度略逊于莫队（后者在离线大量查询时更优）。实际竞赛中可根据题目限制选择。
  • 其他分块技巧：分块还可以用来实现块状链表、维护区间翻转、区间众数等。

总结要点

  1. 分块：将数组分成√n大小的块，块内暴力，块间预处理，查询和修改复杂度均为O(√n)。适合在线且有修改的场景。
  2. 莫队：离线处理区间查询，通过排序使指针移动总次数为O((n+q)√n)，奇偶优化可进一步提升效率。适合大量无修改的区间统计问题。
  3. 常见坑：块大小不当、排序遗漏奇偶、指针移动顺序错误、频率数组越界。
  4. 应用：区间不同元素个数、区间众数、区间和、区间异或和等，只要支持快速添加和删除一个元素，莫队都能处理。

掌握了分块和莫队，你就拥有了对付区间查询问题的两把“利器”——既不用写复杂的线段树，也不用害怕暴力超时。快去试试吧！

例题精讲

1单选题

在分块思想中，若将长度为 n 的序列分为大小为 B 的块，则块数约为 n/B。为了平衡块内暴力与块间预处理的复杂度，通常 B 取值为？

Asqrt(n)
Bn/2
Clog n
Dn
2判断题

在莫队算法中，对查询区间排序时，通常先按左端点所在块的编号升序排序，若左端点所在块相同，则按右端点编号降序排序。

3填空题
以下为莫队算法中维护区间内不同元素个数的代码片段，请将 add 函数中的空缺部分补充完整。
int cur_ans = 0;
int cnt[100010];
void add(int pos) {
    cnt[a[pos]]++;
    if(cnt[a[pos]] == 1) ___;
}
4单选题

莫队算法的时间复杂度通常为（假设序列长度 n，询问次数 m，且 n 与 m 同阶）

AO(n)
BO(n log n)
CO(n sqrt(n))
DO(n^2)
5判断题

分块思想中，预处理阶段的时间复杂度为 O(n)，查询阶段的时间复杂度为 O(sqrt(n))，因此对于 m 次查询，总时间复杂度为 O(n + m sqrt(n))。