【算法提高篇】（十一）树状数组实战练习题：带你从入门到进阶，彻底吃透 BIT 应用-171主机测评

前言

掌握树状数组（BIT）的基础操作后，真正的考验是将其应用到各类复杂场景中。树状数组的核心价值不仅在于单点修改和区间查询的高效实现，更在于与离散化、差分、贪心、DFS 等思想的结合，解决逆序对、图腾计数、 Promotion 统计等经典问题。

本文精选 6 道树状数组高频练习题，均来自洛谷等权威 OJ 平台，帮你拆解解题逻辑，掌握树状数组的灵活用法。刷完这 6 道题，你能彻底跳出模板的局限，真正理解树状数组的应用场景和解题技巧！下面就让我们正式开始吧！

练习题 1：逆序对（洛谷 P1908）

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

题目信息

来源：洛谷 P1908
难度：★★★
核心考点：树状数组 + 离散化，解决逆序对计数问题

题目描述

逆序对的定义：对于给定的正整数序列，逆序对是序列中满足 ai>aj 且 i<j 的有序对。给定一个长度为 n 的序列，求序列中逆序对的数目（序列中可能有重复数字）。

输入要求：第一行输入 n（序列长度），第二行输入 n 个整数（序列元素，每个数字不超过 109）。

输出要求：输出逆序对的数目。

核心思路

逆序对计数是树状数组的经典应用，直接暴力枚举（时间复杂度 O(n2)）会超时，树状数组可将时间复杂度优化至 O(nlogn)。

关键分析

对于序列中第 i 个元素 a[i]，我们需要统计前 i−1 个元素中比 a[i] 大的元素个数，所有位置的统计结果之和即为逆序对总数。

核心步骤

离散化处理：序列元素的取值范围可能高达 109，无法直接用树状数组维护，需将元素映射到 1∼n 的区间（因为序列长度为 n，元素种类最多为 n 种）；

树状数组维护：从左到右遍历序列，对于每个元素 a[i]：

查询树状数组中 “大于 a[i] 的元素个数”（即 query(max_rank) – query(rank[a[i]])，其中 max_rank 是离散化后的最大排名）；
将当前元素的排名插入树状数组（单点修改，计数 + 1）；

累加结果：每次查询的结果累加，最终得到逆序对总数。

完整 C++ 代码

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

#define lowbit(x) (x & -x)
typedef long long LL;
const int N = 5e5 + 10; // 适配n的最大范围

int n;
int a[N], t[N]; // a存储原序列，t存储用于离散化的序列
int m; // 离散化后的最大排名
unordered_map<int, int> mp; // 映射：元素值 -> 离散化后的排名
LL tree[N]; // 树状数组，维护元素出现次数

// 单点修改：将排名x的元素计数+1
void modify(int x) {
for (int i = x; i <= m; i += lowbit(i)) {
tree[i] += 1;
}
}

// 区间查询：查询[1, x]的元素个数（即排名≤x的元素个数）
LL query(int x) {
LL sum = 0;
for (int i = x; i > 0; i -= lowbit(i)) {
sum += tree[i];
}
return sum;
}

int main() {
ios::sync_with_stdio(false);
cin.tie(0);

cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
t[i] = a[i]; // 复制序列用于离散化
}

// 步骤1：离散化（去重+排序+映射）
sort(t + 1, t + 1 + n); // 排序
for (int i = 1; i <= n; i++) {
if (!mp.count(t[i])) { // 去重，避免重复映射
mp[t[i]] = ++m;
}
}

// 步骤2：遍历序列，统计逆序对
LL ans = 0;
for (int i = 1; i <= n; i++) {
int rank = mp[a[i]]; // 当前元素的离散化排名
// 前i-1个元素中比a[i]大的个数 = 总元素个数 – 排名≤rank的个数
ans += query(m) – query(rank);
modify(rank); // 插入当前元素的排名
}

cout << ans << endl;
return 0;
}

