Fenwick Tree / Binary Indexed Tree (樹狀數組)的學習

Binary Indexed Tree的作用

Binary Indexed Tree(BIT)現多用于高效計算數列的前序和，區間和。它可以在O(logn)的時間得到任意的前序和(prefix sum)。如一個array[2,5,-1,3,6]，要計算第2個元素到第4個元素的和:5+-1+3=7。

BIT通過儲存部分的sum到各個節點中，然後通過周遊，從樹的葉子到根來得到total sum。

樹狀數組如何高效進行操作：

1. update(idx, delta): 将num加到位置idx的數字上；
2. prefixSum(idx)：求從數組第一個位置到第idx (含idx) 個位置所有數字的和；
3. rangeSum(from_idx, to_idx)：直接傳回cumulativeSum[to_idx+1] - cumulativeSum[from_idx]即可。該操作為時間複雜度為O(1)。

 LeetCode：

1649. Create Sorted Array through Instructions

大神的講解