【学习笔记】SE1-1A 树状数组
2021/10/1 23:14:18
本文主要是介绍【学习笔记】SE1-1A 树状数组,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
< 数据结构 > 树状数组:
概述
树状数组(Binary Indexed Tree,BIT,也称二叉索引树)是一个支持元素增加操作与计算区间和操作的较快速的数据结构。
其主要运用了lowbit的思想,构造出了如图的索引树
lowbit
在如图的树中,每一层都代表着第n个元素最低位的1的对应值,
例如6的二进制110对应的最低位的1对应值是10,即是十进制下的4,
所以
观察得
这是因为计算机中负数表示为按位取反后加1的,注:"&"表示按位与,都为1即为一。
拓展到所有正整数上,可以得到
解释
给出 A 数组, 为元素的序列
我们可以发现,如图中的树,如果他是右儿子,那么它的父亲就是,如果他是左儿子就是
先引入 C 数组,其中
可以看出,这代表的是图中一个横条(即第i个元素所在横条包括其下面)的元素和,
(1)我们要求的是区间和,所以就可以用前缀和的方法求,不难发现,节点13的前缀和(在后面用Si表示前缀和)在图上就是这样的
即为图中灰色部分的长条之和,即为
代码如下
int ask(int i) { int ans = 0; while (i > 0){ ans += Ci[i]; i -= lowbit(i); } return ans; }
当然,这是求前缀和的的代码,要求区间(l,r)的和,就用即可
(2)我们还要增加某一元素的值,因为在图中C值是相互联系的,所以我们发现,要改变某一元素的值,还要改变其祖先节点的C值
这里也以11为例,修改元素11的值,那么就得修改如图
标灰横条的值,都加上11结点的增量 ,代码如下
void add(int i,int b){ while (i <= n){ Ci[i]+=b; i += lowbit(i); } }
That's the END
这篇关于【学习笔记】SE1-1A 树状数组的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)