代码详解

离散化流程：

复制原序列到 t 数组，对 t 排序后去重，用 unordered_map 建立元素值到排名的映射，确保相同元素映射到同一排名，不同元素映射到不同排名；
离散化后，元素的相对大小关系不变，不影响逆序对的统计结果。

树状数组操作：

modify(x)：将排名 x 的元素计数 + 1，用于记录元素的出现；
query(x)：查询排名≤x 的元素总数，通过 query(m) – query(rank) 得到排名 > rank 的元素个数（即比当前元素大的个数）。

数据类型：逆序对总数可能高达 n(n−1)/2（当序列完全逆序时），n=5e5 时总数约 1.25e11，需用 long long 存储。

练习题 2：火柴排队（洛谷 P1966）

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

题目信息

来源：洛谷 P1966（NOIP2013 提高组）
难度：★★★★
核心考点：贪心 + 映射 + 逆序对 + 树状数组，解决最小交换次数问题

题目描述

两盒火柴各有 n 根，每根火柴有高度。两列火柴的距离定义为 ∑i=1n(ai−bi)2（ai 是第一列第 i 根火柴的高度，bi 是第二列第 i 根火柴的高度）。通过交换同一列中相邻火柴的位置，使两列火柴的距离最小，求最少交换次数（结果对 108−3 取模）。

输入要求：第一行输入 n，第二行输入第一列火柴的高度，第三行输入第二列火柴的高度（两列火柴高度均互不相同）。

输出要求：输出最少交换次数对 108−3 取模的结果。

核心思路

本题需分两步解决：先确定 “距离最小” 的火柴排列方式，再计算该排列所需的最少交换次数。

步骤 1：贪心确定最优排列

根据数学推导，当两列火柴的高度按相同大小顺序对应时，距离最小。证明如下：

设 a[i]<a[j]，b[i]<b[j]，若按顺序对应（a[i] 对 b[i]，a[j] 对 b[j]），距离为 (a[i]−b[i])2+(a[j]−b[j])2；
若逆序对应（a[i] 对 b[j]，a[j] 对 b[i]），距离为 (a[i]−b[j])2+(a[j]−b[i])2；
两式相减得 (a[i]−a[j])(b[j]−b[i])<0，说明按顺序对应时距离更小。

因此，最优方案是：将两列火柴分别排序，使第一列第 k 小的火柴对应第二列第 k 小的火柴。

步骤 2：映射与逆序对统计

最少交换次数等价于 “将一个数组调整为目标顺序所需的相邻交换次数”，该次数等于目标数组的逆序对个数（因为每次相邻交换可消除一个逆序对）。

具体实现：

对两列火柴分别 “值 – 下标” 绑定，按值从小到大排序；

建立映射关系：第一列排序后的第 i 个元素的原下标，对应第二列排序后的第 i 个元素的原下标，得到数组 c；

数组 c 的逆序对个数即为最少交换次数（因为交换 c 使其有序的过程，对应原火柴列的交换过程）。

完整 C++ 代码

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

#define lowbit(x) (x & -x)
typedef long long LL;
const int N = 1e5 + 10;
const int mod = 1e8 – 3; // 取模常数

int n;
// 结构体：存储火柴高度和原下标
struct Node {
int x; // 高度
int id; // 原下标
} a[N], b[N];
int c[N]; // 映射数组：c[a的原下标] = b的原下标
LL tree[N]; // 树状数组，维护逆序对统计

// 排序规则：按高度从小到大排序
bool cmp(Node& x, Node& y) {
return x.x < y.x;
}

// 单点修改：将位置x的计数+1
void modify(int x, int k) {
for (int i = x; i <= n; i += lowbit(i)) {
tree[i] += k;
}
}

// 区间查询：查询[1, x]的元素个数
LL query(int x) {
LL sum = 0;
for (int i = x; i > 0; i -= lowbit(i)) {
sum += tree[i];
}
return sum;
}

