树状数组总结

[王皓宇 (小鸽子)]

你们大概很难想象一个20分钟能敲主席树的人不会树状数组（?

“直面恐惧，斩断循环”

好吧好吧，在写完主席树后，我开始学树状数组了

我在去年这个时候用线段树把树状数组水了（？

找了10分钟，找到了我为数不多写的树状数组

正片开始

如图是一个1-8的树状数组，看上去不是很完整

但是你会发现任何一段区间都能被图中的区间表示（无论加还是减）

我们发现他们的右端点不重复，因此直接以右端点做下标即可

我们又发现任何 [1,i] 的区间都能被若干区间相加而得，而任何 [l,r] 的区间都能被 [1,r] - [1,l-1] 得到

注意到每个区间的长度就是 low bit(r)

low bit(x) 即 x 在二进制下的最小位

如 low bit(7) = 1，low bit(6) = 2，low bit(12) = 4

所以做完了？

还真是，因为我们发现 -lowbit 就是找一在我之前未覆盖的区间， +lowbit 就是找我在树状数组上的父节点，修改就是不停 +lowbit ，查询（前缀）就是 -lowbit ，那么这时候就有人要问了

如图，蓝色代表修改的路径，红色则是查询

会不会重复计算呢？是不会的

很明显，一个变大，一个变小，最多算一次

下课