可以隨時改值的前綴和。更新和區間和查詢都 O(log n),補上前綴和「不能改」的缺口。
O(1),但它是靜態的 —— 只要改一個元素,整張前綴和表就得重建 O(n)。樹狀陣列(Fenwick Tree / BIT)補上這個洞:更新某個元素和查前綴和都做到 O(log n)。它的魔法藏在一個位元技巧 i & (-i)(取出最低位的 1),決定每個節點負責哪一段區間。
前綴和 —— 查詢 O(1)、更新 O(n)(改一格要把後面整段重算)。
樹狀陣列 —— 查詢 O(log n)、更新 O(log n),兩邊平衡,適合「一邊改一邊查」。
關鍵位元技巧 i & (-i) —— 取出 i 最低位的那個 1,代表這個節點負責的區間長度。
每個 tree[i] 存一段部分和 —— 涵蓋 [i - lowbit(i) + 1, i] 這段。
query(i)(前綴和 [1..i]) —— 從 i 往下跳:i -= i & (-i),把沿路的 tree[i] 加起來。最多 log n 步。
update(i, δ)(把 arr[i] 加 δ) —— 從 i 往上爬:i += i & (-i),沿路每個 tree[i] 都加 δ。最多 log n 步。
區間和 [l..r] —— query(r) - query(l-1),跟前綴和公式一樣。
兩個方向剛好相反 —— 查詢往下扒、更新往上爬,都靠 lowbit 跳。
樹狀陣列(Fenwick) —— 短小精悍(幾行),專長是「前綴和 / 區間和 + 單點更新」,記憶體省(一個 n+1 陣列)。
線段樹(Segment Tree) —— 更通用:區間最小 / 最大 / 任何可結合運算,還能「區間更新」(懶標記)。程式較長、記憶體約 2~4n。
怎麼選 —— 只要區間和 + 單點改 → 樹狀陣列;要 min / max 或區間更新 → 線段樹。
兩個都 O(log n) —— 差在通用性 vs 簡潔。
樹狀陣列有 8 格(每格存一段部分和)。切換兩個操作:query(7) 從 7 往下跳 i -= i&-i(7 → 6 → 4)把值加起來;update(3) 從 3 往上爬 i += i&-i(3 → 4 → 8)沿路加值。紫色是當前、綠色是走過的。按「下一步」。
從樹狀陣列 update / query、區間和、動態區間和,到逆序對、二維、線段樹(和 / 最小值),以及三者怎麼選。
❌ 忘了樹狀陣列是 1-indexed —— 位元跳的技巧要從 1 開始;把 0-indexed 陣列丟進去記得 +1。
❌ update 傳「新值」而非「差值」 —— Fenwick 的 update 是「加 delta」,要設成某值得先算差 (new - old)。
❌ 拿樹狀陣列求 min / max —— 它只擅長可加減的量(和、次數)。min / max 要線段樹。
❌ 資料會變還用前綴和 —— 改一格 O(n) 重建;資料常變就用樹狀陣列 / 線段樹。
query(7) 跳過哪幾個 index?各負責哪段區間?加起來為什麼剛好是 [1..7] 的和?update(3) 會更新哪幾個 index?為什麼是這幾個?把答案打到對話裡,我幫你對。