int main() {
ios::sync_with_stdio(false);
cin.tie(0);

cin >> n;
// 读入第一列火柴的高度和原下标
for (int i = 1; i <= n; i++) {
cin >> a[i].x;
a[i].id = i;
}
// 读入第二列火柴的高度和原下标
for (int i = 1; i <= n; i++) {
cin >> b[i].x;
b[i].id = i;
}

// 步骤1：按高度排序，建立映射关系
sort(a + 1, a + 1 + n, cmp);
sort(b + 1, b + 1 + n, cmp);
for (int i = 1; i <= n; i++) {
// a排序后的第i个元素的原下标，对应b排序后的第i个元素的原下标
c[a[i].id] = b[i].id;
}

// 步骤2：统计数组c的逆序对个数
LL ans = 0;
for (int i = 1; i <= n; i++) {
// 逆序对个数 = 已插入元素个数 – 比c[i]小的元素个数
ans += query(n) – query(c[i]);
ans %= mod; // 防止溢出，及时取模
modify(c[i], 1); // 插入当前元素
}

cout << ans % mod << endl;
return 0;
}

代码详解

结构体绑定：用 Node 结构体存储火柴的高度和原下标，排序后可保留原位置信息；

映射数组 c：排序后，两列火柴的 “值顺序” 一致，通过 c[a[i].id] = b[i].id 建立原下标之间的对应关系，数组 c 的有序化过程即为原火柴列的最优交换过程；

逆序对统计：与 “逆序对” 题目的统计逻辑一致，通过树状数组高效计算 c 数组的逆序对个数，结果对 108−3 取模。

练习题 3：楼兰图腾（洛谷 P10589）

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

题目信息

来源：洛谷 P10589
难度：★★★
核心考点：权值树状数组，统计特定形状的三元组（图腾）个数

题目描述

给定 n 个点，坐标为 (1,y1),(2,y2),…,(n,yn)（y1∼yn 是 1∼n 的一个排列，即水平和竖直位置均互不相同）。定义两种图腾：

V 图腾：满足 1≤i<j<k≤n 且 yi>yj、yj<yk（中间点是最小值）；

∧图腾：满足 1≤i<j<k≤n 且 yi<yj、yj>yk（中间点是最大值）。

求这两种图腾的个数。

输入要求：第一行输入 n，第二行输入 n 个整数 y1∼yn。

输出要求：输出两个整数，分别为 V 图腾和∧图腾的个数。

核心思路

对于每个点 j（中间点），统计其左侧和右侧满足条件的点的个数，两者相乘即为该点对对应图腾的贡献，所有点的贡献之和即为图腾总数。

关键分析

V 图腾贡献：对于点 j，左侧比 yj 大的点个数 × 右侧比 yj 大的点个数；

∧图腾贡献：对于点 j，左侧比 yj 小的点个数 × 右侧比 yj 小的点个数。

核心步骤

第一次遍历（左到右）：用树状数组统计每个点左侧比它大、比它小的点个数，分别存储在 up[j]（左侧比 yj 大的个数）和 down[j]（左侧比 yj 小的个数）；

第二次遍历（右到左）：清空树状数组，再次统计每个点右侧比它大、比它小的点个数，与左侧统计结果相乘，累加得到两种图腾的总数；

树状数组维护：由于 yj 是 1∼n 的排列，无需离散化，直接用权值树状数组维护点的出现情况。

完整 C++ 代码

#include <iostream>
#include <cstring>
using namespace std;

#define lowbit(x) (x & -x)
typedef long long LL;
const int N = 2e5 + 10;

int n;
int a[N]; // 存储y数组（a[j] = y_j）
LL up[N], down[N]; // up[j]：左侧比a[j]大的个数；down[j]：左侧比a[j]小的个数
LL tree[N]; // 权值树状数组

// 单点修改：将值x的点标记为已出现（计数+1）
void modify(int x, int k) {
for (int i = x; i <= n; i += lowbit(i)) {
tree[i] += k;
}
}

