企业官网建设流程全解析

最近整理数据结构笔记时，顺手把编号20260112这页留给了“树状数组”——这并不只是一个写着玩的编号，算是我给自己定的一个复习节点。树状数组（简单记作 BIT，也叫 Fenwick Tree）在算法竞赛和日常开发里的出场率都极高，核心能力概括起来很朴素：支持单点修改和前缀和查询，并且两个操作都控制在 O(logn) 的时间复杂度内。花这么大力气单独写一篇总结，是因为它的代码量虽然只有二十多行，但很多初学者卡在“为什么树状数组要长这样”而不是“模板怎么背”。这篇笔记面向的对象就是那些想真正把 BIT 吃透的人，无论你是在备考算法题，还是在准备面试手撕代码，都可以直接参考。

先说一句：我写这篇总结的原则，是每个循环、每个边界都讲清楚原因，而不是丢给你一段不知道哪里抄来的模板。理解完以后你会发现，它并不神秘，本质上就是“用二进制把数组拆成许多小块，再按块维护信息”。

1. 为什么一个数据结构值得单独总结：它解决的是一类“在线”前缀问题

在动手看代码前，先回到最原始的问题。假设你要维护一个长度为 n 的数组 a，支持两类操作：一是把某个位置 i 增加 delta，二是查询前若干个位置的总和。如果操作是一锤子买卖，那直接算前缀和数组就行，初始化 O(n)，查询 O(1)。但现实场景往往是一边修改一边查询，这就是“在线”的前缀统计问题。原始暴力和前缀和数组分别走了一个极端：原始数组做单点修改是 O(1)，但查询前缀和只能从头扫到尾，O(n)；反过来，存完整前缀和会让查询变快，但每次改一个点，后面所有前缀和都要同步更新，又退化成 O(n)。

数据量一上来，无论偏向哪一边都会很尴尬。题目甩给你十万个操作的时候，O(n) 的操作次数会立刻爆炸。树状数组最高明的地方，就是它两边只付出了 O(logn)：单点修改走一条短链，前缀查询拆成若干小块。它不存完整的原始数组，也不存所有前缀和，而是把整个序列切成一堆长度按二进制规律变化的“小计”，分散放在编号固定的数组 slot 里。

我把三种思路摆在一个表里，看得更直观一些：

这类场景在真实世界里并不少。比如直播间的在线人数：每隔几秒就有观众进场和离开，某个人进来只影响一个点数，但要随时知道某一时刻之前累计有多少人；又比如电商订单的累计金额，一张订单改了金额，后台希望立刻算出当天前几个小时的累计营收。这类需求本质都是“单点变动 + 前缀聚合”，树状数组的名字里虽然有“数组”，但在这些场景里它就是一层轻巧的多级缓存。

1.1 为什么前缀和数组做不到“轻量组合”

也许你会想，那我把数组按块分组，比如分 sqrt(n) 块，每块维护一个块内和，查询跨块的时候把完整块的和直接拿来用，这不也行吗？这确实是分块优化的思路，查询和修改能做到 O(sqrt(n))。但树状数组的拆分粒度更细，它不是固定块大小，而是按二进制的 lowbit 动态切块。这样前缀查询需要合并的块数从 sqrt(n) 级别降到了二进制位个数级别，也就是 O(logn)。真工程和竞赛里，O(sqrt(n)) 在十万级数据量下勉强能用，到了百万甚至更大，log 的优越性就非常明显。

另外，前缀和数组还有一个隐藏问题：如果维护的数据类型支持“叠加”但也支持“撤销”，那么前缀和数组可以快速反映单点修改吗？并不能，因为修改一个点要影响它后面所有前缀数组元素，这个更新是连续的一段，没法跳过。树状数组的单点更新路径则是一条条跳跃的链子，虽然也是若干个位置，但这些位置的个数约为 logn 个，远远少于一整段。

2. 从二进制角度看树状数组的骨干：lowbit 区间划分

