树状数组

树状数组

浅谈树状数组 - 王陸 - 博客园 (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;
}
上一篇:【数据结构】零基础树状数组笔记


下一篇:801二进制中1的个数