// 区间查询：查询[1, x]的点个数（即值≤x的点个数）
LL query(int x) {
LL sum = 0;
for (int i = x; i > 0; i -= lowbit(i)) {
sum += tree[i];
}
return sum;
}

int main() {
ios::sync_with_stdio(false);
cin.tie(0);

cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}

// 第一次遍历：左到右，统计左侧比a[i]大、小的个数
memset(tree, 0, sizeof tree);
for (int i = 1; i <= n; i++) {
int val = a[i];
down[i] = query(val – 1); // 左侧比val小的个数：[1, val-1]的和
up[i] = query(n) – query(val); // 左侧比val大的个数：总个数 – [1, val]的和
modify(val, 1); // 标记当前点已出现
}

// 第二次遍历：右到左，统计右侧比a[i]大、小的个数，计算贡献
memset(tree, 0, sizeof tree);
LL v_tot = 0, lambda_tot = 0;
for (int i = n; i >= 1; i–) {
int val = a[i];
LL right_down = query(val – 1); // 右侧比val小的个数
LL right_up = query(n) – query(val); // 右侧比val大的个数

v_tot += up[i] * right_up; // V图腾贡献：左大 × 右大
lambda_tot += down[i] * right_down; // ∧图腾贡献：左小 × 右小

modify(val, 1); // 标记当前点已出现
}

cout << v_tot << " " << lambda_tot << endl;
return 0;
}

代码详解

两次遍历：左到右遍历统计左侧信息，右到左遍历统计右侧信息，避免重复计算；

权值树状数组：由于 yj 是 1∼n 的排列，每个值唯一且范围适中，直接以 yj 作为树状数组的下标，维护点的出现次数；

贡献计算：每个中间点的贡献是左侧符合条件的点个数与右侧符合条件的点个数的乘积，累加后得到最终结果。

练习题 4：Promotion Counting（洛谷 P3605）

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

题目信息

来源：洛谷 P3605（USACO17JAN）
难度：★★★★
核心考点：树状数组 + 离散化 + DFS，统计树上每个节点的下属中能力值更高的个数

题目描述

公司组织成一棵树，1 号奶牛为总裁（根节点），每个奶牛有唯一的能力值 pi。对于每头奶牛 i，求其下属（所有后代节点）中能力值大于 pi 的奶牛个数。

输入要求：第一行输入 n，接下来 n 行输入 p1∼pn（能力值，互不相同），再接下来 n−1 行输入奶牛 2∼n 的上司编号。

输出要求：输出 n 行，第 i 行输出奶牛 i 的下属中能力值更高的个数。

核心思路

这是一道树状数组与 DFS 结合的经典题，核心是用 “树上差分” 的思想，通过 DFS 遍历树的过程中维护树状数组，统计子树内的符合条件的节点个数。

关键分析

树的子树查询：对于节点 u，其下属（子树）的所有节点在 DFS 遍历的 “进入时间” 和 “退出时间” 之间（即子树是一个连续的时间区间）；
能力值离散化：能力值范围可能很大，需离散化到 1∼n 的区间；
树状数组维护：DFS 遍历过程中，进入节点时记录当前树状数组中 “能力值大于 pu 的节点个数”，退出节点时再次查询，两者的差值即为子树内能力值大于 pu 的节点个数（因为退出时子树内所有节点已被插入树状数组）。

核心步骤

离散化能力值：将能力值映射到 1∼n 的排名（能力值越大，排名越高）；

建树：用邻接表存储树的结构（上司→下属）；

DFS 遍历：

进入节点 u 时，查询树状数组中 “排名> 当前节点排名” 的个数，存入 ret[u]（初始为负，用于后续计算差值）；
递归遍历所有子节点；
退出节点 u 时，再次查询树状数组中 “排名> 当前节点排名” 的个数，与进入时的查询结果相加，得到子树内符合条件的节点个数；
将当前节点的排名插入树状数组（供父节点查询）。

