樹狀數組
一種可以有效地更新、計算前綴和的資料結構 / 維基百科,自由的 encyclopedia
樹狀數組或二元索引樹(英語:Binary Indexed Tree),又以其發明者命名為芬威克樹(英語:Fenwick tree),最早由彼得·M·芬威克(Peter M. Fenwick)於1994年以《A New Data Structure for Cumulative Frequency Tables》[1]為題發表在SOFTWARE PRACTICE AND EXPERIENCE。其初衷是解決數據壓縮裡的累積頻率(Cumulative Frequency)的計算問題,現多用於高效計算數列的前綴和, 區間和。它可以以的時間得到任意前綴和,並同時支持在時間內支持動態單點值的修改。空間複雜度。