是人都能看懂的树状数组介绍(看不懂举报我)

发布于:2023-01-20 ⋅ 阅读:(13) ⋅ 点赞:(0) ⋅ 评论:(0)

树状数组是个好东东,我们一定要学会。

单点修改需O(n),树状数组只需O(log_n)

区间查询需O(n),树状数组只需O(log_n)

区间修改与查询,用它!用它!用它!!!

树状数组基本概念

树状数组的核心思想有关于二进制,不算特别难,而且代码贼短,适合作者这种小菜。

树状数组就是让需要改变的那个区间的第一个数加上改变的大小;让区间最后一个数的后一个数减去要改变的大小(类似差分)。第一个数加完后,使包含它的数也加上改变的大小;最后一个数的后一个数减完后,使包含它的数也减上改变的大小

好,讲完这么多,你们肯定不理解,接下来我来解释(说了一堆废话

树状数组单点修改

进入正题。

区间修改我们普通修改是不是需要O(n),但是我们用树状数组只需要O(log_n),是不是很优呢?

当我们修改第一个数的时候,让他增加一个数n(我们假定n为2)。但在个时候,有一些本来包含这个数的大数就不服了:“我们包含他,他咋还比我们大了呢?”,所以说这个时候,为了平复民情啊,我们还需要把包含这个数的大数也加上2,附上一张图:

看,比如说我们要更改的是3的话,那包含他的数是不是有:4,8,16。所以说我们需要让这些数也加上2

这时候就会有同学问了:“怎么找到包含他的数呢?”

诶,问得好!

我也不知道。

啊开个玩笑,我怎么可能不知道呢?

前面我们说了树状数组的核心思想就是二进制,接下来,重要的角色登场了,他就是——lowbit

lowbit

lowbit是树状数组必不可少的一部分。                                                               ————作者

来,让我们一起找规律。

4,8,16包含了3,那他们有什么规律呢?接下来请看:

3的二进制是多少?对,是11

4的二进制是多少?对,是100

8的二进制是多少?对,是1000

16的二进制是多少?对,是10000

你发现了什么规律?

对,每次二进制最低位上的1都又加上了一个1

11最低位上的1加上了一个1,进位,变成了20;然后再次进位,变成了100,是不是这样?

来,让我们再找一组数据:

9,10,12,16

9的二进制是1001

10的二进制是1010

12的二进制是1100

16的二进制是多少?对,是10000

看,是不是也是这样?

好了,我们找到规律了,【庆祝】!!!

这时候有同学就会抽击我们幼小的心灵讲这么多怎么实现呢?

说的依旧很好!!!

 我依旧不知道......

啊我依旧开个玩笑,我依旧怎么可能不知道呢?

接下来把压力给到我们的主角——lowbit【欢呼】【欢呼】

lowbit代码很短,只有一行,但他却是树状数组中最不可缺少的一份!!!

他就是专门来解决这种问题的,具体实现就是:

int lowbit(int x){
    return x & -x;
}

这么短?

是的,就是这么短。

他就是让数字语上一个这个数字的负数,最后就是将最低位的1加上1,非常难理解,大家记住就行,相信几行代码各位大佬肯定能记住,对吧?

说完了lowbit树状数组单点修改的一个大问题也解决了,让我们继续学习单点修改。

树状数组单点修改

当我们解决了如何求出包含这个数字的大数时,单点修改我们也就快学完了。

接下来我们首先让要修改的数字n增加改变的大小,再让序列中包含n的数字也加上改变的大小,也就是n+m

举个栗子:

n我们假定为9

第一次:9+m;

第二次:9+lowbit(9)=10,让10+m;

第三次:10+lowbit(10)=12,让12+m;

第四次:12+lowbit(12)=16,让16+m

第五次:16+lowbit(16)=32,我们发现32大于序列长度,说明超出我们的序列了,结束。

好,模拟完了,大家是不是觉得思路更《清晰》了呢?

也就是循环,让序列的第n项加上m,然后让n+lowbit(n),终止条件是判断n是否大于序列总长度

上代码!!!

int lowbit(int m){
	return m&(-m);
}

void add(int x,int k){
    while(x<=n){
        c[x]+=k;
        x+=lowbit(x);
    }
}

好了,树状数组单点修改就告一段落,接下来有请的是——树状数组区间查询!!!

树状数组区间查询

想要学会树状数组区间查询,首先我们要先学会树状数组单点查询。

其实吧,树状数组单点查询单点修改没有太多的不同,只不过一个是从1n(总共的数字),一个是从n(当前这个数字)到1,具体是怎么做到的,接下来就和我一起看看吧!!!

单点修改我们是让所有包含它的数字都加上要改变的大小,而单点查询就是寻找它包含的数总共的大小啦!是不是很相似呢?所以说我们直接——上代码!!!

int sum(int x){
    int ans=0;
    while(x!=0){
    	ans+=c[x];
    	x-=lowbit(x);
	}
    return ans;
}

好了,这就是今天讲的内容了,你们学废了吗?(记得交学费!!!疯狂暗示


网站公告

欢迎关注微信公众号

今日签到

点亮在社区的每一天
签到