完整 C++ 代码

#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <vector>
using namespace std;

#define lowbit(x) (x & -x)
const int N = 1e5 + 10;

int n;
int p[N], t[N]; // p存储能力值，t存储用于离散化的能力值
unordered_map<int, int> mp; // 映射：能力值 -> 离散化排名（值越大，排名越高）
vector<int> edges[N]; // 邻接表：edges[fa]存储fa的下属
int ret[N]; // 存储每个节点的答案
int tree[N]; // 树状数组，维护排名的出现次数

// 单点修改：将排名x的节点计数+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;
}

// DFS遍历树
void dfs(int u) {
int rank = p[u]; // 当前节点的能力值排名
// 进入节点u：查询当前树状数组中排名>rank的节点个数（即已插入的非子树节点）
ret[u] -= query(n) – query(rank);
// 递归遍历子节点
for (auto v : edges[u]) {
dfs(v);
}
// 退出节点u：查询当前树状数组中排名>rank的节点个数（子树节点已全部插入）
ret[u] += query(n) – query(rank);
// 将当前节点的排名插入树状数组
modify(rank, 1);
}

int main() {
ios::sync_with_stdio(false);
cin.tie(0);

cin >> n;
// 读入能力值
for (int i = 1; i <= n; i++) {
cin >> p[i];
t[i] = p[i];
}
// 读入树的结构（下属→上司）
for (int i = 2; i <= n; i++) {
int fa;
cin >> fa;
edges[fa].push_back(i);
}

// 离散化能力值（值越大，排名越高）
sort(t + 1, t + 1 + n);
for (int i = 1; i <= n; i++) {
mp[t[i]] = i;
}
for (int i = 1; i <= n; i++) {
p[i] = mp[p[i]];
}

// DFS遍历统计答案
dfs(1);

// 输出结果
for (int i = 1; i <= n; i++) {
cout << ret[i] << endl;
}

return 0;
}

代码详解

离散化排名：能力值越大，排名越高，方便查询 “大于当前能力值” 的节点个数（即 query(n) – query(rank)）；

DFS 差分思想：进入节点时记录 “非子树节点” 的符合条件个数（负向），退出时记录 “包含子树节点” 的符合条件个数（正向），两者相加即为子树内的符合条件个数；

邻接表建树：由于是树结构（无环），用邻接表存储上司与下属的关系，DFS 遍历无重复。

练习题 5：计数问题（洛谷 P4054）

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

题目信息

来源：洛谷 P4054（JSOI2009）
难度：★★★
核心考点：二维树状数组，统计子矩阵中特定权值的出现次数

题目描述

给定 n×m 的方格，每个格子有一个整数权值。支持两种操作：

操作 1：x y c，将格子 (x,y) 的权值改为 c；

操作 2：x1 x2 y1 y2 c，查询子矩阵 [x1,x2]×[y1,y2] 中权值为 c 的格子个数。

输入要求：第一行输入 n,m，接下来 n 行输入初始权值，再输入 Q（操作次数），接下来 Q 行输入操作。

输出要求：对于每个操作 2，输出对应的格子个数。

核心思路

本题需要统计子矩阵中特定权值的出现次数，核心是用 “多个二维树状数组” 分别维护每个权值的位置分布。

关键分析

权值范围较小（根据示例和题目隐含条件，权值通常在 1∼100 之间），可以为每个权值创建一个二维树状数组；
每个二维树状数组维护对应权值在方格中的出现情况（格子有该权值则为 1，否则为 0）；
操作 1（修改权值）：先在原权值的二维树状数组中删除该格子（单点修改 – 1），再在新权值的二维树状数组中添加该格子（单点修改 + 1）；
操作 2（查询）：在权值 c 对应的二维树状数组中查询子矩阵的和（即该权值的出现次数）。

核心步骤

