数据结构之树状数组

问题

给定一个序列a，需要对这个序列进行两种操作：

1. 计算序列a中任意两个位置之间所有元素的和；
2. 能够更改序列a中任意一个位置元素的值；

现存解法

方法一：暴力求和。那么操作1的时间复杂度为O(n)，操作2的时间复杂度为O(1)；

方法二：使用前缀和数组。那么操作1的时间复杂度为O(1)，操作2的时间复杂度为O(n)；

那么有没有可能存在一种算法，使得以上两种操作的时间复杂度都是O(nlogn)？

——树状数组（BIT - binary indexed tree）

结构示例

解析：

以上结构分为两个数组，原始序列a和辅助序列c；

主要理解以下3个操作及其概念：

1. lowbit计算；
2. 计算c父节点；
3. 计算c左邻节点；

TODO