树状数组比线段树更适合单点更新+区间求和：代码更短、常数更小、不易出错；下标必须从1开始，update和query需正确处理索引映射与前缀差分；n≥1e5时性能优势显著。
树状数组比线段树更适合单点更新+区间求和
如果只做 update(i, delta) 和 query(l, r)，树状数组（Fenwick Tree）是更优选择：代码短、常数小、不易写错。线段树在纯区间求和场景下属于“杀鸡用牛刀”，多出的区间拆分、懒标记、节点合并逻辑全是冗余开销。
常见错误是把树状数组当“黑盒”背模板，结果 update() 写成从 0 开始索引、query() 没做前缀和差分，导致结果偏移或越界。注意：树状数组下标必须从 1 开始，原始数组 a[0..n-1] 需映射到 tree[1..n]。
-
update(i, delta)中的i要 +1，循环条件是i （不是 <code>） -
query(r) - query(l-1)才是区间和，query(i)返回的是[1, i]前缀和 - 初始化时逐个调用
update(i, a[i])，别试图直接赋值tree[i] = a[i]
线段树仅在需要区间修改时才值得引入
一旦出现 range_update(l, r, delta)（比如给 [l,r] 全体加一个值），树状数组就无能为力了——它不支持 O(log n) 的区间更新。这时必须上带懒标记（lazy propagation）的线段树，但代价是代码量翻倍、调试难度陡增。
容易踩的坑集中在懒标记的下推时机：不是每次 query() 都要下推，而是进入子区间前才下推；update() 中若当前区间被完全覆盖，必须立即更新节点值并设置 lazy，不能只递归到底。
立即学习“C++免费学习笔记（深入）”；
- 节点结构至少含
sum和lazy两个字段，初始化lazy = 0 - 所有访问子节点的操作前，必须先调用
push_down()，包括update()和query()的递归分支入口 - 区间更新后，父节点的
sum必须由子节点重新计算（node.sum = left.sum + right.sum），不能靠懒标记累积
树状数组的底层位运算原理影响边界处理
树状数组依赖 i & -i 获取最低有效位（lowbit），这决定了它的树形结构。这个特性让它的内存访问极其局部，缓存友好；但也意味着你不能随意“跳过”某些索引——比如想查 [3,7]，必须算 query(7) - query(2)，而 query(2) 对应的是 [1,2]，不是 [0,2]。
实际编码中，若原始数据下标从 0 开始，最安全做法是声明 vector<int> tree(n + 1)</int>，所有操作对输入下标 +1，避免混淆。
-
lowbit(i)返回的是i的二进制最低位 1 所代表的值（如lowbit(12) == 4，因 12=1100₂） -
update()循环中，i += i & -i是向上跳父节点；query()中，i -= i & -i是向下跳子区间 - 不要尝试用
std::bitset或其他位操作替代i & -i，编译器对它的优化极好，手写反而慢
性能差异在 n > 1e5 时才真正显现
当数组长度 n 小于 1e4，树状数组和线段树的实际运行时间几乎没差别，此时选谁都行；但到了 1e5 以上，树状数组的常数优势开始放大——它只有单层循环、无递归、无额外节点分配，而线段树每层都要判断区间重叠、维护懒标记、反复调用函数。
实测（Clang++17 -O2）：n=2e5，1e5 次随机 update+query，树状数组约 42ms，线段树约 68ms。差距主要来自指针跳转和函数调用栈开销，而非算法复杂度本身（两者都是 O(log n)）。
- 若用
std::vector实现线段树，务必预留空间：tree.resize(4 * n)，否则频繁扩容拖慢速度 - 树状数组可直接用
std::vector，无需预分配技巧，tree.resize(n + 1)即可 - 竞赛中遇到多次离线查询，优先考虑树状数组 + 离线排序（如“逆序对”问题），比在线线段树快得多
树状数组的简洁性容易让人低估它的适用边界——它只解决一类问题，但这一类问题恰好覆盖了 80% 的区间求和需求；而线段树的通用性背后，是更多隐藏的实现细节和调试成本。写完 update 和 query 后，务必用小数据（如 n=5，手动演算每一步 lowbit 跳转）验证下标是否真的对齐。