初始化：为每个可能的权值创建二维树状数组，遍历初始方格，将每个格子的权值对应的树状数组中该位置标记为 1；

处理操作 1：获取格子 (x,y) 的原权值 oldc，在 oldc 的树状数组中执行 modify(x,y,-1)，再在新权值 c 的树状数组中执行 modify(x,y,1)，更新格子的权值；

处理操作 2：在权值 c 的树状数组中查询子矩阵 [x1,x2]×[y1,y2] 的和，输出结果。

完整 C++ 代码

#include <iostream>
using namespace std;

#define lowbit(x) (x & -x)
const int N = 310; // 方格最大尺寸
const int M = 110; // 权值最大范围（1~100）

int n, m;
int a[N][N]; // 存储每个格子的当前权值

// 二维树状数组结构体
struct BIT2D {
int tree[N][N];
// 单点修改：(x,y)位置的计数±1
void modify(int x, int y, int k) {
for (int i = x; i <= n; i += lowbit(i)) {
for (int j = y; j <= m; j += lowbit(j)) {
tree[i][j] += k;
}
}
}
// 区间查询：查询(1,1)到(x,y)的和
int query(int x, int y) {
int sum = 0;
for (int i = x; i > 0; i -= lowbit(i)) {
for (int j = y; j > 0; j -= lowbit(j)) {
sum += tree[i][j];
}
}
return sum;
}
} bit[M]; // bit[c]：维护权值为c的格子分布

// 子矩阵查询：(x1,y1)到(x2,y2)的和（容斥原理）
int matrix_query(int c, int x1, int x2, int y1, int y2) {
return bit[c].query(x2, y2) – bit[c].query(x1 – 1, y2) –
bit[c].query(x2, y1 – 1) + bit[c].query(x1 – 1, y1 – 1);
}

int main() {
ios::sync_with_stdio(false);
cin.tie(0);

cin >> n >> m;
// 初始化：为每个格子的初始权值标记
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> a[i][j];
int c = a[i][j];
bit[c].modify(i, j, 1);
}
}

int Q;
cin >> Q;
while (Q–) {
int op;
cin >> op;
if (op == 1) {
// 操作1：修改格子(x,y)的权值为c
int x, y, c;
cin >> x >> y >> c;
int old_c = a[x][y];
// 从原权值的树状数组中删除
bit[old_c].modify(x, y, -1);
// 加入新权值的树状数组
bit[c].modify(x, y, 1);
// 更新当前格子的权值
a[x][y] = c;
} else {
// 操作2：查询子矩阵[x1,x2]×[y1,y2]中权值为c的个数
int x1, x2, y1, y2, c;
cin >> x1 >> x2 >> y1 >> y2 >> c;
cout << matrix_query(c, x1, x2, y1, y2) << endl;
}
}

return 0;
}

代码详解

多二维树状数组：为每个权值创建一个二维树状数组，空间复杂度为 O(M×N×N)（M=110，N=310），完全可控；

二维树状数组操作：单点修改和区间查询与基础二维树状数组一致，通过双重循环执行 lowbit 操作；

容斥原理查询：子矩阵和通过 query(x2,y2) – query(x1-1,y2) – query(x2,y1-1) + query(x1-1,y1-1) 计算，避免重复或遗漏。

练习题 6：LOG（洛谷 P3586）

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

题目信息

来源：洛谷 P3586（POI2015）
难度：★★★★★
核心考点：树状数组 + 离散化 + 问题转化，解决复杂的查询可行性问题

题目描述

维护一个长度为 n 的序列（初始全为 0），支持两种操作：

操作 U：U k a，将序列中第 k 个数修改为 a；

操作 Z：Z c s，每次选出 c 个正数，将它们各减 1，询问能否进行 s 次这样的操作（每次查询独立，不修改序列）。

输入要求：第一行输入 n,m（序列长度和操作次数），接下来 m 行输入操作。

输出要求：对于每个操作 Z，输出 “TAK”（可行）或 “NIE”（不可行）。

