树状数组进阶：在线与离线操作实战，解锁区间统计新姿势

而离线操作的核心优势的是：通过排序，将'复杂查询'转化为树状数组可高效处理的'单点修改 + 区间查询'模型。例如：

对于'区间内不同元素个数'问题，离线操作可按'查询右端点排序'，遍历数组时用树状数组标记元素的最新出现位置，查询时直接统计区间内的标记数，即可得到不同元素的个数。

这种'化繁为简'的转化，正是离线操作的魅力所在。

二、离线操作实战 1：HH 的项链（洛谷 P1972）—— 区间不同元素个数统计

这是离线操作 + 树状数组的经典入门题，也是算法竞赛中的高频考点。通过这道题，我们能掌握离线操作的核心流程：'读入所有操作→排序查询→处理数组→树状数组统计→映射答案'。

题目链接：https://www.luogu.com.cn/problem/P1972

2.1 题目信息

• 来源：洛谷 P1972（SDOI2009）
• 难度：★★★★
• 核心考点：离线操作 + 树状数组 + 区间不同元素统计
• 题目描述：给定一条长度为 n 的项链，项链上每个位置是一种贝壳（用整数表示种类）。有 m 个查询，每个查询给出区间 [l, r]，求该区间内包含多少种不同的贝壳。
• 输入要求：第一行 n（项链长度）；第二行 n 个整数（贝壳种类，1≤a[i]≤1e6）；第三行 m（查询个数）；接下来 m 行，每行两个整数 l、r（1≤l≤r≤n）。
• 输出要求：对于每个查询，输出区间 [l, r] 内不同贝壳的种类数。

2.2 问题分析（为什么在线操作不行？）

如果用在线思路：对于每个查询 [l, r]，遍历区间内所有元素，用哈希表统计不同种类数。时间复杂度为 O(mn)，当 n=1e6、m=1e6 时，总操作数达到 1e12，完全超时。

因此必须用离线操作，核心思路是'按查询右端点排序，遍历数组时标记元素最新出现位置，用树状数组统计区间内标记数'。

2.3 离线操作核心思路

步骤 1：转化问题 —— 不同元素个数 = 区间内'最新出现位置'的个数

对于数组中的每个元素 a[i]，如果它在之前已经出现过（记上一次出现位置为 last[a[i]]），那么上一次的位置就失去了'贡献'（因为当前位置 i 是更靠右的出现位置，查询右端点≥i 时，只会统计 i 而不会统计 last[a[i]]）。

因此，我们可以用一个树状数组维护'元素是否是当前区间内的最新出现位置'：

遍历数组到位置 i 时，若 a[i] 之前出现过，先将树状数组中 last[a[i]] 的位置标记为 0（取消贡献）；再将树状数组中位置 i 标记为 1（标记为最新出现位置）；对于所有右端点为 i 的查询 [l, i]，区间内不同元素的个数 = 树状数组中 [l, i] 的区间和（即标记为 1 的位置个数）。

步骤 2：离线处理流程

1. 读入所有操作：将 m 个查询存储起来，并记录每个查询的原始编号（用于后续按原顺序输出答案）；
2. 排序查询：按查询的右端点 r 从小到大排序（因为我们要按数组顺序遍历，处理到 r 时再回答对应的查询）；
3. 按原查询顺序输出答案。

遍历数组 + 维护树状数组：

用 last 数组记录每个元素的上一次出现位置（初始为 0）；遍历数组 a[1..n]： a. 若 last[a[i]]≠0，执行树状数组单点修改（last[a[i]], -1）—— 取消上一次的贡献； b. 执行树状数组单点修改（i, 1）—— 标记当前位置为最新出现位置； c. 更新 last[a[i]] = i； d. 处理所有右端点 r=i 的查询：查询树状数组中 [l, i] 的区间和，将结果存入答案数组（按原始编号映射）；