理解了它想解决什么问题，剩下最关键的就是搞清楚“一块小计到底覆盖了哪一段”。这里必须先认识一个函数 lowbit(x)，它表示正整数 x 在二进制表示下，最低位的 1 对应的值。比如 6 的二进制是 110，最低位 1 对应的数值是 2，所以 lowbit(6) = 2。写代码时一行就能算出来：

int lowbit(int x) { return x & -x; }

为什么x & -x能求出这个值？因为在计算机的补码表示里，-x等于把 x 取反再加一。x 的最低位 1 右边全是 0，取反后这一位变成 0，右边变成 1，再加一后右边重新变回 0，只有这一个低位 1 被保留并且重新进位到原位置。所以 x 和 -x 做按位与之后，得到的结果恰好只有最低位那个 1 是 1，其他位全为 0。这个技巧非常经典，直到今天依然没有更简短的替代写法。

树状数组的维护数组我习惯叫tree，它每一个下标 i 并不直接存 a[i]，而是存储原数组中区间[i - lowbit(i) + 1, i]的和。这句话是整个 BIT 的基石：下标 i 管多长的一段，完全由 i 的二进制最低位决定。为了看得更清楚，我把长度为 16 的序列中前 8 个下标对应的覆盖区间列出来：

从这张表里能明显看到规律：下标为偶数的位置往往覆盖更长的区间，下标为奇数则基本只覆盖自己单个点，因为奇数的二进制最低位一定是 1。这里最重要的一个特性是：所有长度都是 2 的整数次幂，而且每个树状数组节点覆盖的右端点就是它自己的下标，左端点则是右端点减去 lowbit 再加一。

2.1 前缀查询为什么能拆成若干“完整块”

现在来看看查询前缀和。假设我要查询前 13 个数的和，13 的二进制是 1101。按刚才的区间划分，我可以先取 tree[13]，它覆盖 [13,13]；剩下需要前 12 个数，于是把下标变成 13 - lowbit(13) = 12，tree[12] 覆盖 [9,12]；再往前，12 - lowbit(12) = 8，tree[8] 覆盖 [1,8]。整个过程对应的下标路径是 13 → 12 → 8，一共三段，刚好把 [1,13] 完整切成 [13,13]、[9,12]、[1,8]，没有重叠也没有遗漏。

这个现象和二进制的关系非常直观：13 的二进制 1101 其实就是在告诉你，这个前缀可以拆成三个长度分别为 1、4、8 的段。把二进制表示里从低到高的每一个 1 都“抠”出来，每抠掉一个 1，就找到一段已经算好的树状数组值。因为二进制里 1 的个数最多只有 logn 个，所以前缀查询需要的段数也被限制在 logn 个，这就是复杂度 O(logn) 的来源。既然每次查询都只是把若干个现成的“小计”相加，那速度自然很快。

同理，单点修改要更新的位置也反过来：下标 i 更新后，由它组成的所有上层覆盖区间都要同步变化。从下标 i 出发不断执行i += lowbit(i)，就能找到所有“右端点不小于 i 且区间包含 i”的父级节点。比如修改位置 3，它会影响到 tree[3]、tree[4]、tree[8]、tree[16]……这些节点覆盖的区间都包含位置 3。沿着这条路径向上走，走的步数同样是 logn 级别。

lowbit 构成了整个树状数组的骨架。它为什么能同时兼顾“查询时拆块”和“更新时向上合并”，是因为任意正整数都可以唯一表示成若干个 different 的二进制位之和，这两套路径本质上是同一个二进制拆数的过程：查询时从某个下标不断减 lowbit，更新时不断加 lowbit。理解到这一层，后面写任何变种代码都不会觉得是在背模板。

3. 三种写法拆解：单点更新、前缀查询、O(n) 建树

现在可以给出最标准的一维写法。这是我在实际比赛和日常代码里反复使用的版本，没有花哨优化，胜在稳定和容易查错：

const int N = 200010; int n; long long tree[N]; void add(int idx, long long delta) { for (; idx <= n; idx += idx & -idx) { tree[idx] += delta; } } long long query(int idx) { long long res = 0; for (; idx > 0; idx -= idx & -idx) { res += tree[idx]; } return res; }

