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

大神的讲解