企业官网建设流程全解析

简介：一套围绕洛谷树状数组题型的算法学习资料包，面向正在备战算法竞赛或初学数据结构的读者，重点解决动态区间查询、单点更新等高频问题。压缩包共6个文件，包含C/C++源程序、可执行文件及运行输出，总大小仅452KB，麻雀虽小但覆盖了从模板实现到例题调试的完整流程。已有1412人浏览学习，适合希望快速上手树状数组的初学者参考。内容从树状数组的基本结构与初始化讲起，逐步拆解单点更新、区间查询的实现思路，并给出时间复杂度分析和与线段树的对比要点；随附洛谷P1428“小鱼比可爱”的C语言解法与可运行程序，方便对照代码查看运行输出、自行修改实验。通过这套资料，读者既能获得可直接调用的树状数组模板，又能借助典型例题理解算法在不同场景下的应用方式，对刷题和竞赛备赛都有实际帮助。

1. 树状数组：为什么题库里到处都是它的模板题

树状数组（Binary Indexed Tree）是我在算法题里用得最多的数据结构，没有之一。它代码量只有线段树的五分之一，却能稳定支撑单点修改、区间求和、逆序对、动态第 k 小这些高频需求。第一次接触的人多半被lowbit那行代码劝退，但只要理解c[i]到底在维护哪一段区间，后面就是一套可以完全照抄的固定模板。这篇笔记面向正在刷树状数组专题的读者：从 lowbit 讲到差分，再讲到离散化逆序对和倍增第 k 小，原理、模板、翻车点一条龙讲清楚。它值得投入，因为这套结构在竞赛里是必拿分项，在工作里做频次统计、排名维护时同样能直接搬过去用。

2. 从 lowbit 到模板：把树状数组的存储与更新一次看懂

2.1 lowbit 到底在取什么：存储结构的二进制视角

树状数组的底层思想是：每个下标x的更新和查询都只沿着二进制的最低位 1 移动。lowbit(x) = x & -x，它的值是x的二进制表示里最低位的 1 所对应的整数。比如lowbit(6) = 2，因为 6 的二进制是110，最低位的 1 在第二位；lowbit(8) = 8，因为1000的最低位的 1 就是最高位。

树状数组本体是一个数组c[1..n]，其中c[i]维护的是原数组a[i - lowbit(i) + 1 .. i]这一段区间的和。这意味着每个c[i]管的是一个长度恰好为lowbit(i)的连续段，而这些段彼此覆盖交错，形成了一棵逻辑上的树。查询前缀和时，我们每次把下标减去lowbit(i)，就能跳到上一段不相交的区间；更新时，每次加上lowbit(i)，就能找到所有覆盖当前下标的区间节点。

理解这个存储规则后，整个树状数组就没有黑匣子了。后面不管写单点修改、差分还是倍增第 k 小，核心都是lowbit的加减。我见过有人死记模板，遇到区间修改就懵，根源就在于没搞懂c[i]存的是哪一段，所以这里的二进制视角值得花十分钟吃透。

2.2 单点修改 add 和前缀查询 query 的最小模板

竞赛和工程里最常用的模板是 C++ 版本，核心就两个函数加一个lowbit。以下代码可以直接作为刷题基座，n 是原数组长度，c 是树状数组本体：

#include <bits/stdc++.h> using namespace std; const int MAXN = 1e5 + 5; int n; long long c[MAXN]; // 树状数组本体，下标从 1 开始有效 int lowbit(int x) { return x & -x; // 取最低位的 1 } void add(int pos, long long delta) { // 原数组 a[pos] 增加 delta（delta 可为负） for (int i = pos; i <= n; i += lowbit(i)) { c[i] += delta; // 所有覆盖 pos 的区间节点都要改 } } long long query(int pos) { // 返回原数组 a[1] 到 a[pos] 的前缀和 long long res = 0; for (int i = pos; i > 0; i -= lowbit(i)) { res += c[i]; // 累加互不重叠的区间和 } return res; } long long rangeSum(int l, int r) { // 区间求和，闭区间 [l, r] return query(r) - query(l - 1); }