add 函数里，循环起始点是当前需要修改的位置，每走一步都用idx + (idx & -idx)跳到包含它的下一个上级节点。这样，所有覆盖了 idx 的树状数组节点都会被同步加上 delta。query 函数则是反向操作，从idx开始不断去掉最低位的 1，把这些区间小计累加起来，直到 idx 变成 0。

这里有几处新手特别容易踩的细节。第一个是数组下标必须从 1 开始，不能从 0 开始，因为lowbit(0) = 0，查询函数会在idx = 0时陷入死循环。所以不管是原始数组还是树状数组，我都统一把下标偏移成从 1 开始。第二个是 add 的循环条件必须是idx <= n，不能写成< n，否则最后一个位置对应的节点更新不到；query 的循环条件则不能写成idx >= 0，因为到了 0 以后它会死循环。第三个是 res 和 delta 的类型，我建议直接用 long long，因为前缀和很容易超出 int 能表示的范围。

3.1 初始化不是只能暴力插入，O(n) 建树也很简单

最直观的建树方式是把原始数组 a[1..n] 逐个调用 add(i, a[i])，复杂度是 O(nlogn)。虽然大多数题目 n 只有十万级，这个建树成本完全可以接受，但既然要做总结，我建议顺手掌握 O(n) 的线性建树法。原理并不复杂：每个树状数组节点 tree[i] 的组成是它覆盖的原始区间之和，而这个区间可以拆成它自己和它的直接子区间。如果我们从下标 1 到 n 扫描，把当前节点累积的值“盖上”到它的父亲节点上，那么扫描到某个节点时，它手里已经收集齐了原数组的值和所有子区间的贡献。

代码可以写成这样：

for (int i = 1; i <= n; i++) { tree[i] += a[i]; int father = i + (i & -i); if (father <= n) { tree[father] += tree[i]; } }

验证一下：比如 a = [1,2,3,4]。循环到 i=1 时，tree[1] 变成 1，father 是 2，于是 tree[2] 从 0 变成 1；循环到 i=2 时，tree[2] 先加上 a[2] 变成 3，再把 3 加到 tree[4]；循环到 i=3 时，tree[3] 变成 3，father 是 4，所以 tree[4] 再加上 3；循环到 i=4 时，tree[4] 加上 a[4] 变成 7。最后 tree[4] = 1+2+3+4，正确。整个扫描过程每个节点只处理一次，所以是严格的 O(n)。

如果你的树状数组平时从空数组开始反复 add，也可以用另一种直观写法：对每个 i，直接从i - lowbit(i) + 1扫到 i，把 a[j] 相加放进 tree[i]。这个办法理解起来最自然，可惜复杂度是 O(nlogn)，适合作为初学时的验证代码，不适合大规模初始化。

3.2 二维树状数组：把一维循环直接嵌套

二维 BIT 是高频扩展点，代码量依然不大。你需要一个二维数组 tree，然后单点修改和前缀查询都变成两重循环，内层完全照搬一维的 lowbit 逻辑：

void add2d(int x, int y, int delta) { for (int i = x; i <= n; i += i & -i) { for (int j = y; j <= m; j += j & -j) { tree2d[i][j] += delta; } } } long long query2d(int x, int y) { long long res = 0; for (int i = x; i > 0; i -= i & -i) { for (int j = y; j > 0; j -= j & -j) { res += tree2d[i][j]; } } return res; }

二维 BIT 维护的是二维前缀和。求子矩阵(x1,y1)到(x2,y2)的和时，用四个二维前缀和做容斥即可：query2d(x2,y2) - query2d(x1-1,y2) - query2d(x2,y1-1) + query2d(x1-1,y1-1)。这个结构在图像处理、数据热力图等需要频繁更新单元格并查询矩形累计量的场景里很实用。只要你理解了 lowbit 骨架，一维扩展到二维只需要加一层循环，没有新概念。

4. 从套路到题型：树状数组为什么能渗透进一大类题

树状数组能解决的不只是“单点修改 + 前缀和”这一个模板。之所以它应用范围这么广，是因为很多看起来完全不是这个模样的题，都能通过转化变成“单点更新 + 前缀统计”。掌握这些经典套路，往往比多背几十道题有用得多。

