树状数组
浅谈树状数组 - 王陸 - 博客园 (cnblogs.com)
首先我们要明白树状数组是一种数据结构,利用树状数组可以以空间换取时间,这一点和之前的线段树一样,但是树状数组访问会更快,效率更高,树状数组不同于线段数的一点就是这棵树的构成。
单点修改,区间查询: 记录详情 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
区间修改,单点查询: 记录详情 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
对于树状数组这种数据结构其中有三个数组是非常重要的:
a[ ]数组——被维护的数组,就是这棵树最下面的叶子结点。
(可以不要)
c[ ]数组——或许这个才可以真正的称之为树状数组,它是用来存储部分叶子结点之和的,就像是一种工具,就是利用它来提高访问效率的。
sum[ ]数组——前i项a[ ]数组的和,a[ ]的前缀和,这个才是真正需要用来做题的,如何解题全都要围绕这这个sum[ ]数组.
C[1]=A[1];
C[2]=A[1]+A[2];
C[3]=A[3];
C[4]=A[1]+A[2]+A[3]+A[4];
C[5]=A[5];
C[6]=A[5]+A[6];
C[7]=A[7];
C[8]=A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+A[7]+A[8];
C[i]=A[i-2k+1]+A[i-2k+2]+......A[i];
k是 : 把i变成2进制数,最后面0的个数
如i=8(0001000);k=3.
树状数组支持的操作:
//例如:lowbit(8)=4; lowbit(7)=1;
int lowbit(int x)//返回的是2^k
{
return x&(-x);
}
1,单点更新
void update(int x, long long d) //将第x个数加上d
{
while (x <= n)//n为数组的边界
{
c[x] += d;
x += lowbit(x);
}
}
2,单点查询,查询第i个数的大小
用sum[i]-sum[i-1]
3,区间修改
此处c[i]为差分数组,sum[i]为第i个点的值
将区间[10,20]加上2,则c[10]+=20;c[21]-=20;
4,区间查询
long long getsum(int x) //查询sum[x]
{
long long s = 0;
while (x > 0)
{
s += c[x];
x -= lowbit(x);
}
return s;
}