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