【算法提高篇】（十二）树状数组进阶：在线与离线操作实战，解锁区间统计新姿势

前言

在树状数组的学习中，我们已经掌握了一维、二维的各类基础操作（单点修改、区间查询等），但面对复杂的区间统计问题（如 “查询区间内不同元素的个数”），单纯的基础操作已经难以应对。这时候，在线操作与离线操作的思想就成了破局的关键。 在线与离线并非某种具体算法，而是两种截然不同的解题思路 —— 在线操作要求 “即时响应查询”，离线操作则允许 “先收集所有操作，再重新排序处理”。树状数组作为高效的区间统计工具，与这两种思想结合后，能轻松解决各类复杂场景问题。 本文将从 “在线 / 离线的核心概念” 入手，结合两道经典例题（HH 的项链、采花），深度解析树状数组在离线操作中的应用，带你掌握 “离线排序 + 树状数组统计” 的解题模板，让复杂区间问题迎刃而解！下面就让我们正式开始吧！

目录

前言

一、先搞懂：在线操作与离线操作的核心区别

1.1 核心概念拆解

（1）在线操作（Online Operation）

（2）离线操作（Offline Operation）

1.2 关键区别对比表

1.3 为什么离线操作能解决复杂问题？

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

2.1 题目信息

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

2.3 离线操作核心思路

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

步骤 2：离线处理流程

2.4 完整 C++ 代码

2.5 代码详解

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

3.1 题目信息

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

3.3 离线操作核心思路

步骤 1：贡献规则定义

步骤 2：离线处理流程

3.4 完整 C++ 代码

3.5 代码详解

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

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

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

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

总结

一、先搞懂：在线操作与离线操作的核心区别

在算法题中，所有涉及 “修改” 和 “查询” 的操作都可以按 “时间轴” 和 “处理顺序” 分为两类 —— 在线操作和离线操作。理解它们的区别，是选择正确解题思路的前提。

1.1 核心概念拆解

（1）在线操作（Online Operation）

• 定义：每一个查询操作都需要 “即时处理、即时输出答案”，不能等待后续操作输入后再统一计算。
• 特点：必须动态响应，处理顺序严格遵循输入顺序，无法改变操作的执行顺序。
• 适用场景：修改和查询操作穿插紧密，且查询结果依赖于实时的修改状态（如动态区间求和、单点查询等基础树状数组问题）。
• 例子：之前学的 “单点修改 + 区间查询” 模板题（LibreOJ 130）就是典型的在线操作 —— 每次修改后可能紧跟查询，必须立即返回结果。

（2）离线操作（Offline Operation）

• 定义：先将所有的修改和查询操作全部读入（收集起来），然后根据问题的特性，重新安排操作的处理顺序，最后按原查询的时间轴输出答案。
• 特点：不即时响应查询，允许 “打乱操作顺序”，通过排序、重排等方式简化计算，往往能将复杂问题转化为树状数组可处理的 “单点修改 + 区间查询” 模型。
• 适用场景：查询结果不依赖于实时修改顺序，仅依赖于最终的某个状态（如统计区间内不同元素个数、区间内出现次数≥2 的元素个数等）。
• 例子：后面要讲的 “HH 的项链” 问题 —— 查询区间内不同贝壳的种类数，若用在线操作会超时，但用离线操作 + 树状数组可将时间复杂度优化至 O (nlogn)。

1.2 关键区别对比表

1.3 为什么离线操作能解决复杂问题？

很多复杂问题无法用在线操作直接解决，核心原因是 “查询条件复杂”（如统计区间内不同元素个数）—— 若按在线思路，每次查询都要遍历区间，时间复杂度会达到 O (nm)，对于 n=1e6、m=1e6 的场景完全超时。

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

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

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

二、离线操作实战 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] 的区间和，将结果存入答案数组（按原始编号映射）；
4. 按原查询顺序输出答案。

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 代码详解

1. 查询结构体与排序：用Query结构体存储查询的 l、r 和原始编号 id，按 r 排序后，保证遍历数组到 i 时，能处理所有右端点为 i 的查询；
2. last 数组：记录每个元素的上一次出现位置，用于取消旧位置的贡献，确保树状数组中只有 “最新出现位置” 被标记为 1；
3. 树状数组操作：modify用于标记或取消标记位置，interval_query通过前缀和差得到区间内不同元素的个数；
4. 时间复杂度：排序查询的时间为 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 次的颜色种类数），存入答案数组；
4. 按原查询顺序输出答案。

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 次” 的统计），标记上一次位置为 1；
2. 树状数组的作用：树状数组中 1 的位置代表 “该位置是某颜色的第二次出现位置”，区间和即为该区间内出现≥2 次的颜色种类数；
3. 时间复杂度：与 HH 的项链一致，为 O ((n+m) logn)，可处理 2e6 级数据。

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

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

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

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

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

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

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

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

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

总结

在线操作和离线操作是树状数组进阶的核心思想，尤其是离线操作，能让看似复杂的区间统计问题变得简单可解。通过本文的两道例题，我们不仅掌握了 “区间不同元素个数”“区间出现≥2 次元素个数” 的解法，更理解了离线操作 “排序 + 树状数组统计” 的核心逻辑。 学习离线操作的关键在于 “转化思维”—— 不要被问题的表面复杂度吓住，而是思考如何通过排序、重排操作，将复杂问题转化为树状数组可处理的 “单点修改 + 区间查询” 模型。多做类似题目（如洛谷 P3605、P4054 等），就能熟练掌握这种思维方式。 希望本文能帮助你打通树状数组的离线操作难关，在算法竞赛和笔试中应对各类复杂区间统计问题！如果有疑问，欢迎在评论区留言讨论～ 创作不易，点个赞再走吧！ 🚀