跳转到主内容
趣航编程网 - 趣学编程,启航技术之路!

C++实现区间求和的树状数组(BIT) _ 动态更新与单点查询逻辑【实战】

lowbit(x) 正确实现为 x & -x,用于获取二进制最低位1及其后所有0构成的值;BIT下标必须从1开始,update向上跳(i += lowbit(i)),query向下跳(i -= lowbit(i)),初始化须用update累加而非直接赋值。 BIT 的 lowbit 实现必须用位运算,别用取模 很多初学者写
lowbit(x)
时习惯写成
x % 2
或循环除 2,这完全错误——BIT 依赖的是二进制最低位的 1 及其后所有 0 构成的值,比如
lowbit(12)
(1100₂)应为 4(100₂),不是 0 或 2。 正确写法只有一种主流且安全的方式:
int lowbit(int x) { return x & -x; }
原因:负数在计算机中是补码,
-x
等价于
~x + 1
,与原数按位与后恰好保留最右一个 1。这个操作是 O(1),且对正数、负数(只要不溢出)都成立;但 BIT 通常只处理下标 ≥ 1 的场景,所以传入非正数要提前拦截。 容易踩的坑: 立即学习 “ C++免费学习笔记(深入) ”;
lowbit(0)
会返回 0,导致死循环,务必确保树状数组下标从 1 开始,更新/查询前检查
i > 0
若用
unsigned int
,
-x
会转成大整数,结果仍正确,但可读性差,建议统一用
int
别手写 while 模拟,性能差且易错 update 和 query 的方向相反,别把 += 写成 -= BIT 的核心在于:更新时向上跳(
i += lowbit(i)
),查询时向下跳(
i -= lowbit(i)
)。这是由前缀和构造方式决定的——每个节点
tree[i]
管辖
[i - lowbit(i) + 1, i]
这段区间,所以求前缀和要不断剥离右端区间,而更新则要向上传播影响。 典型错误代码片段:
void update(int i, int delta) { while (i <= n) { tree[i] += delta; i -= lowbit(i); // ❌ 错!这会让 i 越变越小,直接跳出循环甚至死循环 } }
正确写法:
void update(int i, int delta) { while (i <= n) { tree[i] += delta; i += lowbit(i); // ✅ 向上覆盖更大前缀 } } int query(int i) { int s = 0; while (i > 0) { s += tree[i]; i -= lowbit(i); // ✅ 向下收缩到更短前缀 } return s; }
注意点: query 返回的是
[1, i]
的和,不是
[i, i]
;单点值需用
query(i) - query(i-1)
update 的
delta
是变化量,不是新值;若要设为新值,得先查旧值再算差 边界条件:query 中
i > 0
是必须的,因为
tree[0]
不合法(下标从 1 起) 初始化不能直接 for 循环 assign,要用 update 累加 常见误解:以为 BIT 可以像线段树那样“建树”一次完成,于是写: C知道 CSDN推出的一款AI技术问答工具 下载
for (int i = 1; i <= n; ++i) tree[i] = a[i]; // ❌ 完全无效
这样只是把原始数组抄进 tree,但没维护 BIT 的区间管辖关系,后续 query 全错。 正确初始化只有两种等效方式: 全部清零后,对每个位置调用
update(i, a[i])
—— 简单可靠,O(n log n) 用「前缀和差分」优化到 O(n):先计算前缀和
prefix[i]
,再令
tree[i] = prefix[i] - prefix[i - lowbit(i)]
;但容易写错 lowbit 边界,实战中不如第一种直观 推荐做法(清晰、不易错):
vector tree(n + 1, 0); for (int i = 1; i <= n; ++i) { update(i, a[i]); }
注意:
a[i]
是原数组第 i 个元素(下标从 1),如果输入是 0-indexed 数组,记得加 1 偏移。 区间求和 [l, r] 就是 query(r) - query(l-1),但 l=1 时别越界 BIT 天然支持前缀和,区间和靠减法得到,这点和前缀和数组一样,但要注意边界。 写
query(r) - query(l-1)
时,若
l == 1
,则
l-1 == 0
,而
query(0)
必须返回 0(否则逻辑崩)。所以要么在 query 函数开头加判断:
int query(int i) { if (i <= 0) return 0; // ✅ 关键防护 int s = 0; while (i > 0) { s += tree[i]; i -= lowbit(i); } return s; }
要么调用时手动处理:
int range_sum(int l, int r) { return query(r) - (l > 1 ? query(l-1) : 0); }
另外注意: 所有下标操作(update/query/range_sum)必须统一用 1-indexed,混用 0-indexed 是最隐蔽的 bug 来源 如果题目要求「单点查询」某个位置的当前值,不要直接读
tree[i]
,它不是原值,而是管辖区间的增量聚合,老老实实用
query(i) - query(i-1)
BIT 不支持任意区间更新(如 [l,r] 加 delta),那是线段树或带 lazy 的 BIT 的事,普通 BIT 只保证单点改 + 区间查 真正难的不是写对四个函数,而是每次调用时都下意识检查下标是否越界、lowbit 是否触发了 0、delta 是不是该用差值——这些细节在压测或大数据下才暴露。

相关文章