莫队算法

区间不同数查询问题：从暴力到莫队算法

问题描述

给定一个长度为 n 的数组，处理 q 次查询，每次查询区间 [l, r] 内不同数的个数。

数据范围：数组中的数值范围为 [1, m]，需要高效处理多次查询。

算法演进过程

1. 暴力解法

思路

对于每次查询 [l, r]：

用数组 cnt[] 统计区间内每个数的出现次数
遍历整个数据范围 [1, m]，计算有多少个数的计数非零

代码框架

int query(int l, int r) {
    memset(cnt, 0, sizeof(cnt));

    // 统计区间内每个数的出现次数
    for (int i = l; i <= r; i++) {
        cnt[arr[i]]++;
    }

    // 遍历数据范围，计算不同数的个数
    int result = 0;
    for (int i = 1; i <= m; i++) {
        if (cnt[i] > 0) {
            result++;
        }
    }
    return result;
}

时间复杂度

统计区间：O(n)
遍历数据范围：O(m)
单次查询：O(n + m)
q 次查询：O(q(n + m))

缺点

当数据范围 m 很大时，每次都要遍历 [1, m] 效率很低。

2. 改进解法1：避免遍历数据范围

优化思路

在统计的同时记录不同数的个数，避免遍历整个数据范围。

代码框架

int query(int l, int r) {
    memset(cnt, 0, sizeof(cnt));
    int distinct_count = 0;

    for (int i = l; i <= r; i++) {
        if (cnt[arr[i]] == 0) {
            distinct_count++;  // 第一次遇到这个数
        }
        cnt[arr[i]]++;
    }

    return distinct_count;
}

时间复杂度

单次查询：O(n)
q 次查询：O(qn)

优势

消除了数据范围 m 的影响，当 m >> n 时效果显著。

3. 改进解法2：排序优化

思路

将查询按左端点排序，用双指针维护当前区间，减少重复计算。

存在的问题

如果右端点跳跃幅度大，指针频繁大幅移动
最坏情况下复杂度退化为 O(qn)
时间复杂度：O(qn log n)（包含排序）

问题分析

这种方法高度依赖数据特性，出题人可以构造数据使其效果很差。

4. 莫队算法（重点）

算法思想

莫队算法通过特殊的排序方式最小化指针移动的总距离，从而获得稳定的时间复杂度。

核心步骤

1. 分块

将数组按位置分成 √n 个块，每块大小约为 √n
块的划分：block_size = √n
对于位置 i，其所属块号为：block_id = i / block_size

2. 查询排序

bool cmp(Query a, Query b) {
    int block_a = a.l / block_size;
    int block_b = b.l / block_size;

    if (block_a != block_b) {
        return block_a < block_b;  // 按左端点所在块排序
    }
    return a.r < b.r;  // 同块内按右端点排序
}

3. 双指针处理

维护当前区间 [left, right] 和答案：

void add(int x) {
    if (cnt[x] == 0) {
        distinct_count++;
    }
    cnt[x]++;
}

void remove(int x) {
    cnt[x]--;
    if (cnt[x] == 0) {
        distinct_count--;
    }
}

// 处理查询
int left = 1, right = 0;
for (auto query : sorted_queries) {
    // 移动左指针
    while (left < query.l) {
        remove(arr[left]);
        left++;
    }
    while (left > query.l) {
        left--;
        add(arr[left]);
    }

    // 移动右指针
    while (right < query.r) {
        right++;
        add(arr[right]);
    }
    while (right > query.r) {
        remove(arr[right]);
        right--;
    }

    answer[query.id] = distinct_count;
}

分块示例

假设 n = 16，block_size = 4：

位置: 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16
块号: 0  0  0  0  1  1  1  1  2  2  2  2  3  3  3  3

查询示例：

查询A: [2, 10] -> l=2, 属于块0
查询B: [6, 15] -> l=6, 属于块1
查询C: [3, 5]  -> l=3, 属于块0
查询D: [7, 12] -> l=7, 属于块1

排序后：

块0: C[3,5], A[2,10]  (按r排序: 5 < 10)
块1: B[6,15], D[7,12] (按r排序: 12 < 15)

处理顺序: C[3,5] -> A[2,10] -> D[7,12] -> B[6,15]

时间复杂度证明

关键分析：指针移动总距离

左指针移动分析

1. 同块内移动

每个块内，左端点都在范围 [i×√n, (i+1)×√n) 内
同块内任意两个查询，左指针移动距离 ≤ √n
q 个查询，左指针同块内总移动：O(q√n)

2. 跨块移动

总共 √n 个块，最多跨块 √n 次
每次跨块最多移动 √n 距离
跨块总移动：O(√n × √n) = O(n)

左指针总移动：O(q√n + n)

右指针移动分析

1. 同块内移动

同块内查询按 r 排序，右指针单调递增
每个块内，右指针最多从 0 移动到 n
√n 个块，每块内移动 O(n)
同块内总移动：O(√n × n) = O(n√n)

2. 跨块移动

换块时右指针可能需要重新定位
最多换块 √n 次，每次最多移动 n
跨块总移动：O(√n × n) = O(n√n)

右指针总移动：O(n√n)

总复杂度

总时间复杂度 = 左指针移动 + 右指针移动 + 排序
             = O(q√n + n) + O(n√n) + O(q log q)
             = O(q√n + n√n + q log q)
             = O((q + n)√n)

当 q 和 n 同阶时，复杂度为 O(n√n)。

复杂度证明的数学严格性

定理：莫队算法的时间复杂度为 O((q + n)√n)。

证明：

设 block_size = B = √n，总共有 ⌈n/B⌉ ≤ √n + 1 个块。

左指针分析：

设第 i 块内有 q_i 个查询
第 i 块内左指针移动总距离 ≤ q_i × B
所有块内移动：∑q_i × B = B∑q_i = B × q = q√n
跨块移动：最多 √n 次，每次最多 B，总计 ≤ √n × √n = n
左指针总移动：q√n + n

右指针分析：

每个块内右指针单调递增，最多移动 n
√n 个块，总移动 ≤ √n × n = n√n

总复杂度：O(q√n + n + n√n) = O((q + n)√n) ∎

算法优势

稳定性：不依赖数据分布，任何情况下都是 O((q + n)√n)
实用性：常数较小，实际运行效率高
通用性：适用于各种可以增删维护的区间查询问题

应用场景

莫队算法适用于满足以下条件的问题：

离线查询（可以重新排序）
知道 [l, r] 的答案，能够 O(1) 得到 [l±1, r] 和 [l, r±1] 的答案
无修改操作

典型问题包括：

区间不同数个数
区间数字种类数
区间平方和
区间众数等