对于这两个操作：
- 快速求前缀和
- 修改某一个数 若用数组来实现, 则第一步是 , 第二步是 。而前缀和数组则第一步是 , 第二步是 。
而树状数组就采用一种基于二进制, 折中的方法, 使得两个操作的复杂度都是 。
Binary Indexed Tree, also known as a Fenwick Tree, is a data structure used for efficient range queries and point updates on an array of numbers.
Each element at index i stroes the sum of the elements from the orignal array that come before or includeing i.
我们把一个数 x 在数轴上根据二进制划分为多个区间如下：
可以用该式子描述这种形式的区间：
对于1~n, 这样的区间共有 n 个, 因为区间右端点唯一确定一个区间。
接着去看不同的C区间有什么关系：
若将区间c的含义定为区间和, 那么显然从1累加到8的值就是c8的值。
若想确定第8位元素的值时, 就需要把 得到的就是 的值, 而减去的区间也很特殊, 他们都满足
是 1000(8的二进制) 减去一之后 0111 从右到左依次减去最后一位1得到的值,
如 刚开始 0111（7）, 0110（6）, 0100（4）
也就是说, 我们可以用这种方法以O(logn)的复杂度访问所有不重复的子区间。 而访问父区间也可以通过 + lowbit 操作实现, 如 0110(6) + lowbit(6) = 1000(8)。
综上所述, 可以实现以 的复杂度查询和修改前缀和数组。查询 x 时, 就从 x 开始, 依次 减去 lowbit值, 将得到的子区间累加即可。修改时, 则加上 lowbit 值, 直到越界, 并把得到的子区间都修改对应的值即可。
树状数组无法求区间最值问题, 只有满足当某一区间的值可以由减去子区间得到, 才能使用树状数组, 比如求和之类的。