樹狀陣列 (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)$。

小結：一句話記住它

「樹狀陣列是『極簡主義者的線段樹』。她利用二進位位元運算實現對數級性能，且幾乎沒有額外記憶體開銷。如果你只需要區間和，選她準沒錯。」