第一种套路是差分。差分的思想很简单：给原数组区间 [l, r] 整体加上 v，等价于在差分数组里d[l] += v，d[r+1] -= v。这样一来，区间加变成了两个单点修改，查询某个位置 a[x] 变成了求差分数组的前缀和。于是“区间加、单点查询”这类问题直接被 BIT 收编。甚至“区间加、区间求和”也能做，你需要同时维护两个 BIT：一个维护差分数组 d[i]，另一个维护 d[i] * (i-1)，公式推导完成后仍只有两次单点更新和两次前缀查询。差分与 BIT 的组合，本质上就是把“连续一段的变化”改写成“两个端点的变化”，非常优雅。

第二种套路是权值计分。当问题是“统计有多少个数比当前值大”时，你可以把值域作为 BIT 的下标，用 BIT 维护每个数值出现的次数。每次插入一个新的数 x 时，先查询当前已经插入的数中有多少个落在某个前缀范围内，再对 x 这个位置做 add(x, 1)。这个玩法最典型的例子是逆序对计算。把原序列按顺序扫描，每次统计“已经出现过的且数值比 x 大的数的个数”，累加的结果就是逆序对数。由于值域可能很大，通常需要先离散化一下，给每个不同的数分配一个紧凑的排名，BIT 数组的大小就不再依赖原始值域了。

// 离散化 vector<int> vals = a; sort(vals.begin(), vals.end()); vals.erase(unique(vals.begin(), vals.end()), vals.end()); long long inv = 0; for (int x : a) { int id = lower_bound(vals.begin(), vals.end(), x) - vals.begin() + 1; // 已插入的、值大于 x 的数量 inv += (long long)query(n) - query(id); add(id, 1); }

第三种套路是第 k 小/第 k 大查询。既然 BIT 是一棵按二进制分块的树，那它天然支持“在累计频率里二分”。想知道当前所有数中第 k 小的值，可以用一个类似二进制倍增的写法，从大到小枚举步长，尝试累加树状数组节点：

int maxLog = 1; while ((maxLog << 1) <= n) maxLog <<= 1; int kth(int k) { int pos = 0; for (int step = maxLog; step >= 1; step >>= 1) { int nxt = pos + step; if (nxt <= n && tree[nxt] < k) { k -= tree[nxt]; pos = nxt; } } return pos + 1; }

这段代码我是按 n 的最大二次幂来枚举 step 的。如果第 k 小的值在权值 BIT 上查询为 pos+1，那么 tree[nxt] 正好是“前 nxt 个频率的和”。整个查找过程从大到小逼近答案，复杂度 O(logn)。很多人会用线段树二分求第 k 小，但既然 BIT 天然是二进制结构，用这个写法显然更短更快。

除了这些经典套路，树状数组还可以处理动态排名、流式数据的前缀截断、滑动窗口内的频率统计等。你会发现 BIT 在这些题里很多时候不是“主角算法”，而是“基础设施”：基础数据结构负责维护信息，你负责设计信息的维护方式和查询公式。这种习惯非常重要，真正的高手眼里，树状数组就像一把多用途扳手，碰上合适的问题，直接拧上去。

5. 和线段树的边界：什么时候别留恋漂亮代码

说到树状数组，就绕不开线段树。两者都能把区间操作做到 O(logn)，于是很多人在选型时纠结。我的建议很简单：能用 BIT 绝不上线段树，但该上线段树的时候也别硬撑。为什么这么说？我拿一份亲身体会总结对比表来展示：

为什么 BIT 这么简洁？因为它的本质建立在“区间信息可以相减”的基础上，也就是前缀和可以用两个端点做差。如果问题需要的统计量支持反向运算（求和、求异或、求积等），BIT 都能轻松处理；但如果是区间最大值这种不可逆统计，BIT 就很别扭。虽然可以设计出支持前缀最大值且只增不改的变体，但任意区间查询最值时，线段树才是正解。

