网站建设 慕课,沈阳学校网站建设,能源科技网站建设,东莞正规网站建设树状数组能够完成如下操作#xff1a;
给一个序列a0-an
计算前i项和
对某个值加x
时间o(logn) 注意#xff1a;有人觉得前缀和就行了#xff0c;但是你还要维护啊#xff0c;改变某个值#xff0c;一个一个改变前缀和就是o(n)了。
线段树树状数组的题就是这样#x…树状数组能够完成如下操作
给一个序列a0-an
计算前i项和
对某个值加x
时间o(logn) 注意有人觉得前缀和就行了但是你还要维护啊改变某个值一个一个改变前缀和就是o(n)了。
线段树树状数组的题就是这样维护一个树比较容易看出来。 线段树
https://blog.csdn.net/hebtu666/article/details/82691008
如果使用线段树只需要对网址中的实现稍微修改即可。以前维护最小值现在维护和而已。
注意要求只是求出前i项而并未给定一个区间那我们就能想出更快速、方便的方法。
对于任意一个节点作为右孩子如果求和时被用到那它的左兄弟一定也会被用到那我们就没必要再用右孩子因为用他们的父就可以了。
这样一来我们就可以把所有有孩子全部去掉
把剩下的节点编号。 如图可以发现一些规律13579等奇数区间长度都为1
61014等长度为2
........................
如果我们吧编号换成二进制就能发现二进制以1结尾的数字区间长度为1最后有一个零的区间为2两个零的区间为4.
我们利用二进制就能很容易地把编号和区间对应起来。 计算前i项和。
需要把当前编号i的数值加进来把i最右边的1减掉直到i变为0.
二进制最后一个1可以通过i-i得到。 更新
不断把当前位置i加x把i的二进制最低非零位对应的幂加到i上。
下面是代码
思想想出来挺麻烦代码实现很简单我都不知道要注释点啥
向发明这些东西的大佬们致敬
int bit[MAX_N1]
int n;int sum(int i)
{int gg0;while(i0){ggbit[i];i-i-i;}return gg;
}void add(int i,int x)
{while(in){bit[i]x;ii-i;}
}