2.4 完整 C++ 代码

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
#define lowbit(x) (x & -x)
const int N = 1e6 + 10; // 适配 n 和 m 的最大范围
int n, m;
int a[N]; // 项链的贝壳种类数组
int tree[N]; // 树状数组：维护位置是否为最新出现位置（1 表示是，0 表示否）
int last[N]; // 记录每个贝壳上一次出现的位置（初始为 0）
int ans[N]; // 存储最终答案，按查询原始编号排列
// 查询结构体：存储 l、r、原始编号 id
struct Query {
    int l, r, id;
} q[N];
// 排序规则：按查询的右端点 r 从小到大排序
bool cmp(Query& x, Query& y) {
    return x.r < y.r;
}
// 树状数组单点修改：位置 x 的数值增加 k（k=1 或 -1）
void modify(int x, int k) {
    for (int i = x; i <= n; i += lowbit(i)) {
        tree[i] += k;
    }
}
// 树状数组区间查询：查询 [1, x] 的前缀和
int query(int x) {
    int sum = 0;
    for (int i = x; i > 0; i -= lowbit(i)) {
        sum += tree[i];
    }
    return sum;
}
// 区间查询：查询 [l, r] 的和（不同元素个数）
int interval_query(int l, int r) {
    return query(r) - query(l - 1);
}
int main() {
    // 加速输入输出（处理 1e6 级数据必备）
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    cin >> m;
    for (int i = 1; i <= m; i++) {
        cin >> q[i].l >> q[i].r;
        q[i].id = i; // 记录原始查询编号
    }
    // 步骤 1：按查询右端点 r 排序
    sort(q + 1, q + 1 + m, cmp);
    // 步骤 2：遍历数组，维护树状数组并处理查询
    int pos = 1; // 指向当前要处理的查询（按 r 排序后的顺序）
    memset(last, 0, sizeof last); // 初始化 last 数组为 0
    for (int i = 1; i <= n; i++) {
        int current = a[i];
        // 若当前元素之前出现过，取消上一次的贡献
        if (last[current] != 0) {
            modify(last[current], -1);
        }
        // 标记当前位置为最新出现位置
        modify(i, 1);
        // 更新 last 数组
        last[current] = i;
        // 处理所有右端点 r=i 的查询
        while (pos <= m && q[pos].r == i) {
            int l = q[pos].l;
            int id = q[pos].id;
            ans[id] = interval_query(l, i);
            pos++;
        }
    }
    // 步骤 3：按原始查询顺序输出答案
    for (int i = 1; i <= m; i++) {
        cout << ans[i] << endl;
    }
    return 0;
}

2.5 代码详解

查询结构体与排序：用 Query 结构体存储查询的 l、r 和原始编号 id，按 r 排序后，保证遍历数组到 i 时，能处理所有右端点为 i 的查询； last 数组：记录每个元素的上一次出现位置，用于取消旧位置的贡献，确保树状数组中只有'最新出现位置'被标记为 1； 树状数组操作：modify 用于标记或取消标记位置，interval_query 通过前缀和差得到区间内不同元素的个数； 时间复杂度：排序查询的时间为 O(m logm)，遍历数组和处理查询的时间为 O(n logn + m logn)，总时间复杂度为 O((n+m) logn)，可轻松处理 1e6 级数据。

三、离线操作实战 2：采花（洛谷 P4113）—— 区间内出现≥2 次的元素个数统计

这道题是'HH 的项链'的进阶版，要求统计区间内'出现次数≥2'的元素个数，进一步考验对离线操作和树状数组的灵活运用。

题目链接：https://www.luogu.com.cn/problem/P4113

3.1 题目信息

• 来源：洛谷 P4113（HEOI2012）
• 难度：★★★★
• 核心考点：离线操作 + 树状数组 + 区间特定出现次数统计
• 题目描述：花园中有 n 朵花，每朵花有颜色（1~c）。有 m 个行程，每个行程是区间 [l, r]，求该区间内'出现次数≥2'的颜色种类数（公主不喜欢只出现一次的颜色）。
• 输入要求：第一行 n、c、m（花的个数、颜色数、行程数）；第二行 n 个整数（花的颜色 x[i]）；接下来 m 行，每行两个整数 l、r（1≤l≤r≤n）。
• 输出要求：对于每个行程，输出区间 [l, r] 内出现次数≥2 的颜色种类数。

