树状数组
本文最后更新于398 天前,其中的信息可能已经过时,如有错误请发送邮件到1739584917@qq.com

树状数组主要是用来解决动态前缀和问题;一般来说,问题是这么问的:

给定一个数组,有m次操纵(选择数组中的一个元素并让其加v)以及q次询问(查询a[1]+a[2]+a[3]+…+a[x]的值)

如果用暴力的方法,每次操作的时间复杂的为O(1),而每次查询的时间复杂度O(n),n为数组的长度;

所以总的时间复杂度为O(qn);显然不行,所以就用到了树状数组。

树状数组大概长这样:

我们知道,前缀和数组的每一位记录的是从开始到当前位置的所有元素的和,而树状数组也是类似的,

对于上图,节点4记录的是a[1]到a[4]的和,a[3]记录的是a[3]到a[3]的和,也就是a[3];树状数组是将数组分成了若干段,每次修改只需要改覆盖到当前节点的区间,例如要修改节点6的值,我们只需要更新a[6]、a[8]、a[16];如果要查询某个位置的前缀和,例如节点11,我们只需要查询a[8]、a[10]、a[11]的值然后相加即可。

原理很简单,那现在问题来了,我们怎么知道要修改或者查询哪些区间呢?

我们是这么定义的:

对于某个位置x,那么x所覆盖的区间里元素的个数为 2k 个(k指的是x二进制末尾0的数量)

例如:x==6,6的二进制为 110 末尾0的数量k=1,所以6的区间里元素个数为:21=2个

又如:x==8,8的二进制为 1000 末尾0的数量k=3,所以8的区间里元素的个数为:23=8个

对于询问:

我们一般采用二进制拆分的方式,例如我们要询问13这个点的前缀和:

13的二进制为 1101 ,我们每次都会减去末尾1

11012 = 13

11002 = 12(1101-0001=1100)

10002 = 8(1100-0100=1000)

我们可以看到上面的图,13的前缀和等于:a[13]+a[12]+a[8],正好跟上面操作所得到的结果是一样的。

对于修改:

我们将查询时的方法倒过来,每次都在末尾1的相同位置加上1(同一二进制位)

例如,我们要修改10这个点:

10102=10

11002=12(1010+0010=1100)

100002=16(1100+0100=10000)

对于10这个点,我们只需要修改节点10、12、16;

对于加减末尾1的这个操作,我们是这么实现的:

int lowbit(int x)
{
	return x & (-x);
}
//x+=lowbit(x)
//x-=lowbit(x)

为什么要这么写呢?

在计算机里,负数一般是用补码表示的,而补码指对原码的每一位进行取反,然后加1,比如-6,6的二进制是0110,而补码是 1010(0110 取反 1001+1=1010),我们对原码和补码进行与运算(&)就会得到x的末尾1;

原码:0110

补码:1010

&:= 0010

这里解释一下,我们刚刚说了,补码是对原码的每一位进行取反,这时候跟原码正好是反过来,如果这时候进行&运算结果为0,因为它们每一位都不同;但如果取反之后加1,那么在末尾一定会进1,那么除这一位以外,所有位都都没有相同的1

那最后看一下代码:

//数组a是要维护的数组,也就是树状数组
//n是数组a的长度
int lowbit(int x)
{
	return x & (-x);
}

int query(int x)//查询操作
{
	int res = 0;
	while (x)
	{
		res += a[x];
		x -= lowbit(x);
	}
	return res;
}
void add(int x, int v)//x这个位置加上v
{
	while (x<=n)
	{
		a[x] += v;
		x += lowbit(x);
	}
}
如果觉得本文对您有所帮助,可以支持下博主,一分也是缘
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇
/* */