想象你住在一栋 8 层的公寓里，物业人员常常要统计“前 7 层一共住了多少人”。最笨的办法是一层一层跑去数，数 7 层要跑 7 趟；如果这栋楼有 1 万层，就要跑 1 万趟——这就是普通的数组累加。聪明的物业设计了一套“楼层管家”制度：每一层安排一位管家，每位管家只负责自己名下的一小段楼层，比如 6 楼的管家负责记录 5～6 层的人数，4 楼的管家负责记录 1～4 层的人数。这样物业要查“前 7 层总人数”时，只要分别问 7 楼管家（7 层自己）、6 楼管家（5～6 层）、4 楼管家（1～4 层），三个人三次就报完数了，再也不用一层层跑！这个“分层负责、按块汇总”的智慧，就是树状数组（Binary Indexed Tree，简称 BIT）的核心思想。今天我们就用这栋“管家公寓”的故事，把 BIT 的原理、查询、更新和各种应用讲透。

岗位关联

对 AI 从业者而言，树状数组是处理“动态前缀统计”问题的利器——从推荐系统的实时 CTR 累计、排行榜动态排名，到流式文本的词频统计，它都能以 O(log n) 的优雅代价完成增量式数据聚合。

目录
  1. 可视化演示
  2. BIT基础结构
  3. lowbit运算
  4. 前缀和查询
  5. 单点更新
  6. 区间扩展
  7. 经典应用
  8. 性能对比
  9. AI 应用场景
  10. Python 演示
  11. 常见误区
  12. 面试题

可视化演示

树状数组(Binary Indexed Tree)是支持单点修改和前缀和查询的高效数据结构，通过lowbit运... 切换模式查看不同维度。

本节配有交互动效（进入视口后自动加载，约 3KB）。

树状数组结构：核心原理 动态展示关键流程与数据流动 交互控件调节参数实时渲染 f(x) = transform(x) 核心概念的可视化呈现

BIT基础结构

物业经理宣布实施“楼层管家”制度的那天，整栋楼的住户都松了一口气。规则很简单：每一层安排一位管家，第 i 层管家负责记录“某一段连续楼层”的住户变化情况。神奇的是，这段楼层范围不是随意划定的，而是由楼层编号 i 的二进制性质决定的——编号为 6 的管家负责 5～6 层，编号为 4 的管家反而负责 1～4 层。看起来毫无规律，实则暗藏玄机：每位管家负责的区间恰好是 (i - lowbit(i), i] 的闭区间。

在技术上，树状数组用一个长度为 n+1 的数组 BIT 来存放这些“管家账本”。BIT[i] 表示第 i 个位置记录的区间和，而这个区间由 i 的二进制决定。为了实现“任意前缀都能由若干互不重叠的区间拼出来”，BIT 的下标必须从 1 开始——如果从 0 开始，lowbit 链会陷入死循环，这个问题我们后面会详细解释。

这套“楼层管家”制度能成立的关键在于：任意一个前缀区间 [1, x]，都可以被拆成若干个完整的“管家责任区间”，而且这些区间互不重叠、刚好拼满。物业经理正是利用这一性质，把原本需要 O(n) 次累加的问题压缩到了 O(log n) 次问询。整栋楼的住户从此告别了“一层层数人数”的原始时代。

range(i)=[ i−lowbit(i)+1,  i ]\text{range}(i) = [\,i - \text{lowbit}(i) + 1,\; i\,]
  1. i楼层编号，同时也是管家登记表 BIT 数组的下标。
    i∈{1,2,…,n}i \in \{1, 2, \dots, n\}
  2. lowbit(i)i 的二进制最低位 1 对应的数值，可以理解为管家“分到的楼层跨度”。
    lowbit(i)=i&(−i)\text{lowbit}(i) = i \mathbin{\&} (-i)
  3. i - lowbit(i) + 1用跨度算出区间左端点，管家从这一层开始负责。
    l=i−lowbit(i)+1l = i - \text{lowbit}(i) + 1
  4. […, i]闭区间写法，表示管家负责的左边界到右边界之间所有楼层。
    [ l,  i ]=[ i−lowbit(i)+1,  i ][\,l,\; i\,] = [\,i - \text{lowbit}(i) + 1,\; i\,]

