1. 題目
有一個長度為 n 的動態頻率表，位置 i 的值會被頻繁增加，系統需要查詢前綴和、區間和，並按累計權重找到第 k 個單位落在哪個位置。請實作 Fenwick Tree（Binary Indexed Tree），要求單點更新與前綴查詢為 O(log n)，並解釋它與普通前綴陣列、線段樹的取捨。
2. 約束與澄清
- 內部陣列使用 1-based 索引；公開介面可以接受 0-based 位置，但必須統一轉換一次。
- 更新可以是增量，也可以先計算差值再寫入；要明確是否允許負值。
k的排名從 1 開始，只有所有權重非負且總和至少為k時才定義按權重選擇。- 先討論單執行緒結構；並行更新需要額外鎖或分片，不能假設普通整數寫入自動形成一致快照。
3. 核心思路
樹狀陣列的第 i 項保存一個連續區間的部分和，區間長度由 lowbit(i) = i & -i 決定。前綴查詢不斷減去 lowbit，單點更新不斷加上 lowbit，因此每次只存取 O(log n) 個陣列位置。區間和用兩個前綴相減；若初始陣列已知，可以用線性傳播把每個值累加到其父索引，建樹為 O(n)。
4. 參考實作
text
class Fenwick:
init(values):
tree = [0] * (len(values) + 1)
for i from 1 to len(values):
tree[i] += values[i - 1]
parent = i + lowbit(i)
if parent < len(tree):
tree[parent] += tree[i]
add(index0, delta):
i = index0 + 1
while i < len(tree):
tree[i] += delta
i += lowbit(i)
prefixSum(index0Exclusive):
total = 0
i = index0Exclusive
while i > 0:
total += tree[i]
i -= lowbit(i)
return total
rangeSum(left0, right0Exclusive):
return prefixSum(right0Exclusive) - prefixSum(left0)按權重選擇時，從最高的二進位步長開始試探：若跳到候選索引後的累計和仍小於 k，就接受該步並減少 k；最後得到的索引加一就是第 k 個單位所在的位置。此操作依賴累計和單調，權重出現負數時不能直接使用。
5. 複雜度與取捨
Fenwick Tree 使用 O(n) 陣列，單點增量、前綴和與按權重選擇均為 O(log n)；線性建樹為 O(n)。它比線段樹更緊湊、常數更小，但只能自然表達可逆的前綴聚合，難以直接支援區間最小值、複雜區間更新或保留完整分段資訊。若所有資料唯讀，普通前綴陣列查詢是 O(1)；若需要頻繁更新，Fenwick Tree 才有價值。
6. 驗證與觀測
- 對隨機陣列比較每次
add、prefixSum與rangeSum和樸素陣列結果，覆蓋空陣列、單元素與最大索引。 - 測試全為零、權重很大、累計和恰好等於
k、k超出總和以及非法索引。 - 交叉驗證線性建樹與逐點
add建樹的內部陣列和查詢結果。 - 對按權重選擇生成非負隨機權重，逐個
k檢查返回位置的前綴和邊界；單獨拒絕負權重輸入。
7. 常見誤區
- 混用 0-based 與 1-based 索引，導致位置 0 不更新或最後一個位置越界。
- 把
i & -i當作取負號技巧，卻沒有解釋它表示最低位的二進位區塊。 - 用 Fenwick Tree 處理帶負值的按權重選擇，忽略累計和不再單調。
- 更新值直接覆蓋樹節點，而不是沿更新路徑累加 delta。
8. 面試評分點
能解釋 lowbit 與區間覆蓋
應說明每個樹節點保存哪段連續區間，以及查詢和更新為何沿 lowbit 路徑跳轉。
能寫出無邊界錯誤的實作
應統一 1-based 內部索引，處理空陣列、非法位置與右開區間，並保證更新不會存取陣列末端之外。
能推導複雜度與建樹方式
應給出查詢、更新、選擇的 O(log n) 和線性建樹的 O(n)，並比較前綴陣列與線段樹的適用邊界。
能識別按權重選擇的前提
應指出權重必須非負、累計和必須單調，並用邊界測試驗證 k 恰好命中、超界與大數情況。