首页 > 其他分享 >树状数组笔记整理

树状数组笔记整理

时间:2023-01-06 21:12:03浏览次数:58  
标签:前缀 树状 int lowbit 笔记 数组 节点

树状数组用途
单点增加
求逆序对
动态维护前缀和

树状数组介绍

树状数组,顾名思义,就是树状的一维数组。

二叉树同样也可以用一维数组存储。我们以二叉树进行类比。

image

如图所示,图中节点的序号就是存在数组中的下标

记父节点序号为 \(p\),子节点序号为 \(s\)。

则有:

\(p\) \(=\) \(s\) \(/\) \(2\) (向下取整)。

左子节点 \(s_{left}\) \(=\) \(p\) \(* 2\) 。

右子节点 \(s_{right}\) \(=\) \(p\) \(*2+1\) 。

综上可知,二叉树能用一维数组存,是由于其父子节点间存在一定关系,以至于不需要用额外的变量来表示信息。

那类比到树状数组中,可以发现:

image

\(c\)数组即为树状数组。\(c_i\) 表示区间\(a\)\([i-lowbit(i),i]\) 的和。

ps:点我了解lowbit运算是什么

同样记父节点下标为 \(p\) ,子节点下标为 \(s\)。

则有:

\(p\) \(=\) \(s\) \(+\) \(lowbit(s)\)。

由这条公式亦可反推出:

\(s\) \(=\) \(p\) \(-\) \(2^i\)(\(0 \le i < p_{last}\))

这里的 \(p_{last}\) 指的是 \(p\) 二进制表示下最后一位 \(1\) 所在的位数。

例如:\(6\) 的二进制数表示为 \(110\),则它的 \(p_{last}\) 为 \(1\)。(这里的位数从右往左从\(0\)开始记)。

因为公式 \(1\) 由 \(s\) 加上自身 \(lowbit(s)\) 得到 \(p\) 其过程一定会产生进位。且 \(lowbit(s)\) 一定小于 \(lowbit(p)\) ,所以可以倒推得到子节点。

由于以上关系,树状数组不仅可以用一维数组存。而且还衍生出了一系列用途。

树状数组功能

单点增加

Q:给序列中的一个数 \(a[x]\) 加上 \(y\) 。此时如何维护树状数组?

A:将所有包含 \(a[x]\) 的节点加上 \(y\) 即可,也就是 \(c[x]\) 和它所有的祖先节点。

ps:初始化时亦可运用此操作。

点击查看代码
void add(int x,int y){
	for (; x <= N;x += x&-x)  c[x] += y;
	return ;
}

动态维护前缀和

之所以说动态维护,因为用树状数组维护前缀和只需要 \(\log N\) 的时间复杂度。更为优秀。

Q:求 \(a\) 数组 \(a_i \sim a_x\) 的和。

A:将数 \(x\) 分成若干个区间。

区间共同特点:若区间结尾为 \(R\),则区间长度就等于 \(lowbit(R)\),即 \(R\) 二进制分解下最小的整数次幂。

举例:当 \(x\) = \(7\) 时

image

如图所示。

区间划分方式与树状数组相同。前面又提到“\(c\)数组即为树状数组。\(c_i\) 表示区间\(a\)\([i-lowbit(i),i]\) 的和。”

因此只需要将这几个区间所对应的 \(c_i\) 相加。即可得到前缀和。

点击查看代码
int ask(int x){
	int ans = 0;
	for (; x ; x -= x & -x) ans += c[x];
	return ans;
}

求逆序对

桶排+树状数组:

1.桶排部分:

对于一个序列 \(a\) , 我们建立一个 \(cnt\) 数组,\(cnt[x]\) 表示 \(x\) 在序列 \(a\) 中出现过的次数。当 \(a_i=val\) 时,\(cnt[val]++\)。

2.树状数组部分:

倒序扫描序列 \(a\),对于新加入的数 \(a_i\),查询 \(cnt[1~a_i-1]\) 的前缀和,并将返回的前缀和加入答案。前缀和部分就可以用树状数组来维护。

操作简单粗暴,但相当好用。

点击查看代码
for ( int i = n; i; i --) {
	ans += ask (a[i] - 1);
	add (a[i] , 1 );
}

\(-End-\)

\(2023.1.6\)

标签:前缀,树状,int,lowbit,笔记,数组,节点
From: https://www.cnblogs.com/lzyan-blog/p/17030992.html

相关文章

  • 道长的算法笔记:状态机模型之股票系列问题
    (一)股票系列问题所谓的股票问题,是一个动态规划状态机模型的系列问题,这些题目来自于LeetCode社区,这些问题非常经典,能够帮助我们理解动态规划的本质,这些问题大多初看之......
  • seata 使用笔记
    版本如下:seata-server1.6.1spring-cloud-alibaba.version2021.0.1.0mysql-connector-java8.0.21druid-spring-boot-starter1.2.8dynamic-datasource-spring-boot......
  • [概率论与数理统计]笔记:2.3 常用的离散型分布
    2.3常用的离散型分布退化分布若随机变量\(X\)满足\[P\{X=a\}=1\]则称\(X\)服从\(a\)处的退化分布,这种情况下,随机变量退化成了一个确定的常数。两点分布定义若随机......
  • (笔记)在每个 Linux 用户SSH登录时执行自定义脚本
     有些时候,我们需要在linux用户登录时执行我们自己编写的脚本,比如登录时给个友好的交互输出提示。为了实现该目的,我们有必要去了解一下linux在用户登录时执行内部shell的......
  • 思源笔记挂件src-sy-post-publisher使用教程
    思源笔记挂件src-sy-post-publisher使用教程因为目前我只使用了博客园和语雀,所以只写了博客园和语雀的配置内容。‍博客园博客网址:https://www.cnblogs.com/......
  • OpenMVG学习笔记
    一直基于OpenMVG在做算法移植,在此梳理一下OpenMVG的主要源码,边学边补充。openMVG主要的模块有openMVG_Libraries、openMVG_Samples和software。1.openMVG:  1.1.came......
  • 数组处理
    一、PHP获取二维数组中某一列的值集合 PHP还是比较常用的,于是我研究了一下PHP二维数组。在处理php数组的时候,有一种需求特别的频繁,如下二维数组:$arr=array(......
  • 混合开发的笔记
    浅谈混合APP中H5页面的缓存处理混合app中的H5多页和单页问题......
  • LeetCode 删除数组中重复项 26 80
    26(80)给你一个升序排列的数组nums,请你原地删除重复出现的元素,使每个元素只出现一次(使得出现次数超过两次的元素只出现两次),返回删除后数组的新长度。元素的相对顺......
  • 高等代数笔记【4】向量与向量空间
    \(n\)维向量注意到,直接使用集合无法区分元素的顺序,例如\[\{a,b\}=\{b,a\}\]而且,也无法区分两个值相等但地位不同的对象\[\{a,a\}=\{a\}\]于是,我们定义有序对的概念......