核心思路

本题的关键是将 “能否进行 s 次操作” 转化为可通过树状数组统计的条件，核心是问题转化和数学推导。

关键分析

将序列中的每个数看作 “石子堆的高度”，操作 Z 的本质是：能否通过 s 次操作，每次从 c 个堆中各取 1 个石子，最终取完所有需要取的石子。

转化为数学条件：

设序列中高度 ≥ s 的石子堆个数为 cnt，这些堆最多能提供 cnt×s 个石子（但实际只需取 s 次，每次取 c 个，共需 c×s 个石子）；
对于高度 < s 的石子堆，总石子数为 sum（即所有高度 < s 的堆的高度之和）；
- cnt：序列中 ≥ s 的元素个数；
- sum：序列中 < s 的元素总和；
- total：序列中所有元素的总和（total=sum+sumai≥sai）。

核心步骤

离散化：所有操作中的 a 和 s 可能很大，需离散化到 1∼m 的区间（m 是操作次数）；

树状数组维护：用两个树状数组：

A：维护元素的总和（即每个离散化后的值对应的元素总和）；
B：维护元素的个数（即每个离散化后的值对应的元素个数）；

处理操作 U：修改第 k 个数时，先删除原数值的贡献（A 和 B 中减去原数值和 1），再添加新数值的贡献（A 和 B 中加上新数值和 1）；

处理操作 Z：查询 c,s 时：

离散化 s 得到 ranks；
计算 cnt=B.query(maxrank)−B.query(ranks−1)（≥ s 的元素个数）；
计算 sumgeqs=A.query(maxrank)−A.query(ranks−1)（≥ s 的元素总和）；
sumless=A.query(ranks−1)（< s 的元素总和）；
total=A.query(maxrank)（总元素总和）；
检查条件：total≥(LL)c×s 且 sumless≥(LL)max(0,c−cnt)×s，满足则输出 “TAK”，否则输出 “NIE”。

完整 C++ 代码

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

#define lowbit(x) (x & -x)
typedef long long LL;
const int N = 1e6 + 10;

int n, m;
// 存储所有操作
struct Op {
char op;
int x, y; // U: x=k, y=a; Z: x=c, y=s
} op[N];
int t[N]; // 存储所有需要离散化的值（a和s）
int a[N]; // 存储序列当前值（初始为0）
unordered_map<int, int> mp; // 映射：原始值 -> 离散化排名

// 树状数组结构体
struct BIT {
LL tree[N];
void modify(int x, LL k) {
for (int i = x; i <= m; i += lowbit(i)) {
tree[i] += k;
}
}
LL query(int x) {
LL sum = 0;
for (int i = x; i > 0; i -= lowbit(i)) {
sum += tree[i];
}
return sum;
}
} A, B; // A维护总和，B维护个数

int main() {
// 用scanf加速输入（数据量较大）
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
scanf(" %c", &op[i].op);
scanf("%d%d", &op[i].x, &op[i].y);
t[i] = op[i].y; // 收集所有a和s的值，用于离散化
}

// 步骤1：离散化所有需要用到的值
sort(t + 1, t + 1 + m);
int max_rank = 0;
for (int i = 1; i <= m; i++) {
if (!mp.count(t[i])) {
mp[t[i]] = ++max_rank;
}
}

