-
lowbit运算：lowbit(x)=x&(-x)
//原码与补码相与，取x的二进制最右边的1和它右边的所有0,x的二进制最右边的1的位置
可以理解为能够整除x的最大2的幂次。
-
思想：区间查询->前缀和相减->树结构维护
给出一个长度为n的数组，完成以下两种操作
1.将第x个数加上k
update(x,k)
void update(int x,int k)
{
for(int i=x;i<=MAX;i+=lowbit(i))//取到MAX，c[MAX]也要更新
{
t[i]+=k;
}
}
2.输出区间[x,y]内的数之和。
getsum(y)-getsum(x-1)
int getsum(int x)
{
int sum=0;
for(int i=x;i>=1;i-=lowbit(i))//最小到t[1]
{
sum+=t[i];
}
return sum;
}
树状数组定义图
树状数组t[x]：在x号位之前lowbit(x)个整数之和
//下标必须从1开始。
-
实现：update(x,k)
将第x个数加上k
由于将第x个数加上k后，对应树状数组t[x]中能覆盖a[x]的都要加上k,所以要找最近的，又能覆盖的。
等价于：求一个尽可能小的整数a,使得lowbit(x+a)>lowbit(x)
如果lowbit(a)<lowbit(x)
lowbit(a)假设0010，lowbit(x)假设0100
lowbit(x+a)为0010<lowbit(x)，不成立。
所以lowbit(a)>=lowbit(x)
当a取lowbit(x)=0100时，lowbit(x+a)=1000>lowbit(x)
-
实现：getsum(x)
输出区间[1,x]内的数之和
sum[1,n]
=a[1]+a[2]+.....+a[n]
=a[1]+..+a[n-lowbit(n)]+a[n-lowbit(n)+1]+....+a[n]
=sum[1,n-lowbit(n)]+t[n]
