树状数组用普通数组实现，核心是lowbit(x)=x&-x，用于单点修改和区间求和，时间复杂度均为O(log n)；下标必须从1开始，lowbit(12)=4，lowbit(7)=1，不可用x%2或循环除2替代。
用普通数组就能实现树状数组（bit），关键不在“树”的形态，而在下标间的位运算关系。它不建树、不指针、不递归，只靠一个 lowbit 函数和两个循环，就把单点修改和区间求和都压到 o(log n) 时间内。
lowbit 是核心，必须写对
所有逻辑都依赖 lowbit(x) = x & -x。这个操作不是求奇偶或末位，而是提取二进制里「最低位的 1 及其后所有 0」构成的值：
-
lowbit(12)→12是1100₂，结果是100₂ = 4 -
lowbit(7)→7是111₂，结果是1₂ = 1 -
绝不能写成
x % 2或循环除 2，那会完全破坏结构 - 传入 0 会返回 0，导致死循环，务必保证下标从 1 开始，且每次调用前检查
i > 0
单点修改：向上更新所有管辖节点
修改位置 i 的值，不是只改 tree[i]，而是要同步更新所有「管着 i」的上级节点——它们的下标是 i, i + lowbit(i), i + lowbit(i) + lowbit(i + lowbit(i)), …，直到超过数组长度：
- 循环写法：
for (int j = i; j - 错误写法：
j -= lowbit(j)—— 这会让下标越来越小，直接跳出或崩溃 - 初始化不能直接赋值
tree[i] = a[i]，必须用update(i, a[i])逐个累加，否则父子关系不成立
区间求和：向下拆解前缀为若干子段和
求 [1, i] 前缀和，本质是把区间拆成至多 log n 个不重叠的管理段，每段和就存于 tree[j] 中：
- 从
j = i开始，每次加tree[j]，再令j = j - lowbit(j)，直到j == 0 - 求任意区间
[l, r]就是query(r) - query(l-1) - 注意：
query(0)必须返回 0，且循环条件是j > 0，不是j >= 1（虽等价，但更推荐前者）
实际使用时的硬性约定
- 原数组和树状数组都从下标 1 开始用，
a[0]和tree[0]不参与任何计算 - 树状数组大小至少为
n + 1（建议开N + 5防越界） - 涉及差分扩展（如区间修改+单点查询）时，仍复用同一套
lowbit和循环逻辑，只是语义变为维护差分数组 - 不要试图“看懂图再写”，先背住两个方向：改的时候
+=，查的时候-=