逻辑说明：add从pos开始向上跳，每次都进入一个覆盖pos的更大区间，所以一次修改最多更新O(log n)个节点。query从pos开始向下跳，lowbit(i)恰好等于c[i]管辖的区间长度，跳过的节点刚好把[1, pos]完整切成若干段不重叠区间，累加即得前缀和。

参数说明里最容易忽略的是：pos必须是 1-based 下标；n必须在全局提前设定，数组c的长度至少开到n + 1；delta用long long，防止单次累加在极端数据下溢出int。区间求和用闭区间[l, r]，注意是query(r) - query(l - 1)，不是query(r) - query(l)，这个减 1 的坑在后面有专门一节讲。

2.3 建树的两种姿势：add 逐个插入与 O(n) 直构

最常见的建树方法是先把c清零，然后对每个位置调用add(i, a[i])，复杂度O(n log n)。这个写法直观、不易错，适合比赛赶时间。代码如下：

memset(c, 0, sizeof(c)); for (int i = 1; i <= n; ++i) { add(i, a[i]); // 逐个插入，简单但多一个 log }

如果数据规模到了1e6且多次多组输入，O(n log n)的建树可能会成为常数瓶颈。这时可以用O(n)直构：先算原数组前缀和，再按pre[i] - pre[i - lowbit(i)]直接填c[i]。更常见的实现是下面这种原地累加写法：

for (int i = 1; i <= n; ++i) { c[i] += a[i]; // 先把自己的值放进去 int nxt = i + lowbit(i); if (nxt <= n) { c[nxt] += c[i]; // 把当前区间的和累加到父节点 } }

逻辑说明：每个c[i]的管辖区间是[i - lowbit(i) + 1, i]，它的直接父节点是i + lowbit(i)，而c[nxt]的管辖区间恰好完全包含c[i]的管辖区间，所以把c[i]累加进去即可完成自底向上的构建。

我一般会在单组数据且n <= 2e5时无脑用add建树，代码短、不容易写错；只有当输入规模大、组数多时才换 O(n) 直构。两者结果完全一致，混用也不会出问题，但千万别对一棵已经建好的树再跑一遍累加，那会把值翻倍。

3. 差分树状数组：区间修改怎么变成两个单点更新

3.1 差分数组的定义与区间修改的等价变形

树状数组原生只支持单点修改加前缀查询，但算法题里大量出现“区间修改 + 区间查询”，直接裸上会超时。常见做法是引入差分数组：定义b[i] = a[i] - a[i - 1]，其中b[1] = a[1]，那么a[pos] = b[1] + b[2] + ... + b[pos]，也就是对差分数组做前缀和就能还原原数组。

对原数组做一次“区间[l, r]整体加v”的操作，在差分数组上的效果只有两处改动：b[l] += v，b[r + 1] -= v。因为区间内部的相邻差值没有变，只有区间边界处会跳变。于是区间修改从“遍历区间内每个元素”降成了两个单点更新，配合树状数组的add，单次修改复杂度稳定在O(log n)。

这个技巧的核心价值在于：树状数组模板完全不需要改，只换一层调用关系即可。差分数组本身可以理解成“把区间操作翻译成边界操作”，这是算法题里的通用思路，线段树懒标记虽然也能做，但对树状数组而言，差分的代码量少得多。前提是你能接受：查询单点时得到的是原数组的值，而不再是差分值本身。

3.2 区间修改 + 单点查询的完整实现

直接复用第二章的add和query，新的操作层放在业务函数里：

void rangeAdd(int l, int r, long long v) { // 原数组区间 [l, r] 整体加 v add(l, v); // 差分头部加 v if (r + 1 <= n) { // 防止差分尾部越界 add(r + 1, -v); // 差分尾部减 v，抵消影响 } } long long pointQuery(int pos) { // 单点查询，实际是对差分数组求前缀和 return query(pos); }

逻辑说明：add(l, v)让b[l]变大，于是后续所有a[pos]（pos >= l）的前缀和都会加上v；add(r + 1, -v)让b[r + 1]变小，于是pos >= r + 1处前缀和又被拉回来，最终只有[l, r]内的位置真正加上了v。pointQuery只是对普通树状数组做了一次前缀查询，含义却完全不同——它查的是差分数组的前缀和，也就是原数组单点值。

参数说明：v可以为负数，这正好对应区间减操作；r == n时r + 1 == n + 1超出下界，很多模板直接不判断，把树状数组n开成MAXN - 1让它自然失效，但那是危险习惯，因为i += lowbit(i)一旦超过MAXN就会越界写坏内存。我建议显式判断r + 1 <= n，多一行代码换整个程序的稳定性。

3.3 区间修改 + 区间查询：两个树状数组维护 d[i] 与 i * d[i]

如果题目同时要求区间修改和区间求和，一个差分树状数组不够，因为a的区间和不是简单的b的前缀和。推导过程很短：对差分数组b，a[1] + ... + a[x]中每个b[i]出现的次数是x - i + 1，于是变成(x + 1) * sum(b[i]) - sum(i * b[i])。所以要同时维护b[i]和i * b[i]两个前缀和，对应两个树状数组：

long long bit1[MAXN], bit2[MAXN]; // bit1 存 b[i]，bit2 存 i * b[i] void addPoint(long long c[], int pos, long long v) { for (int i = pos; i <= n; i += lowbit(i)) { c[i] += v; } } void rangeAdd(int l, int r, long long v) { addPoint(bit1, l, v); addPoint(bit1, r + 1, -v); addPoint(bit2, l, l * v); addPoint(bit2, r + 1, -(r + 1) * v); } long long prefixSum(int x) { // 原数组 [1, x] 的区间和 long long s1 = 0, s2 = 0; for (int i = x; i > 0; i -= lowbit(i)) { s1 += bit1[i]; s2 += bit2[i]; } return (x + 1) * s1 - s2; } long long rangeSum(int l, int r) { return prefixSum(r) - prefixSum(l - 1); }

逻辑说明：bit1维护的是差分值序列的前缀和，bit2维护的是下标乘以差分值的前缀和。因为差分数组每次区间修改在l和r + 1两点各打一个标记，所以两个树状数组各自只需要两个单点更新；而查询时按推导公式把两个前缀和组合起来，就得到原数组前缀和，再做一次减法得到任意区间和。

参数说明：addPoint的c[]参数是为了一个函数复用到两棵树上；r + 1的越界判断和上一节一样不能省；公式里的x + 1是long long，乘s1时不会溢出。对比线段树，这套写法代码量少一半，唯一的限制是只支持“区间加”这种能被差分线性表达的修改，遇到区间赋值或更复杂标记就得换线段树了。

4. 逆序对与离散化：树状数组在 OJ 里的两大高频实战

4.1 逆序对：用树状数组替代归并排序的哪一半

逆序对定义是i < j 且 a[i] > a[j]的个数。归并排序能统计，但树状数组同样能，而且代码更直接：从右往左扫原数组，对于每个位置，先查“已经扫过且值小于当前元素”的个数，再把自己的值加一。因为扫描方向是从右往左，已扫过的元素全在当前位置右边，其中值小于当前值的那些，恰好和当前元素构成逆序对。全过程只需要值域树状数组，不需要动原数组顺序。

long long ans = 0; for (int i = n - 1; i >= 0; --i) { int id = getId(a[i]); // 离散化后的下标，1-based，见 4.2 ans += query(id - 1); // 右边比 a[i] 小的数量 add(id, 1); // 当前值出现的次数 + 1 } printf("%lld\n", ans);

逻辑说明：query(id - 1)统计的是值域树状数组里小于id的已出现元素个数，也就是右边比当前值小的元素个数；add(id, 1)把这个值登记进去。这样每个i只统计一次逆序对，复杂度O(n log n)。

参数说明：这里的query和add用的还是第二章模板，但数组长度变成了离散化后的值域大小M，而不是n。答案最大是n * (n - 1) / 2，1e5 规模下接近 5e9，必须用long long累加，这是很多新手翻车的地方。

4.2 值域太大先离散化：把 1e9 压进 1..n 的写法

树状数组的下标要求是正整数且值域有限。数据范围经常是1e9，开不下，所以先排序去重，把每个原值映射成它在排序数组里的排名，排名一定在1..M内，M不超过n。这一步叫离散化，是逆序对、第 k 小等题目的前置动作：

vector<int> nums(a, a + n); // 复制原数组 sort(nums.begin(), nums.end()); nums.erase(unique(nums.begin(), nums.end()), nums.end()); // 去重后得到值域 int M = nums.size(); // 值域大小，树状数组开到 M + 1 auto getId = [&](int x) { // lower_bound 找第一个 >= x 的位置，因为 x 必然存在，返回其排名 return lower_bound(nums.begin(), nums.end(), x) - nums.begin() + 1; };

逻辑说明：unique把相邻重复元素折叠到数组前部并返回新结尾迭代器，erase之后nums里每个值唯一，按升序排列。lower_bound返回的是第一个不小于 x 的迭代器，减去起始迭代器得到 0-based 下标，加 1 转成树状数组要求的 1-based 下标。

这里有两个边界细节必须注意：unique必须配合erase一起用，漏掉erase会导致M偏大，树状数组下界多出一段空值，查出来的排名虽然没错但值域变大；lower_bound能正常工作前提是x一定在nums里，题目的查询目标都是原数组中的值，所以这个前提一定成立。离散化后的M就是树状数组的n，所有后续add和query都不能超过它。

4.3 理解 add 与 query 再往上走一步：求第 k 小

值域树状数组除了统计逆序对，还能回答“当前所有已插入元素中从小到大的第 k 个是谁”。做法是二分答案：假设答案是mid，如果query(mid) >= k，说明前mid个值里至少包含 k 个数，答案在左半边；否则答案右移。这是树状数组题里典型的二分套查询，实现如下：

int kth(int k) { int l = 1, r = M, ans = M; while (l <= r) { int mid = (l + r) >> 1; if (query(mid) >= k) { ans = mid; r = mid - 1; // 答案可能更小，继续左找 } else { l = mid + 1; // 前 mid 个数不够 k 个，右移 } } return ans; // 返回的是离散化后的值，不是原值 }

逻辑说明：query(mid)统计的是值域[1, mid]内已插入元素的个数，这个数量随mid单调不减，所以可以二分。找到的ans是离散化排名，要还原原值只需查nums[ans - 1]。

参数说明：k必须在1..当前元素总数之间，否则答案越界；这个写法单次查询O(log^2 M)，两百次以内查询完全够用。如果需要频繁查第 k 小，尤其查询次数超过 1e5，就该用第六章的倍增写法，一次降到O(log M)。这里先掌握二分版，理解“值域上做前缀和”这个模型，后面倍增只是把二分的内层循环用位运算展开了而已。

5. 树状数组避坑指南：五个提交记录里最常见的翻车现场

5.1 下标从 1 开始：从 0 开始会陷入死循环

现象：程序在add(0, x)或query(0)处卡死，或者数组越界，提交结果超时或 RE。 原因：lowbit(0) = 0，for (int i = 0; i <= n; i += 0)永远不前进，直接死循环；即使没走到 0，从 0 开始的任何更新也无法被query(pos)统计到，因为query的循环条件是i > 0。 解决：所有下标一律 1-based。如果题目输入是从 0 开始的数组，读入时直接idx = i + 1再操作。我的个人习惯是：输入循环里先pos加 1 再调用add，不在调用处临时写a[i+1]，因为后者忘记加 1 的概率极高。

5.2 lowbit 写错：错得最隐蔽的一行代码

现象：树状数组更新后，query的结果时大时小，单点更新后查询某些位置正确、某些位置不正确。 原因：最常见是把x & -x写成x & (x - 1)，后者是把最低位的 1 清零，不是取最低位的 1；还有写成x - (x & (x - 1))的，含义对但没必要绕。lowbit(6)正确是 2，写错后变 4，跳到错误的节点导致部分区间漏更新。 解决：直接背int lowbit(int x) { return x & -x; }，然后用lowbit(8) = 8、lowbit(6) = 2两个用例自测。这段代码不需要理解补码原理，但必须写对。我一般会在模板文件开头写一行注释：// x & -x，别写成 x & (x - 1)。

5.3 区间查询写成 query(r) - query(l)：多算一个元素

现象：区间[l, r]的求和结果恰好比正确答案大a[l]，或者只大一点点，很难一眼看出来。 原因：query(l)返回的是前缀[1, l]的和，而我们要减掉的应该是[1, l - 1]，多减少一个元素导致结果偏大。 解决：把区间求和封装成一个独立函数：

long long rangeSum(int l, int r) { return query(r) - query(l - 1); // 闭区间，务必减 l-1 }

然后在业务代码里只调用rangeSum，不要裸写query(r) - query(l)。封装的意义在于：错误只会在封装函数内部出现一次，修复后全项目受益；裸写在每个调用点都可能犯同样的错。

5.4 离散化去重与 lower_bound 边界：重复值被重复映射

现象：逆序对数量偏少，且数据里重复元素越多偏差越大。 原因：两个相同的值在排序后lower_bound返回同一个下标，这本身没错；但如果unique之后没有erase，M比实际值域大，后面query(M)会统计到本不存在的值；更隐蔽的是拿到 0-based 下标后忘记加 1，导致add(0, 1)，直接触发 5.1 的死循环。 解决：统一写成一步到位：

nums.erase(unique(nums.begin(), nums.end()), nums.end()); auto getId = [&](int x) { return lower_bound(nums.begin(), nums.end(), x) - nums.begin() + 1; };

重复值映射到同一个id，add(id, 1)累加的是出现次数，完全正确。注意id + 1是离散化排名，不是原数组个数，树状数组长度用M + 1，避免末尾下标越界。

5.5 int 溢出与差分越界：树状数组不只能存非负数

现象：小数据全对，大数据答案变负、输出乱码，或者n = 1e5以上的题目直接 WA。 原因：逆序对答案上限是约 5e9，int装不下；差分树状数组里add(r + 1, -v)存的是负数，用unsigned或误判“树状数组只能存正数”就会出错；r + 1当r == n时越界写坏相邻内存。 解决：所有可能累加答案和修改值的变量统一用long long；r + 1处显式判断：if (r + 1 <= n) add(r + 1, -v);。树状数组存负数没有任何问题，因为它维护的是区间和，正负皆可，但前提是别把中间结果放int里截断。我把这条记作“树状数组四件套”：下标 1-based、lowbit 背对、闭区间减一、全程 long long。

6. 一个值钱的进阶技巧：在树状数组上倍增求第 k 小

第 4.3 节的二分写法是O(log^2 M)，代码好懂，但在需要几十万次动态第 k 小查询时不够快。常见做法是把二分展开成从高到低的二进制位试跳，直接复用树状数组内部的c数组，把复杂度压到O(log M)。这段逻辑是整套树状数组里最漂亮也最值得吃透的部分。

const int LOG = 20; // 值域 1e6 内 2^20 足够，按需调大 int kth(long long k) { int idx = 0; // 当前累计的排名位置 for (int bit = LOG; bit >= 0; --bit) { int nxt = idx + (1 << bit); if (nxt <= M && c[nxt] < k) { idx = nxt; // 跳过这段，缩小答案范围 k -= c[nxt]; // 扣掉已跳过的元素个数 } } return idx + 1; // idx 是“最大且前缀和 < k”的位置 }

逻辑说明：这里直接使用树状数组的原始c数组，而不是调用query。因为c[nxt]恰好表示[nxt - lowbit(nxt) + 1, nxt]这一段的和，而二进制试跳的步长lowbit(nxt)恰好对齐这个管辖区间，所以累加c[nxt]就能得到真实的前缀和片段。整个过程每一步维护“前缀和小于 k 的最大下标”，循环结束后idx + 1就是第 k 小元素的排名。这个技巧依赖 2.1 节的存储结构理解，代码看着短，原理却比二分版深一层。

与二分法对比：二分版单次O(log^2 M)，代码直观，适合查询次数少、逻辑简单时使用；倍增版单次O(log M)，适合插入删除密集、查询次数上十万的场景。两者返回的都是离散化排名，要原值就查nums[ans - 1]。二分版是理解入口，倍增版是竞赛常客，我建议先跑通二分版再做这个优化，直接跳级容易在nxt和c[nxt]的对应关系上卡住。

最后一条个人经验：凡是树状数组题卡数据的，先检查 5.1 到 5.5 这五个点，再检查离散化后的值域M是否真的传给了树状数组的全局n——我因为这个传错，有一次全场只过了样例，排查了半小时。树状数组本身不难，难的是细节一次到位。做题时先把模板当“基础设施”沉淀下来，别每次手写，然后在该用差分的题目里不要硬上单点修改，在该离散化的题目里不要硬开大数组。希望帮到你。

本文还有配套的精品资源，点击获取