树状数组可以用于快速从经常改变值得数组中求出某一部分的元素
用了几次树状数组,开始几次总也有不明白的地方,倒不是不会用,关键在于总感觉触摸不到精髓。
现在写下一些个人的小想法。
- 树状数组的核心在于标号末尾的0的个数,主要决定了控制范围,(如两个0是四个数的和,三个0是八个数的和,事实上每多出一个0的时候,控制的范围就增加了一倍,原来范围内的修改都要向计算原本和增加范围的和的数据进行更新,当然没有出现范围扩增时候也要向上更新)
- 对于一次求和操作,总是只能求出前若干项的和
- 每次有更改的时候逐级向上修改,从图中可以清楚的看出来,每当末尾多出现一个0的时候就要进行一次汇总操作
1 | void Insert(int i, int value) |
其中i += i&(-i);
,为什么要+=
后面的东西呢?前面说过除了本身,每增加一次0的时候会计算一次和(对于增加一次0其实也就是控制范围大了一倍),所以加一次自己控制的范围