树状数组核心操作：update需从i开始向上更新（i += lowbit(i)），query需从i向下累加（i -= lowbit(i)）；必须1-indexed，数组开n+1，区间查询用query(r)-query(l-1)，单BIT不支持原生区间修改+区间查询，需双BIT配合差分实现。
BIT 的核心操作：update 和 query 怎么写才对
树状数组不是拿来“建树”的，而是靠两个底层函数维持前缀和能力：update 负责单点修改后向上更新，query（或叫 prefix_sum）负责从下往上累加前缀和。错在把 update 写成向下更新、或把 query 当成查区间直接返回 query(r) - query(l) 却忘了下标从 1 开始——这是最常导致越界或结果偏移的根源。
实操建议：
-
update的循环条件是i ，每次 <code>i += i & -i（不是减） -
query的循环条件是i > 0，每次i -= i & -i（不是加） - 数组必须开
n+1大小，索引 0 不用；所有输入坐标先+1 - 查区间
[l, r]时，用query(r+1) - query(l)（若原始数组下标从 0 开始）或query(r) - query(l-1)（若已整体偏移为 1-indexed）
为什么不能直接用 BIT 做区间更新 + 区间查询
裸 BIT 天然只支持单点修改 + 前缀查询。想实现“给 [l,r] 加 v”这种区间更新，必须套一层差分——即维护差分数组 d，然后对 d[l] += v、d[r+1] -= v 做两次 update；之后 query(i) 返回的就是原数组第 i 位的值。但这样只能查单点值，要查区间和还得再套个前缀和结构，常见做法是用两个 BIT 分别维护 d[i] 和 i*d[i]。
简单说：一个 BIT 不够用。强行只用一个去扛区间更新+区间查询，逻辑会绕晕，且容易在 r+1 越界或符号弄反时静默出错。
立即学习“C++免费学习笔记（深入）”；
C++ 实现时要注意的底层细节
BIT 对数据类型敏感，尤其涉及负数、大数累加时溢出风险高。C++ 中常见踩坑点：
- 用
int存前缀和，但多次update后总和超过INT_MAX→ 改用long long -
i & -i在i == 0时未定义，所以 BIT 下标必须从 1 开始，绝不能传入 0 给update或query - 构造函数里初始化数组要用
vector<long long>(n+1, 0)</long>，别漏掉+1或写成(n, 0) - 如果题目要求离散化（比如坐标范围达 1e9），BIT 本身不处理离散化，你得自己用
map或排序去重后映射到1..m
什么时候该换线段树而不是硬刚 BIT
BIT 快、省空间、代码短，但能力边界清晰：不支持任意区间赋值、不支持区间最值、不支持合并复杂信息（如最大子段和）。一旦需求出现以下任一情况，就该切线段树：
- 需要
set(l, r, val)这种覆盖操作 - 查询不只是和，还要
max、gcd、或带懒标记的复合信息 - 动态插入/删除元素（BIT 依赖静态长度）
- 需要可持久化（BIT 几乎无法持久化）
BIT 的优势在于“刚好够用且极快”，它的简洁性来自克制——一旦需求破界，硬塞只会让 update/query 逻辑膨胀到难以验证。
