树状数组
- 树状数组可以视为线段树的一个分枝 树状数组能做的题 线段树基本都能做
- 但线段树的代码量比较少 容易实现
- 思想用lowbit 动态维护某一区间的和 求lowbit： lowbit= k & (-k);
- 在维护和求值时用到了二分的思想
- 线段树的题基本可以分三种情况
1.点更新 区间查询
2.区间更新 点查询
3.区间更新 区间查询
一，点更新 区间查询（最基本的用法）
在这种用法中 c数组里存储的每个值就代表某一段区间的和 插入点时向右维护c数组里的值（因为后面的数代表的前i项和中才又可能包含此时的值）
用求和函数求得前n项和（也称前缀和）
void add(int num,int value)
{
while(num<=n)
{
c[num]+=value;
num+=num&-num;
}
}
int getsum(int num)//1~num的区间和
{
int sum=0;
while(num)
{
sum+=c[num];
num-=num&-num;
}
return sum;
}}二，区间更新 点查询
说到区间更新 就不得不先讲数组的区间更新
我们要用数组更新一个区间(l r) 可以在区间左端处+value 右端点处-value
比如说 数组c长度为5 开始全部为0
我们想让2~4区间的数值都加2 只需让c[2]+=2 c[5]-=2 那么数组就变成了 0 2 0 0 -2 0
当我们想访问某一个数的时候 求c数组的前n项和 即从这个数对应的下标开始 求和到最左端 向左求和
1的值为c[1]=0 2的值为c[2]+c[1]=2 3的值为c[3]+c[2]+c[1]=2
5的值为c[5]+c[4]+c[3]+c[2]+c[1]=0 6的值为c[6]+c[5]+c[4]+c[3]+c[2]+c[1]=0
这样我们通过求和得出一个数的复杂度为On
而且可以得到 c[i]=a[i]+a[i-1] 所以c数组也叫差分数组
树状数组和数组的更新的思想是一样的 因为树状数组求和的复杂度低 只有log(n) 所以可以视作数组的优化
同时也是向右更新 向左查询
void add(int num,int v)
{
while(num <= n)
{
c[num] += v;
num += num&(-num);
}
}
int getsum(int num)
{
int sum = 0;
while( num > 0 )
{
sum += c[num];
num -= num&(-num);
}
return sum;
}上面的这种方法是博客上比较常用的 我们的第三者方法也要用到
但是同样的 我们在更新区间的时候也可以向左更新 向右查询 只是换了种思路 不再赘述
三，区间更新 区间查询
在查询一段区间的时候 我们有
a[1]+a[2]+…+a[n]
= (c[1]) + (c[1]+c[2]) + … + (c[1]+c[2]+…+c[n])
= n*c[1] + (n-1)*c[2] +… +c[n]
= n * (c[1]+c[2]+…+c[n]) - (0*c[1]+1*c[2]+…+(n-1)*c[n])
这里面的c数组和上面提到的一样 结果中的前半部分容易得到 而为了求后面的部分 我们可以再维护一个b数组 使得b[i]=(i-1)*c[i] 每当做区间修改的时候 就同时维护在两个区间 保持复杂度不变
void update(int int *a,int x,int v)
{
while(x<=n)
{
a[x]+=v;
x += x&(-x);
}
}
int getsum(int int *a,int x)
{
int sum=0;
while(x>0)
{
sum+=a[x];
x -= (x&(-x));
}
return sum;
}
当更新(x,y)区间的时候
update( c , y+1 , -z );
update( c , x , z );
update( b , y+1, -z*(y+1) );
update( b , x , z*x );最后求区间和时
sum = getsum(c,y)*(y+1) - getsum(c,x-1)*x - getsum(b,y) + getsum(b,x-1);