树状数组实现
树状数组能够完成如下操作：
给一个序列a0-an
计算前i项和
对某个值加x
时间o(logn)
注意：有人觉得前缀和就行了，但是你还要维护啊，改变某个值，一个一个改变前缀和就是o(n)了。
线段树树状数组的题就是这样，维护一个树，比较容易看出来。
线段树：
https://blog.csdn.net/hebtu666/article/details/82691008
如果使用线段树，只需要对网址中的实现稍微修改即可。以前维护最小值，现在维护和而已。
注意：要求只是求出前i项，而并未给定一个区间，那我们就能想出更快速、方便的方法。
对于任意一个节点，作为右孩子，如果求和时被用到，那它的左兄弟一定也会被用到，那我们就没必要再用右孩子，因为用他们的父就可以了。
这样一来，我们就可以把所有有孩子全部去掉
把剩下的节点编号。
如图，可以发现一些规律：1，3，5，7，9等奇数，区间长度都为1
6，10，14等长度为2
……………………
如果我们吧编号换成二进制，就能发现，二进制以1结尾的数字区间长度为1，最后有一个零的区间为2，两个零的区间为4.
我们利用二进制就能很容易地把编号和区间对应起来。
计算前i项和。
需要把当前编号i的数值加进来，把i最右边的1减掉，直到i变为0.
二进制最后一个1可以通过i&-i得到。
更新：
不断把当前位置i加x，把i的二进制最低非零位对应的幂加到i上。
下面是代码：
思想想出来挺麻烦，代码实现很简单，我都不知道要注释点啥
向发明这些东西的大佬们致敬
int bit[MAX_N+1]int n;int sum(int i){int gg=0;while(i>0){gg+=bit[i];i-=i&-i;}return gg;}void add(int i,int x){while(i<=n){bit[i]+=x;i+=i&-i;}}
我不是女神ヾ
小鱼儿
朱雀
忘是亡心i
ゞ 浴缸里的玫瑰
还没有评论，来说两句吧...