设为首页 加入收藏

TOP

树状数组笔记整理(一)
2023-07-23 13:39:14 】 浏览:281
Tags:

树状数组介绍

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

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

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;
}

例题【具体应用】

主要利用树状数组可以快速求前缀和的优势,以数据范围为下标,快速统计区间内的个数(或所需要的信息),适用于数据范围适中(一般为 \(0 \le x \le 10^6\))且需要多次求前缀和的题目。

【例题1】 三元上升子序列

【题目分析】

对于一个数 \(x\) ,计算其作为 \(j\) 时,位置在它前面比它小的数 \(x_{min}\)、位置在它后面比它大的数 \(x_{max}\),运用乘法原理的知识可知,将\(x_{min} \times x_{max}\),即可得到 \(x\) 作为 \(j\) 时的方案数 ,枚举所有 \(x\) ,即可得到总方案数。

【树状数组作用】

统计 \(x_{min}\)\(x_{max}\) 时,即可将数 \(x\) 的范围作为树状数组的下标。

此时两种操作所代表的意思分别为:

\(add(x,1)\) 表示数值为 \(x\) 的数的个数 \(+1\)

\(sum(y)\) 表示在已经扫描过的区间内,数值为从 \(1 \sim y\) 的所有数的个数。

顺序扫描序列,对于数 \(x\) ,统计两个信息。

\(r_{i,0}\) 表示位置在数 \(x\) 前面,且比它小的数。

\(r_{i,1}\) 表示位置在数 \(x\) 前面,且比它大的数。

位置在数 \(x\) 后面,且比数 \(x\) 大的数就等于:

\(所有数 - 所有位置在 x 前面比 x 小的数 - r{i,1}\)

【code】

点击查看代码
#include<iostream>
#include<cstdio>
#include<cmath>
#define ll long long
using namespace std;
ll tree[100005],n,num;
ll r[40005][2],a[100005];
void add(ll x,ll y){
	for(;x<=100005;x+=(x&-x)) tree[x]+=y;
}
ll sum(ll x){
	ll ans=0;
	for(;x;x-=(x&-x)) ans+=tree[x];
	return ans;
}
int main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;i++){
		ll x;
		scanf("%lld",&x);
		a[i]=x;
		num=max(num,x);
		add(x,1);
		r[i][0]=sum(x-1);
		r[i][1]=sum(num)-sum(x);
	}
	ll ans=0;
	for(int i=1;i<=n;i++)
		ans+=r[i][0]*(sum(num)-sum(a[i])-r[i][1]);
	cout<<ans<<endl;
	return 0;
}

【summary】

此题算是初步认识了以数值范围为下标的树状数组的用法。下一大点求逆序对的思想与此相同。

【例题2】 [USACO04OPEN] MooFest G 加强版

【题目分析】

将奶牛按照音量从小到大进行排序,保证当前奶牛的音量一定最大,然后分类讨论所有比当前奶牛音量小的奶牛与当前奶牛的距离(坐标比当前奶牛大的和坐标比当前奶牛小的)。两者相加,乘上当前奶牛音量,枚举每个奶牛,即可得到答案。

【树状数组作用】

定义两个树状数组,都是以距离的范围作为下标, \(c\) 数组用于统计对应距离的个数,\(t\) 数组用于表示对应距离 \(\times\) 对应 距离个数的总数,通过二者,即可快速计算距离差。

【code】

计算过程的解释已在代码中注释出来。

点击查看代码
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define ll long long
using namespace std;
ll n,t[50005],c[50005];
struct A
首页 上一页 1 2 3 4 5 下一页 尾页 1/5/5
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇c++学习笔记——模板和IO(一) 下一篇队列——queue的用法(及洛谷B361..

最新文章

热门文章

Hot 文章

Python

C 语言

C++基础

大数据基础

linux编程基础

C/C++面试题目