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 的场景，所以传入非正数要提前拦截。
容易踩的坑：
-
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 <p>正确写法：</p><pre class="brush:php;toolbar:false;">void update(int i, int delta) {
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++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
for (int i = 1; i <p>这样只是把原始数组抄进 tree，但没维护 BIT 的区间管辖关系，后续 query 全错。</p><p>正确初始化只有两种等效方式：</p>
- 全部清零后，对每个位置调用
update(i, a[i])—— 简单可靠，O(n log n) - 用「前缀和差分」优化到 O(n)：先计算前缀和
prefix[i]，再令tree[i] = prefix[i] - prefix[i - lowbit(i)]；但容易写错 lowbit 边界，实战中不如第一种直观
推荐做法（清晰、不易错）：
vector<int> tree(n + 1, 0);
for (int i = 1; i <p>注意：<code>a[i]</code> 是原数组第 i 个元素（下标从 1），如果输入是 0-indexed 数组，记得加 1 偏移。</p>
<h3>区间求和 [l, r] 就是 query(r) - query(l-1)，但 l=1 时别越界</h3>
<p>BIT 天然支持前缀和，区间和靠减法得到，这点和前缀和数组一样，但要注意边界。</p>
<p>写 <code>query(r) - query(l-1)</code> 时，若 <code>l == 1</code>，则 <code>l-1 == 0</code>，而 <code>query(0)</code> 必须返回 0（否则逻辑崩）。所以要么在 query 函数开头加判断：</p>
<pre class="brush:php;toolbar:false;">int query(int i) {
if (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 是不是该用差值——这些细节在压测或大数据下才暴露。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