lowbit运算

物业给每位管家发了一把“责任跨度密码锁”，这把锁决定了他们管辖多少层楼。密码的规则来自楼层号的二进制写法：从左往右看，二进制最低位那个 1 所代表的数值，就是这位管家的管辖跨度。比如 6 的二进制是 110，最低位的 1 代表 2，所以 6 楼管家负责 2 层（5～6 层）；4 的二进制是 100，最低位的 1 代表 4，所以 4 楼管家负责 4 层（1～4 层）。

在 C/C++/Python 中，这个“最低位 1 的数值”可以用一个精妙的位运算公式直接算出来：x & (-x)。为什么负号有这种魔力？因为负数在计算机中用补码表示，-x 等价于对 x 逐位取反再加 1，这恰好会让“最低位的 1”在补码中保持不变，而它右边的 0 和左边的所有位都被取反。与运算后，只有最低位那个 1 被保留下来。

学会用 lowbit 这把“钥匙”之后，整个管家的责任体系就清晰了：管家 i 的管辖范围是以 lowbit(i) 为跨度的一段连续楼层。需要特别提醒的是，lowbit 的结果永远是 2 的幂次（1、2、4、8……），这也保证了区间拆分总是规整的。物业经理把这把密码锁命名为 lowbit——“最低位的比特”，从此每位管家都明确知道自己的辖区边界。

lowbit(x)=x&(−x)\text{lowbit}(x) = x \mathbin{\&} (-x)
  1. x任意正整数下标，例如 6。
    x=6=(110)2x = 6 = (110)_2
  2. -xx 的补码表示，等价于 ~x + 1。
    −6=(…1010)2  (补码)-6 = (\dots 1010)_2 \;(\text{补码})
  3. & 按位与两个二进制数逐位取交集，只有都为 1 的位结果才为 1。
    (110)2&(010)2=(010)2(110)_2 \mathbin{\&} (010)_2 = (010)_2
  4. 运算结果得到最低位 1 对应的数值。
    lowbit(6)=(010)2=2\text{lowbit}(6) = (010)_2 = 2

前缀和查询

物业经理要想知道“前 7 层一共住了多少人”，现在只需要做三件事：先问 7 楼管家要他自己那层的数字（因为 lowbit(7)=1，他只管 7 层自己）；然后往左跳到 6 楼，问 6 楼管家要 5～6 层的累计数；再往左跳到 4 楼，问 4 楼管家要 1～4 层的累计数。三个数相加，前 7 层的总人数就到手了。这个“向左逐级上报”的过程，在代码里就是不断地执行 i -= lowbit(i)，每跳一次收集一个 BIT[i]。

这个流程之所以总是能恰好拼满前缀，是因为每次减去 lowbit(i) 后，新的下标 i' 恰好是上一个管家区间的左边界再往左一位。数学上可以严格证明：对任意正整数 i，将 i、i-lowbit(i)、i-lowbit(i)-lowbit(i-lowbit(i))……这条链走到底，会得到一组互不重叠且无缝覆盖 [1, i] 的区间。而且链的长度绝不会超过 log₂(n)+1，因为每次 i 都会至少去掉二进制中的一个 1。

这一小段“问询-跳跃-累加”的循环，就是整个 BIT 数据结构的半边天。无论楼层总数 n 有多大，查询前 i 层的总人数都只需要走 log₂n 步左右。物业经理很满意：以前查一次要跑遍整栋楼，现在喝杯咖啡的功夫就出结果了。而且每次有住户搬入搬出，只需要在管家账本上轻轻改一笔，查询依然高效如初。