// 步骤2：处理所有操作
for (int i = 1; i <= m; i++) {
if (op[i].op == 'U') {
// 操作U：修改第k个数为a
int k = op[i].x;
int new_val = op[i].y;
int old_val = a[k];

// 1. 删除原数值的贡献
if (old_val != 0) {
int r = mp[old_val];
A.modify(r, -old_val);
B.modify(r, -1);
}

// 2. 添加新数值的贡献
if (new_val != 0) {
int r = mp[new_val];
A.modify(r, new_val);
B.modify(r, 1);
}

// 3. 更新序列当前值
a[k] = new_val;
} else {
// 操作Z：查询能否进行s次操作
int c = op[i].x;
int s = op[i].y;

// 计算所需统计量
LL total = A.query(max_rank); // 总元素总和
if (total < (LL)c * s) { // 总石子数不足，直接不可行
puts("NIE");
continue;
}

// 离散化s，找到其排名
int rank_s = mp.count(s) ? mp[s] : 0;
// cnt：≥s的元素个数 = 总个数 – <s的个数
LL cnt = B.query(max_rank) – B.query(rank_s – 1);
// sum_less：<s的元素总和
LL sum_less = A.query(rank_s – 1);

// 检查条件：sum_less ≥ max(0, c – cnt) * s
LL required = (LL)max(0, c – (int)cnt) * s;
if (sum_less >= required) {
puts("TAK");
} else {
puts("NIE");
}
}
}

return 0;
}

代码详解

问题转化：将复杂的操作可行性问题转化为 “总石子数” 和 “部分和、部分个数” 的统计，是本题的核心；

双树状数组维护：A 维护元素总和，B 维护元素个数，通过离散化处理大数值范围；

离散化技巧：收集所有操作中的 a 和 s 进行离散化，避免遗漏可能的值；

条件判断：先检查总石子数是否足够，再检查低高度堆的总石子数是否能补充高高度堆的不足，确保判断的正确性。

6 道练习题核心总结

题型与核心技巧对应表

题号题型核心技巧树状数组作用

1	逆序对计数	离散化 + 权值统计	统计前缀中特定范围的元素个数
2	火柴排队	贪心映射 + 逆序对	统计数组有序化所需的交换次数
3	楼兰图腾	双向遍历 + 权值统计	统计左右两侧特定大小关系的元素个数
4	Promotion Counting	DFS + 树上差分	统计子树内特定条件的节点个数
5	计数问题	多二维树状数组	维护不同权值的位置分布，统计子矩阵个数
6	LOG	问题转化 + 双树状数组	统计总和、个数，验证可行性条件

通用解题技巧

离散化：处理大数值范围问题的必备技巧，将值映射到小范围，适配树状数组的下标要求；

问题转化：将复杂问题（如 LOG 的可行性查询）转化为树状数组可统计的 “和、个数、范围查询”；

多树状数组：需要维护多种信息时（如总和和个数、不同权值），使用多个树状数组分别维护；

结合其他算法：树状数组常与 DFS、贪心、差分等结合，解决树、序列的复杂统计问题；

数据类型：注意结果溢出，优先使用long long存储统计结果和中间变量。

总结

通过以上这些练习题的训练，相信大家已经能熟练运用树状数组的基本原理了。希望大家能多多练习加以巩固~

前言

目录

练习题 1：逆序对（洛谷 P1908）

题目信息

题目描述

核心思路

关键分析

核心步骤

完整 C++ 代码

代码详解

练习题 2：火柴排队（洛谷 P1966）

题目信息

题目描述

核心思路

步骤 1：贪心确定最优排列

步骤 2：映射与逆序对统计

完整 C++ 代码

代码详解

练习题 3：楼兰图腾（洛谷 P10589）

题目信息

题目描述

核心思路

关键分析

核心步骤

完整 C++ 代码

代码详解

练习题 4：Promotion Counting（洛谷 P3605）

题目信息

题目描述

核心思路

关键分析

核心步骤

完整 C++ 代码

代码详解

练习题 5：计数问题（洛谷 P4054）

题目信息

题目描述

核心思路

关键分析

核心步骤

完整 C++ 代码

代码详解

练习题 6：LOG（洛谷 P3586）

题目信息

题目描述

核心思路

关键分析

核心步骤

完整 C++ 代码

代码详解

6 道练习题核心总结

题型与核心技巧对应表

通用解题技巧

总结

相关推荐

评论 抢沙发

热门标签

热门文章

最新文章

归档

分类

评论抢沙发