另一个判断标准是区间修改的复杂性。BIT 用差分可以优雅地解决区间加和单点查询，解决区间加和区间求和也需要两个 BIT 做推导；但如果要“区间赋值、区间求和”，BIT 就很难受，这时候线段树的懒标记是天生为它准备的。区间翻转、区间覆盖这类问题，线段树的优势更是无可替代。所以选型时先问两件事：第一，统计量可不可逆；第二，修改操作是不是只在端点级别。如果两个答案都是肯定，放心用 BIT。

我在实际项目里还遇到过另一种情况：题目本身可以用线段树，但线段树的常数在几十万次操作下明显偏大。同样跑一组数据，BIT 可能三秒内出结果，线段树却要接近超时。这时即便线段树能支持更多操作，我也会优先选择 BIT，除非题目必须用到区间最值或懒标记。树状数组“漂亮”的不只是代码，更是它极低的常数，这才是它长期在竞赛数据结构中不被淘汰的真正原因。

6. 我在实际使用中反复踩到的坑与避坑建议

最后写一部分自查清单，都是我真实踩过、或者帮别人调代码时反复看到的坑。每一条背后都是血的教训。

第一，循环条件“差一个等于号”。add 函数里写成idx < n看似差不多，实际上当 idx 正好等于 n 时，最后一次更新不会执行，导致最后一个位置始终缺席。正确写法是idx <= n。类似的，初始化 O(n) 建树时，判断父亲节点也要带等于号：if (father <= n)。

第二，查询函数的终止条件。query 里如果写成idx >= 0，程序会在 idx=0 时因为idx -= lowbit(0)永远得不到 0 而陷入死循环。想清楚 lowbit(0) 等于 0 这个事实，终止条件自然写idx > 0。

第三，下标从 1 开始还是从 0 开始。原始数组用 0-based 很顺手，但 BIT 的树状数组下标是从 1 开始的。转换不一致会带来一系列越界和漏算。我的习惯是读入数据后，把 a[i] 存到 index i+1 的位置，所有业务逻辑统一用 1-based。

第四，int 溢出。这个坑尤其隐蔽：单点增加虽然只是一个数，但所有包含它的节点都会同步累加，几万次累加下来，tree 里的数值很可能超过 int 范围。前缀查询的结果也一样。我从一开始就建议 BIT 的 value 类型用 long long，不要等 WA 了才回头改类型，改完整段代码的代价更高。

第五，离散化去重后的“边界”问题。做逆序对这类题目时，如果原数组有大量重复值，unique去重后你需要用 lower_bound 把同一个值映射到同一个 id。统计“严格大于当前值”和“大于等于当前值”时，查询公式略有不同，别混淆。例如统计逆序对时，通常用当前 id 之后的数量；如果有重复值，那两个相等的数不应算作逆序对，所以依赖去重后 id 的相对次序时，思路要始终保持一致。

第六，不要把区间最值硬凹进 BIT。很多题目在求区间最小值，你搜索一圈可能看到“BIT 支持前缀最值”的说法，就顺手套上去，结果查询任意区间时发现前缀最值无法做差。BIT 求任意区间最值的通用性很差，要么加辅助数组，要么直接换线段树。这个坑特别容易让新手浪费大量时间。

第七，写完模板别急着交，先对拍。我的习惯是用一个随机小数据生成器，把暴力前缀和结果和 BIT 结果逐项比较，操作几百次以后再测边界 n=1、n=2、n 很大这些情况。对拍的代码量没多少，但它能在你写错任何一个边界时立刻亮红灯，省下的调试时间是翻倍的。尤其是 kth 函数里步长的初始值，如果最高位不够大，会直接漏掉一半值域，这种错误肉眼很难发现，对拍一秒钟就能暴露。

写到这里，这页编号 20260112 的树状数组总结就算是完整闭环了。结合我自己的经验，最想传递的一条建议是：一维 BIT 的几个核心函数，add、query、O(n) 建树、kth，值得你练到能默写的程度，因为它不只是模板，更是你理解“二进制拆数 + 区间覆盖”这个思想的最小骨架。遇到新的统计题，先问自己能不能转化成前缀信息，能，就往 BIT 的方向靠；不能，再去动线段树。保持这个思维习惯，很多算法题会瞬间变得通透许多。