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。
Fenwick Tree / Binary Indexed Tree (树状数组)的学习
原文：https://www.cnblogs.com/johnnyzhao/p/12452792.html