树状数组 (Fenwick Tree / BIT)

引言：“动态前缀和”问题

如果你需要计算一个不断变化的数组的前 $K$ 個元素之和（前缀和）：

• 静态前缀和数组： 查询 $O(1)$，但更新需要 $O(N)$。对于频繁变动的数据太慢。
• 线段树： 查询和更新均为 $O(\log N)$，但实现复杂且占用 $4N$ 内存。

树状数组 (Binary Indexed Tree, BIT) 是完美的平衡点。它仅需 $1N$ 内存 和约 10 行代码，就能实现 $O(\log N)$ 的查询与更新。

算法要解决什么问题？

• 输入： 一个支持“在索引 i 处增加 X”操作的数组。
• 输出： 快速计算区间 [L, R] 的元素之和。
• 承诺： 高性能、低内存占用的动态前缀和处理。

核心思想 (直觉版)

树状数组基于 二进制拆分。 每个整数都可以拆分为 2 的冪次之和（例如 $7 = 4 + 2 + 1$）。 在树状数组中，索引 i 处的节点存储了一个区间的和，而这个区间的长度由 i 的 最后一位 1 (lowbit) 决定：

• 索引 4 (二进制 100) 存储了 4 个元素的和。
• 索引 6 (二进制 110) 存储了 2 个元素的和。
• 索引 7 (二进制 111) 存储了 1 个元素的和。

要计算前 7 項的和，你只需累加 tree[7] + tree[6] + tree[4]。

算法是如何工作的？

1. Lowbit 函数： i & -i 可以提取出 i 的二进制中最低位的 1 所代表的值。
2. 更新 (Update)： 要在索引 i 增加值，你需要通过不断加上 lowbit 来向上更新受影响的父节点，直到 $N$。
3. 查询 (Query)： 要计算前 i 項之和，你需要通过不断减去 lowbit 來向下累加，直到 0。

典型业务场景

• ✅ 实时仪表盘： 随着每笔交易入库，实时更新“今日总銷售額”计数器。

• ✅ 算法竞赛： 任何涉及动态维护前缀和或求逆序对的问题。

• ✅ 信号处理： 计算实时信号的累积分布函数 (CDF)。

• ❌ 不可逆操作： 树状数组非常适合“加法”，因为你可以通过 Sum(R) - Sum(L-1) 得到区间和。但它很难处理 区间最值 (RMQ)，因为“最大值”操作不具备可逆性。对于最值问题，请使用 线段树 或 稀疏表。

性能与复杂度总结

• 查询 (求和)： $O(\log N)$。
• 更新 (点增)： $O(\log N)$。
• 空间： $O(N)$。

小结：一句话记住它

“树状数组是‘极简主义者的线段树’。它利用二进制位運算实现对数级性能，且几乎没有额外内存开销。如果你只需要区间和，选它準沒錯。”