prefix(i)=BIT[i]+prefix(i−lowbit(i))\text{prefix}(i) = \text{BIT}[i] + \text{prefix}\big(i - \text{lowbit}(i)\big)
  1. BIT[i]当前下标 i 的管家账本，记录其责任区间的总和。
    BIT[i]=∑k=i−lowbit(i)+1iak\text{BIT}[i] = \sum_{k=i-\text{lowbit}(i)+1}^{i} a_k
  2. i - lowbit(i)向左跳一步，跳到下一个待询问的管家位置。
    i←i−lowbit(i)i \leftarrow i - \text{lowbit}(i)
  3. 递归叠加重复累加并跳跃，直到 i 变为 0。
    prefix(i)=BIT[i]+BIT[i′]+BIT[i′′]+⋯\text{prefix}(i) = \text{BIT}[i] + \text{BIT}[i'] + \text{BIT}[i''] + \cdots
  4. 终止条件i = 0 时没有管家可问，递归结束。
    prefix(0)=0\text{prefix}(0) = 0

单点更新

这天 3 楼搬来了 2 位新住户，物业经理必须保证所有相关管家的账本都是最新的。哪些管家的账本需要更新呢？凡是“责任区间覆盖 3 楼”的管家都要改。按照管家制度，3 楼自己肯定要记一笔；4 楼管家负责 1～4 层，覆盖 3 楼，要改；8 楼管家负责 1～8 层，也覆盖 3 楼，同样要改。这串需要更新的位置恰好是 3 → 4 → 8，规律就是不断执行 i += lowbit(i)——向右上方攀升，直到超过大楼总层数 n。

这个过程与前缀和查询形成了完美的对称：查询是向左下方跳（i -= lowbit(i)），更新是向右上方跳（i += lowbit(i)）。为什么会这样？因为 lowbit(i) 的意义就是“管家 i 向上级汇报的跨度”，而所有包含下标 i 的管家位置，都等于 i 加上某个不断翻倍的 lowbit 值。代码实现极短，但背后是严谨的二进制进位逻辑。

有了单点更新，树状数组就真正“活”了起来——它不再是一张静态的表格，而是一套可以随时响应变化的动态系统。对 AI 场景尤其重要的是：互联网数据是以“流”的形式不断到达的，每一次点击、每一条日志都是一个“单点增量”。BIT 能以极低代价把这种增量实时融入全局统计之中。物业经理终于可以宣布：以后搬入搬出、临时住户登记，账本永远实时准确。

update(i,δ):BIT[i]+=δ;    i+=lowbit(i)\text{update}(i, \delta): \quad \text{BIT}[i] \mathrel{+}= \delta;\;\; i \mathrel{+}= \text{lowbit}(i)
  1. BIT[i] += δ先更新当前管家的账本，加上增量 δ。
    BIT[i]←BIT[i]+δ\text{BIT}[i] \leftarrow \text{BIT}[i] + \delta
  2. i += lowbit(i)向右上方跳到管辖范围更大的下一位管家。
    i←i+lowbit(i)i \leftarrow i + \text{lowbit}(i)
  3. 循环条件只要 i 不超过 n，就继续更新。
    while i≤n\text{while } i \le n
  4. 路径长度每一步 lowbit 至少翻倍，故总步数为 O(log n)。
    步数≤log⁡2n+1\text{步数} \le \log_2 n + 1

区间扩展

管家制度运行一段时间后，物业经理收到一个新的需求：不仅要知道“前 n 层总人数”，还想知道“任意一段楼层（比如 3 到 6 层）住了多少人”。这难不倒聪明的前台：先用刚才的查询方法算出“前 6 层总人数”，再算出“前 2 层总人数”，两者相减，3～6 层的精确人数就出来了。这就像把一个长绳子的总长减去起点之前那段绳子的长度，剩下的恰好就是我们想要的中间段。

更妙的是，如果需求变成“给 3～6 层统一增加 2 人”这种区间修改，单纯一个 BIT 就不够用了，这时需要引入差分数组的思想：把“区间加 v”转化为在差分数组上的两次单点操作——在位置 l 加 v，在位置 r+1 减 v。这样原本的“区间修改”就被拆解成了两个“单点更新”，BIT 的看家本领刚好用得上。若要同时支持区间修改和区间查询，则需要用两个 BIT 配合，一个维护差分值，一个维护带权差分值。

差分数组的标记公式同样重要：

物业经理意识到，这套“加标记-减标记”的玩法就像在某些楼层贴临时通知，到期限自动失效，只要沿着走廊走一遍就能看到所有生效中的通知。BIT 正是那个让“走一遍”变成“跳着走”的高速电梯。

query(l,r)=prefix(r)−prefix(l−1)\text{query}(l, r) = \text{prefix}(r) - \text{prefix}(l - 1)
  1. prefix(r)先查询前 r 层的总人数。
    prefix(r)=∑k=1rak\text{prefix}(r) = \sum_{k=1}^{r} a_k
  2. prefix(l-1)再查询第 l 层之前的累计人数。
    prefix(l−1)=∑k=1l−1ak\text{prefix}(l-1) = \sum_{k=1}^{l-1} a_k
  3. 相减两个前缀和的差正好是 [l, r] 区间的和。
    ∑k=lrak=prefix(r)−prefix(l−1)\sum_{k=l}^{r} a_k = \text{prefix}(r) - \text{prefix}(l-1)
  4. 复杂度两次 O(log n) 查询，总代价仍是 O(log n)。
    T=O(log⁡n)T = O(\log n)
diff[l]+=v,diff[r+1]−=v\text{diff}[l] \mathrel{+}= v,\quad \text{diff}[r+1] \mathrel{-}= v
  1. diff[l] += v在区间起点打一个“加 v”的标记。
    diff[l]←diff[l]+v\text{diff}[l] \leftarrow \text{diff}[l] + v
  2. diff[r+1] -= v在区间终点后一位打一个“减 v”的标记。
    diff[r+1]←diff[r+1]−v\text{diff}[r+1] \leftarrow \text{diff}[r+1] - v
  3. 前缀和还原对 diff 做前缀和即可得到每个位置的真实增量。
    Δak=∑t=1kdiff[t]\Delta a_k = \sum_{t=1}^{k} \text{diff}[t]

经典应用

管家制度的能力边界比物业经理想象的还要宽广。第一个经典应用是逆序对计数：如果住户门牌号是按入住顺序贴的，物业想知道“有多少对住户的门牌号顺序是反的”。办法是让住户依次登记入住，第 j 位住户入住时，先查一下“目前已经入住的住户中，门牌号小于等于他的有多少位”，那么在他之前且比他大的住户数量就是 j - 已登记的小于等于他的数量，累加所有贡献就是总逆序对数。BIT 在这里充当了“实时频率统计表”。

第二个应用是动态排名：游戏排行榜中玩家的分数不断变化，BIT 可以维护“每个分数段有多少人”的频次数组，查询“当前排名第 k 的分数”时通过二分 + 前缀和快速定位。第三个应用是区间频率统计：在 NLP 的流式处理中，统计最近 N 个 token 里某个词出现了多少次，BIT 的每次单点更新与区间查询都是 O(log n)，完美匹配高吞吐场景。为了处理数值范围很大的情况，通常先对原始数据做离散化，把它们映射到 1..m 的小范围排名上。

物业经理看着这栋楼从“管人数”发展到“管门牌号顺序”、“管游戏分数”、“管词频”，感慨当初这套管家制度真是万能的积木。其实本质上，所有应用都在做同一件事：把“位置”映射到 BIT 的下标上，用前缀和回答“排名范围内有多少个已登记元素”。这正是 BIT 作为“动态前缀统计器”的灵魂。

inv=∑j=1n(j−prefix(rank[aj]))\text{inv} = \sum_{j=1}^{n} \Big( j - \text{prefix}\big(\text{rank}[a_j]\big) \Big)
  1. rank[a_j]把原数组第 j 个元素离散化后的排名，缩放到 1..m。
    rank[aj]∈[1,m]\text{rank}[a_j] \in [1, m]
  2. prefix(rank[a_j])查询已登记元素中排名不超过它的数量。
    prefix(r)=∑k=1rBIT[k]\text{prefix}(r) = \sum_{k=1}^{r} \text{BIT}[k]
  3. j - prefix(rank[a_j])在第 j 个元素之前、且比它大的元素个数。
    contribution=j−prefix(rank[aj])\text{contribution} = j - \text{prefix}(\text{rank}[a_j])
  4. 求和每个元素的贡献累加即为总逆序对数。
    inv=∑j=1ncontributionj\text{inv} = \sum_{j=1}^{n} \text{contribution}_j

性能对比

物业经理听说隔壁小区用了一套更复杂的“大堂经理”管理系统——线段树，据说功能更全面，于是特意做了一次对比调研。结论是：在“单点修改 + 前缀/区间和查询”这一类问题上，楼层管家制度（BIT）几乎全面胜出——代码短、常数小、空间省；但如果物业管理需要“某段楼层中人数最多是多少”这类区间最值查询，管家账户的“减法抵消”逻辑就失效了，必须请出线段树这个更重量级的大堂经理。

从时空复杂度看，BIT 的构建可以用原始数组直接在线性时间内完成：初始化 BIT 数组后，对每个位置 i，将 a[i] 累加到 BIT[i] 并把值传递给 i+lowbit(i)。而线段树需要 O(4n) 的空间存储树形结构。实际运行中 BIT 的循环极短、缓存友好，常数因子远小于线段树的递归开销。

物业经理最后的决策是：常规的住户统计、排行榜、词频分析全部用 BIT；只有偶尔需要“找出某段楼层最热闹的楼层”这种特殊需求时，才临时启用线段树。这个决策准则对 AI 工程师同样适用：大部分增量式聚合任务（CTR 统计、向量相似度排名、流式频率）BIT 已游刃有余，不必杀鸡用牛刀。毕竟，能用一把小钥匙打开的门，就不要扛着一根大撬棍。

TBIT=O(log⁡n),SBIT=O(n)T_{\text{BIT}} = O(\log n), \quad S_{\text{BIT}} = O(n)
  1. T_BIT = O(log n)单次单点更新或前缀查询的时间复杂度。
    每操作≤log⁡2n+1 步\text{每操作} \le \log_2 n + 1 \text{ 步}
  2. S_BIT = O(n)只需长度为 n+1 的数组存储。
    空间=n+1 个整数\text{空间} = n + 1 \text{ 个整数}
  3. 对比线段树线段树时间同为 O(log n)，空间为 O(4n)。
    Sseg=4n+O(1)S_{\text{seg}} = 4n + O(1)
  4. 决策准则只做可加减的前缀统计用 BIT，需要区间最值再升级线段树。
    需求⇒选择\text{需求} \Rightarrow \text{选择}

AI 应用场景

推荐系统实时 CTR 统计

阶段：特征工程与在线服务

解决的问题：推荐系统需要实时统计“某个商品在最近 N 次曝光中的点击率”。传统做法用滑动窗口数组，每来一条新数据都要重算窗口内和，复杂度 O(N)；当曝光量每秒上万时 CPU 很快被打满。用树状数组把每次曝光/点击作为单点增量写入 BIT，前缀和查询直接给出窗口内累计值，O(log N) 的消耗让实时 CTR 计算变得轻如鸿毛。

具体案例：某新闻 App 的信息流推荐中，每条新闻的“最近 1000 次曝光点击率”需要毫秒级刷新。工程师将曝光序列映射到 BIT 下标（循环复用），每次点击执行单点 +1，查询时用前缀和相减得到最近 1000 次中的点击数，再除以 1000 即得实时 CTR。该方案单机可支撑每秒 5 万次曝光。

流式文本词频统计

阶段：数据预处理与特征提取

解决的问题：NLP 流式管线中需要在滑动窗口内统计某个 token 的频率（如 TF-IDF 变体、共现统计）。用 Python 列表切片再 count 是 O（窗口长度），高吞吐语料下不可行。BIT 以 token 的离散化 ID 为下标维护频次，窗口滑动时旧 token 出窗口做单点 -1，新 token 进来做单点 +1，查询某 token 窗口频率只需一次前缀和。

具体案例：在实时翻译系统中，系统需要统计最近 5000 个源语言 token 中每个词的出现次数，用于动态调整领域词汇权重。接入 BIT 后，每次 token 滑入滑出仅需两次 O(log V) 操作（V 为词表大小），吞吐量从每秒 2000 词提升到 8 万词。

Python 演示

python46 行
class Bit:    def __init__(self, n):        self.n = n        self.tree = [0] * (n + 1)     def lowbit(self, x):        return x & -x     def add(self, idx, delta):        while idx <= self.n:            self.tree[idx] += delta            idx += self.lowbit(idx)     def prefix(self, idx):        res = 0        while idx > 0:            res += self.tree[idx]            idx -= self.lowbit(idx)        return res     def range_sum(self, l, r):        return self.prefix(r) - self.prefix(l - 1)  def inversion_count(nums):    sorted_vals = sorted(set(nums))    rank = {v: i + 1 for i, v in enumerate(sorted_vals)}    bit = Bit(len(nums))    inv = 0    for j, x in enumerate(nums):        r = rank[x]        inv += j - bit.prefix(r)        bit.add(r, 1)    return inv  if __name__ == "__main__":    bit = Bit(8)    data = [3, 1, 4, 1, 5, 9, 2, 6]    for i, v in enumerate(data, 1):        bit.add(i, v)    print("前5项和:", bit.prefix(5))    print("区间[2,6]和:", bit.range_sum(2, 6))    bit.add(3, 2)    print("更新后前6项和:", bit.prefix(6))    print("逆序对数:", inversion_count([5, 3, 2, 4, 1]))
目的：实现一个完整的树状数组类，演示单点更新、前缀和查询、区间求和，并用它高效计算逆序对数。
  1. tree = [0] * (n + 1)下标从 1 开始，多开一格数组存放管家账本
  2. return x & -x核心 lowbit 运算，一把钥匙算出管辖跨度
  3. idx += self.lowbit(idx)单点更新时向右上方攀升，逐级通知上级管家
  4. idx -= self.lowbit(idx)前缀查询时向左下方跳跃，逐级收集管家账本
  5. return self.prefix(r) - self.prefix(l - 1)区间和 = 两个前缀相减，抵消中间冗余
  6. inv += j - bit.prefix(r)逆序对核心公式：已扫描元素中比当前元素大的数量
  7. if __name__ == "__main__":可执行入口，直接运行即可看到全部演示输出

常见误区

误区我以为 `x & (-x)` 里的负号就是把 x 变成负数，比如 lowbit(6) = 6 & (-6)，数学上 -6 是一个负数，跟 6 按位与怎么会得到正数 2？感觉特别玄乎，背下来就算了。

正解这里的负号不是数学乘法意义上的“取负”，而是计算机的补码表示。在补码中，-x 等于 ~x + 1，这个操作会把 x 的二进制最低位 1 保留下来，同时把它左边所有位取反。于是 x & (-x) 恰好只留下最低位的那个 1。拿 6 举例：6 = (110)₂，-6 的补码是 (…1010)₂，两者相与得 (010)₂ = 2。就像管家制度里的“跨度密码锁”，不是负号有魔法，而是补码恰好放大了最低位 1 的痕迹。

为何常见：大多数人第一次接触位运算时，教材都直接丢公式不解释补码，大家就用“数学负号”的直觉去理解，自然觉得玄学。

误区数组下标不都是 0 开始吗？我把 BIT 也写成从 0 开始，结果查询时 while (i >= 0) 永远减不到负数，程序直接卡死。我觉得是循环条件写错了。

正解根本原因不是循环条件，而是 BIT 的设计前提就是“下标从 1 开始”。因为 lowbit(0) = 0，如果从 0 出发执行 i -= lowbit(i)，会永远停留在 0 上；同理 i += lowbit(i) 也会卡死。下标从 1 开始后，查询链 7 → 6 → 4 → 0 能在有限的 log n 步内自然终止。可以理解为：管家编号从 1 楼开始，没有“0 楼管家”，这样每次问询都在向真实楼层编号收敛。

为何常见：习惯了 Python/Java 的 0-based 数组，下意识照搬到 BIT 上，忽略了 lowbit(0) 这个特例。

误区BIT 能做区间和，那我把每个节点的值换成“区间最大值”，不就能用 BIT 做 RMQ 区间最值查询了吗？反正都是 O(log n)。

正解BIT 能工作的前提是“两个前缀可以相减抵消”。最大值操作不可逆——max(a) - max(b) 无法还原出中间区间的最大值，前缀抵消的策略就失效了。类比管家制度：如果你问“前 6 层谁家最热闹”和“前 2 层谁家最热闹”，这两个信息相减并不能推出“3～6 层谁最热闹”。所以区间最值需求下，BIT 只能支持“单点更新 + 整体最值”，真正做区间 RMQ 还是得上线段树。

为何常见：看到 BIT 的“区间和”很好用，就想推广到其他操作，没意识到“可减性”是 BIT 成立的基础。

误区我想给 3～6 层统一加 2 人，就直接调用 BIT 的 add 方法，把 3、4、5、6 这四层各加一遍，觉得这样就行，结果查询前缀和全乱了。

正解BIT 原生只擅长单点修改。要实现“区间修改”，正确姿势是引入差分数组 diff：在 diff[l] += v、diff[r+1] -= v 两个位置做单点更新。这样任意位置的真实变化量 = diff 的前缀和，依然可以用 BIT 高效查询。如果还要区间查询，就得用两个 BIT，一个维护差分本身，另一个维护“下标 × 差分”的加权值。只调用四次 add 虽然单点上也对，但完全失去了区间修改“一次标记、批量生效”的意义，还会让修改量大的场景退化回 O（区间长度）。

为何常见：把“区间修改”简单拆成多个“单点修改”，没有利用差分把区间操作压缩成 O(log n) 的技巧，等于重新发明了低效方案。

面试题

Q1. 在树状数组中，lowbit(6) 的值是多少？

单选题 · easy

  • A.1
  • B.2← 正确答案
  • C.4
  • D.6

答案：B。6 的二进制是 (110)₂，最低位的 1 对应数值 2，所以 lowbit(6) = 2。这就像 6 楼管家只负责 2 层楼（5～6 层）。A 是 lowbit（奇数） 的结果，C 是 lowbit(4) 或 lowbit(12) 的结果，D 是 6 本身而不是它的最低位 1。

Q2. BIT 单次前缀和查询的时间复杂度是多少？

单选题 · easy

  • A.O(1)
  • B.O(log n)← 正确答案
  • C.O(n)
  • D.O(n log n)

答案：B。前缀和查询通过 i -= lowbit(i) 跳跃，每次跳跃至少消去二进制中一个 1，而二进制中 1 的个数不超过 log₂n，所以总步数为 O(log n)。就像物业查前 7 层只问了 3 位管家，而不用一层层跑完 7 层。A 只有空间换时间的预处理才能做到，C 是朴素数组累加，D 是排序复杂度。

Q3. 实时游戏排行榜中，玩家分数从 800 涨到 900，用 BIT 维护分数频次时应该执行什么操作？

单选题 · easy

  • A.区间修改
  • B.单点更新← 正确答案
  • C.前缀查询
  • D.离散化

答案：B。分数从 800 变成 900，本质是“800 分段的频次减 1、900 分段的频次加 1”，这是两次单点更新。BIT 的看家本领就是单点更新 O(log n) 完成。A 是给一段区间统一加值，C 是查询操作，D 是预处理手段不是动作。

Q4. BIT 的下标为什么必须从 1 开始？

单选题 · mid

  • A.为了节省一个数组元素
  • B.因为 lowbit(0)=0，从 0 开始查询链会死循环← 正确答案
  • C.为了配合 C 语言的指针运算
  • D.因为 0 号管家负责的区间不存在

答案：B。如果下标从 0 开始，i -= lowbit(i) 中 lowbit(0)=0，查询会永远停在 0 无法终止；更新同理。下标从 1 开始，查询链如 7→6→4→0 能在 log n 步自然结束。A 不成立，反而多了开头的空位；C、D 不是根本原因。

Q5. 关于单点更新的向上攀升路径，下列说法正确的是？

多选题 · mid

  • A.每一步执行 i += lowbit(i)← 正确答案
  • B.路径上的 lowbit 值严格非减← 正确答案
  • C.总步数为 O(log n)← 正确答案
  • D.路径终点一定是 2 的幂次

答案：ABC。更新路径从 i 开始反复 i += lowbit(i)，每一步的 lowbit 至少翻倍（非减），步数不超过 log₂n，所以 A、B、C 都对。D 错，例如 n=7 时更新位置 3：路径 3→4→8 到 8 就停了，而 n=10 时更新 3：3→4→8→16 超过 n 终止，终点是 16 = 2⁴，看起来像 2 的幂但实际只要 i <= n 都会继续，比如 n=100 时更新 97：97→98→100→104，终点 100 不是 2 的幂，D 说法不成立。

Q6. 用 BIT 求区间 [l, r] 的元素和，正确公式是？

单选题 · mid

  • A.prefix(r) + prefix(l)
  • B.prefix(r) - prefix(l-1)← 正确答案
  • C.prefix(l) - prefix(r-1)
  • D.prefix(r) + prefix(l-1)

答案：B。区间和 = 前 r 项之和减去前 l-1 项之和，相当于把绳子总长剪掉起点前那段。A 和 D 是相加会重复计算，C 把两个端点的角色搞反了。举个具体例子：求 [3,5] 的和，就是 prefix(5) - prefix(2)，B 中 l-1 = 2 恰好对应。

Q7. 在逆序对计数的 BIT 解法中，离线离散化（rank 映射）的主要作用是什么？

单选题 · mid

  • A.把数据压缩成连续正整数，使 BIT 下标紧凑← 正确答案
  • B.对数据排序，方便后续二分查找
  • C.去重，避免重复计数
  • D.把负数变成正数

答案：A。原数组数值可能很大甚至为负（如 10⁹ 或 -5），BIT 下标必须是正整数且尽量紧凑。离散化把所有不同值映射到 1..m 的连续排名上，BIT 只需 m 个位置即可工作。B 中的排序是离散化的副产品而非目的，C 中的去重是排序时顺手做的，D 只是部分场景的附带效果。

Q8. 要实现“区间修改（一段统一加 v）+ 区间查询（求一段总和）”，BIT 的正确做法是？

单选题 · hard

  • A.朴素 BIT 直接对每个点单点更新
  • B.差分数组 + 单点更新即可
  • C.用两个 BIT，一个维护差分，一个维护加权差分← 正确答案
  • D.必须改用线段树

答案：C。仅用差分数组（方案 B）可以高效做区间修改，但查询需要再对差分数组做前缀和还原，若频繁查询复杂度会退化。正确方案是用两个 BIT：BIT1 维护差分 diff[i]，BIT2 维护 diff[i] × i，这样区间查询 = (r+1)*sum(diff, r) - sum(diff*i, r) - (l)*sum(diff, l-1) + sum(diff*i, l-1)，仍然 O(log n)。A 退化为 O(n log n)，D 没必要——双 BIT 完全够用。

Q9. 下列哪些问题适合用树状数组高效解决？

多选题 · hard

  • A.单点修改 + 区间求和← 正确答案
  • B.前缀最小值查询（值会动态更新）
  • C.动态排名：查询第 k 小的分数← 正确答案
  • D.求静态数组每个位置左边比它小的元素个数← 正确答案

答案：ACD。A 是 BIT 最经典的应用；C 用 BIT 维护频次后二分即可找到第 k 小；D 本质是逆序对变体，逐个插入并查询前缀和即可。B 错误，min 操作不可减——前缀最小的信息无法通过两个前缀相减还原出区间最小，所以 BIT 无法直接支持前缀最值查询。

Q10. 在 BIT 上用“两个前缀最大值相减”来求区间最大值，会得到什么结果？

单选题 · extreme

  • A.正确结果，因为 max 是结合律的
  • B.无意义的结果，因为 max 操作没有逆运算← 正确答案
  • C.正确结果，但时间复杂度变高
  • D.溢出错误

答案：B。区间和能被前缀差出来，是因为加法有逆运算“减法”；而最大值没有逆运算——max(a, b) - max(a) 无法还原出 b。比如前缀 [1..6] 最大值是 9，前缀 [1..2] 最大值是 3，9 - 3 = 6 并不是 [3..6] 的最大值（可能是 7）。这就像管家制度里“最热闹的楼层”无法通过两次汇报相减得出，BIT 的区间查询本质上依赖可减性，所以求区间最值需要线段树。