3.2 问题分析（比 HH 的项链难在哪？）

HH 的项链统计'出现≥1 次'的元素个数，而本题统计'出现≥2 次'的元素个数，核心区别在于：

元素第一次出现：无贡献； 元素第二次出现：产生 1 点贡献（此时出现次数≥2）； 元素第三次及以上出现：贡献不变（仍为 1 点，因为种类数只算一次）。

因此，需要维护两个数组：

last[x]：颜色 x 上一次出现的位置； llast[x]：颜色 x 上上次出现的位置。

通过这两个数组，判断当前元素出现次数是否达到 2 次，进而更新树状数组的贡献。

3.3 离线操作核心思路

步骤 1：贡献规则定义

当颜色 x 第一次出现（last[x] = 0）：无贡献，仅更新 last[x] = 当前位置 i； 当颜色 x 第二次出现（llast[x] = 0）：产生 1 点贡献，将 last[x]（上一次位置）标记为 1（因为查询右端点≥i 时，last[x] 在区间内则 x 出现≥2 次），更新 llast[x] = last[x]，last[x] = i； 当颜色 x 第三次及以上出现（llast[x] ≠ 0）：贡献不变，先取消 llast[x] 的标记（因为上上次位置已不再影响'出现≥2 次'的统计），再标记 last[x] 的位置，更新 llast[x] = last[x]，last[x] = i。

步骤 2：离线处理流程

1. 读入所有操作：存储 m 个查询，记录原始编号；
2. 排序查询：按查询右端点 r 从小到大排序；
3. 按原查询顺序输出答案。

遍历数组 + 维护树状数组：

用 last[x] 记录 x 上一次出现位置，llast[x] 记录 x 上上次出现位置（初始均为 0）； 遍历数组 x[1..n]： a. 根据 last[x[i]] 和 llast[x[i]] 的状态，更新树状数组的标记（取消旧贡献、添加新贡献）； b. 更新 last[x[i]] 和 llast[x[i]]； c. 处理所有右端点 r=i 的查询：查询区间 [l, i] 的和（即出现≥2 次的颜色种类数），存入答案数组；

3.4 完整 C++ 代码

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
#define lowbit(x) (x & -x)
const int N = 2e6 + 10; // 适配 n=2e6 的范围
int n, c, m;
int x[N]; // 花的颜色数组
int tree[N]; // 树状数组：维护颜色出现≥2 次的贡献（1 表示有贡献，0 表示无）
int last[N], llast[N]; // last[x]：x 上一次出现位置；llast[x]：x 上上次出现位置
int ans[N]; // 存储答案，按查询原始编号排列
// 查询结构体
struct Query {
    int l, r, id;
} q[N];
// 排序规则：按右端点 r 从小到大排序
bool cmp(Query& a, Query& b) {
    return a.r < b.r;
}
// 树状数组单点修改：位置 pos 的数值增加 k（k=1 或 -1）
void modify(int pos, int k) {
    for (int i = pos; i <= n; i += lowbit(i)) {
        tree[i] += k;
    }
}
// 树状数组区间查询：[1, pos] 的前缀和
int query(int pos) {
    int sum = 0;
    for (int i = pos; i > 0; i -= lowbit(i)) {
        sum += tree[i];
    }
    return sum;
}
// 区间查询：[l, r] 的和（出现≥2 次的颜色种类数）
int interval_query(int l, int r) {
    return query(r) - query(l - 1);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> c >> m;
    for (int i = 1; i <= n; i++) {
        cin >> x[i];
    }
    for (int i = 1; i <= m; i++) {
        cin >> q[i].l >> q[i].r;
        q[i].id = i;
    }
    // 步骤 1：按查询右端点排序
    sort(q + 1, q + 1 + m, cmp);
    // 步骤 2：遍历数组，维护树状数组和查询
    int pos = 1; // 指向当前要处理的查询
    memset(last, 0, sizeof last);
    memset(llast, 0, sizeof llast);
    for (int i = 1; i <= n; i++) {
        int color = x[i];
        if (!last[color]) { // 第一次出现：无贡献，仅更新 last
            last[color] = i;
        } else if (!llast[color]) { // 第二次出现：添加 last[color] 的贡献（1）
            modify(last[color], 1);
            llast[color] = last[color];
            last[color] = i;
        } else { // 第三次及以上出现：取消 llast[color] 的贡献，添加 last[color] 的贡献
            modify(llast[color], -1);
            modify(last[color], 1);
            llast[color] = last[color];
            last[color] = i;
        }
        // 处理所有右端点为 i 的查询
        while (pos <= m && q[pos].r == i) {
            int l = q[pos].l;
            int id = q[pos].id;
            ans[id] = interval_query(l, i);
            pos++;
        }
    }
    // 步骤 3：按原始顺序输出答案
    for (int i = 1; i <= m; i++) {
        cout << ans[i] << endl;
    }
    return 0;
}

3.5 代码详解

1. 树状数组的作用：树状数组中 1 的位置代表'该位置是某颜色的第二次出现位置'，区间和即为该区间内出现≥2 次的颜色种类数；
2. 时间复杂度：与 HH 的项链一致，为 O((n+m) logn)，可处理 2e6 级数据。

贡献维护逻辑：

第一次出现：仅记录位置，无贡献； 第二次出现：标记上一次位置为 1（此时该颜色在区间内出现≥2 次，产生贡献）； 第三次及以上出现：取消上上次位置的标记（因为上上次位置已被上一次位置覆盖，不再影响'出现≥2 次'的统计），标记上一次位置为 1；

四、在线操作 vs 离线操作：如何选择？

通过两道离线例题的学习，我们可以总结出选择在线或离线操作的核心判断标准：

4.1 优先选择离线操作的场景

1. 问题涉及'区间内不同元素个数''区间内出现次数≥k 的元素个数'等复杂统计；
2. 在线操作时间复杂度太高（如 O(nm)），无法通过时间限制；
3. 查询结果仅依赖于区间的某个状态（如右端点固定时的前缀状态），与操作顺序无关。

4.2 优先选择在线操作的场景

1. 问题是基础区间统计（如区间求和、单点查询、区间修改等）；
2. 查询需要即时响应（如实时数据监控、在线系统等）；
3. 无法收集所有操作（如输入是流式数据，无法提前获取所有查询）。

4.3 离线操作的通用解题模板

对于树状数组相关的离线问题，可遵循以下模板：

1. 收集操作：读入所有修改和查询操作，为查询记录原始编号；
2. 排序操作：根据问题特性排序（如按查询右端点、左端点等）；
3. 遍历处理：按排序后的顺序遍历数组或操作，用树状数组维护所需状态（如标记位置、统计贡献等）；
4. 映射答案：将处理结果按查询的原始编号存入答案数组；
5. 输出答案：按原始查询顺序输出答案。

总结

在线操作和离线操作是树状数组进阶的核心思想，尤其是离线操作，能让看似复杂的区间统计问题变得简单可解。通过本文的两道例题，我们不仅掌握了'区间不同元素个数''区间出现≥2 次元素个数'的解法，更理解了离线操作'排序 + 树状数组统计'的核心逻辑。

学习离线操作的关键在于'转化思维'——不要被问题的表面复杂度吓住，而是思考如何通过排序、重排操作，将复杂问题转化为树状数组可处理的'单点修改 + 区间查询'模型。多做类似题目（如洛谷 P3605、P4054 等），就能熟练掌握这种思维方式。

希望本文能帮助你打通树状数组的离线操作难关，在算法竞赛和笔试中应对各类复杂区间统计问题！