首页 > 其他分享 >线段树 & 树状数组

线段树 & 树状数组

时间:2024-10-31 16:57:38浏览次数:1  
标签:树状 int 线段 数组 区间 复杂度

线段树

常用于维护区间值

代码

和题解有很大差异,但是过了就好

void Pushup(int x) {
	s[x]=(s[x<<1]+s[x<<1|1]);
}
void Pushdown(int x,int l,int r) {
	s[x]=(s[x]+ad[x]*(r-l+1));
	if(l!=r) ad[x<<1]=(ad[x<<1]+ad[x]);
	if(l!=r) ad[x<<1|1]=(ad[x<<1|1]+ad[x]);
	ad[x]=0;
}
void Build(int x,int l,int r) {
	if(l==r) {
		s[x]=a[l];
		return;
	}
	int mid=(l+r)>>1;
	Build(x<<1,l,mid);
	Build(x<<1|1,mid+1,r);
	Pushup(x);
}
void Plus(int x,int l,int r,int k,int L,int R) {
	Pushdown(x,l,r);
	if(l>=L&&r<=R) {
		if(l!=r) ad[x<<1]=(ad[x<<1]+k);
		if(l!=r) ad[x<<1|1]=(ad[x<<1|1]+k);
		s[x]=(s[x]+(r-l+1)*k);
		return;
	}	
	int mid=(l+r)>>1;
	Pushdown(x<<1,l,mid);
	Pushdown(x<<1|1,mid+1,r);	//注意这两句
	if(L<=mid) Plus(x<<1,l,mid,k,L,R);
	if(R>mid) Plus(x<<1|1,mid+1,r,k,L,R);
	Pushup(x);
}
long long Quary(int x,int l,int r,int L,int R) {
	Pushdown(x,l,r);
	if(l>=L&&r<=R) return s[x];
	long long ans=0;
	int mid=(l+r)>>1;
	if(L<=mid) ans=(ans+Quary(x<<1,l,mid,L,R));
	if(R>mid) ans=(ans+Quary(x<<1|1,mid+1,r,L,R));
	return ans;
}

实现细节

线段树开4倍大小的原因是,一些数(如5)可能使得层数多一层

Pushup的时候俩儿子的懒标记必须传干净

Pushdown的时候注意不要让叶子节点访问子节点,不然会RE

Pushdown用法总结:

1、访问到一个节点时,啥也不干,先Pushdown消除懒标记,使得后面的分析更容易;

2、Plus函数在访问完两个儿子后,要Pushup使得x数值正确,本来两儿子Add的Pushdown可以使得懒标记消掉,但是会有儿子进不了Add,因此需要在外面Pushdown一次;

3、Pushup不会对懒标记进行操作,故Pushup前先Pushdown两个儿子保证数值正确;

代码调试

对一个区间反复加和往往能发现问题(如[1,2],[1,1],[2,2],[1,3],[2,3]……)

当然,如果能背版是最好的

区间除法

转换成减法 未解决

区间开方

link

区间gcd

区间第一个值小于k的位置

区间最大子段和

维护区间和,最大前缀和,最大后缀和,最大子段和即可

例:小白逛公园

区间限长最大子段和

区间历史版本和

题目链接

维护从开始到当前时刻的\([l,r]\)区间和的和,即求\(\displaystyle\sum_{ver=1}^mS_{ver}[l\sim r]\)

一种思路是在后一个加标记遇到前一个加标记时,下推前一个加标记统计贡献

发现这种方法意味着加标记不可合并,会退化成\(O(n^2)\)(相当于加标记只能在叶子消除)

进一步思考发现:并不是不能合并,考虑前一个标记存在时的历史和:

\(S=(s[x]+ad[x]*len_{seq})*len_{time}=s[x]*len_{time}+ad[x]*len_{time}*len_{seq}\)

这时\(ad[x]*len_{time}\)与后续时间无关(因为\(ad[x]\)被更新了),又与区间长无关,可以作为标记下传

因此另开一个标记维护即可

大数比较

对于\(10^5\)位的数的比较,可以用线段树上二分来做——在结点上挂哈希值,不同就进儿子继续比较,时间复杂度\(O(\log n)\)

例题:The Classic Problem 可持久化即可

扫描线

用于解决二维数点问题

模型:对于

线段树实现

设\(s[x]\)为\([l,r]\)的总长度,\(fac[x]\)为\([l,r]\)的实际覆盖长度,\(tag[x]\)为覆盖次数懒标记,\(tag[x]\)不为\(0\)时用\(s[x]\)更新\(fac[fa[x]]\),否则用\(fac[x]\)

实现时发现\(tag[x]\)是难以维护的,因为\(tag[x]\)为\(0\)时不意味着儿子为\(0\),而儿子的覆盖状态是离散的,无法获取

思考发现不同于正常线段树,\(tag[x]\)是不需要上传或下传的;当\(tag[x]=1\)时,\([l,r]\)每个点覆盖次数$ \ge 1\(,直接取\)s[x]\(即可,当\)tag[x]=0\(时,覆盖状态一定是若干个区间,而子树内的节点可以完全表示出这些区间,这些表示区间的节点\)tag[]$均 \(\ge 1\),说明它们的\(s[]\)在前面下放\(tag[]\)时已经统计上来,存在\(fac[x]\)中了,直接取\(fac[x]\)即可

例题

P1502 窗口的星星

直接考虑矩形的价值不可行

正难则反,考虑每个点的贡献,发现每个点对一个矩形内的点有贡献,贡献转移至矩形,扫描线

李超线段树

树状数组(BIT)

参考自bestsort的博文

定义

树状数组本质上为线段树的优化,与线段树相比,它的优点在于代码简洁,时间效率高(线段树固定是\(O(logn)\),而树状数组最坏为\(O(logn)\)),但是遇到一些非常规操作,树状数组就没有那么灵活

以下是各路收集的优质理解:

线段树的变形

在用线段树求前缀和时,发现访问的节点均为左节点,大量节点弃置不用,造成时间和空间的浪费

如图,灰色节点永远用不上

于是对线段树进行改进,丢掉无用点,发现剩下的节点刚好就能放进原数组里,于是原数组就被改造为树状数组

基于二进制的高效访问

空间已经优化完了,但如果还是像线段树一样从根向下一层一层跑,那就优化了个寂寞

于是有人发现了树状数组的访问规律

lowbit(x):取出x二进制位中最低位的1(注意取出的是1<<(i-1)不是位数i)

发现在查询时,只要不断丢掉最低位的1,就可以访问到全部前i个元素

而在单点修改时也类似,只要不断加上最低位的1,就可以完成管辖元素i的所有节点的更新

下图更清晰

另一种理解:区间求和

观察树状数组,发现对于节点i,其实管辖的是右端点为i,长度为lowbit(i)的区间,通过i-=lowbit(i),可以快速跳往前一个区间,达到不重不漏地访问前i个元素,易知跳转操作次数由i的二进制表示中的1的个数决定,这就是树状数组的时间复杂度最坏为\(O(logn)\)的原因

这种理解在分析二维树状数组中会很方便

单点修改,区间查询

如上文

这里求lowbit(x)用了一种基于机器编码的方法,具体证明见bestsort原文

int n,c[MAXN];	//长度为n的树状数组
int lb(int x) {return x&-x;}
void Add(int x,int k) {
	for(int i=x;i<=n;i+=lb(x))
		c[i]+=k;
}
int Quary(int x) {
	int ans=0;
	for(int i=x;i;i-=lb(x))
		ans+=c[i];
	return ans;
}

Add(x,k);	//给元素x加上k
Quary(y)-Quary(x-1);	//[x,y]求和

区间修改,单点查询

考虑利用差分数组,这样前i个数的和就是元素i,而区改也能快速实现

//前面一样
Add(x,k); Add(y+1,-k);	//[x,y]加k
Quary(x);	//求元素x

区间修改,区间查询

考虑区改单查的变形

前x个元素的和为(d[]为差分数组)

\[\sum^x_{i=1}a[i]=\sum^x_{i=1}\sum^i_{j=1}d[j]=\sum^x_{i=1}(x-i+1)*d[i] \]

\[=(x+1)*\sum^x_{i=1}d[i]-\sum^x_{i=1}i*d[i] \]

记录两个数组 \(d[i]\) 和 \(s[i]=i*d[i]\) 即可

int n,d[MAXN],s[MAXN];
int lb(int x) {return x&-x;}
void Add(int x,int k) {
	for(int i=x;i<=n;i+=lb(x))
		d[i]+=k,s[i]+=k*x;
}
int Quary(int x) {
	int sumd=0,sums=0;
	for(int i=x;i;i-=lb(x))
		sumd+=d[i],sums+=s[i];
	return (x+1)*sumd-sums;
}

Add(x,k); Add(y+1,-k);	//[x,y]加k
Quary(y)-Quary(x-1);	//[x,y]求和

树状数组二分

和线段树一样,树状数组也可以二分

上面提到的一种定义\(c[i]\)的方法:右端点为i,长度为lowbit(i)的区间

由于lowbit(i)为\(2^k\),考虑类似倍增的思路

令\(pos=0\),\(s=0\),不断尝试对\(pos\)加上\(2^{20},2^{19},...,2^0\),此时,\(s\)的增量为\(c[pos+2^k]\)(因为最低位是刚加上去的\(k\)),如果\(s+c[pos+2^k]<=goal\),则加上这一位

二维树状数组

类比一维树状数组,c[x]表示右端点为x,长度为lowbit(x)的区间,则c[x][y]表示右下角坐标为(x,y),长lowbit(x),宽lowbit(y)的矩阵,类推转移即可

(懒得写了,现场推吧)

模型:求区间元素种类数

[P1972] HH的项链

树状数组可以快速地统计前缀和,但是遇到相同元素就会重复统计种类

由于在[l,r]中,第i种颜色只能在最后一个该颜色删除后才会消失,所以只需维护每种颜色最后出现的位置即可

01树状数组存储,st数组记录每种元素最后出现位置,若有相同元素进入,则删掉该位的1(没有贡献),更新st[]

权值线段树 & 权值树状数组

在统计个数问题上(三维偏序)有优势

求区间第k小值

权值线段树+二分即可,时间复杂度为\(O(nlogn)\)

这是主席树的底层原理之一

动态开点线段树

细节

一般开到 \(n*50\) 就差不多了

注意与动态开点线段树有关的题目,自己分析复杂度正确时TLE,有可能是炸数组了(普通线段树是RE)

线段树合并

对于一棵树,如果每个点只有\(O(1)\)的信息,要求快速求出一系列点(链或子树)的信息,可以对每个点开一棵线段树,用线段树合并维护

思路:类似于主席树,可以想到链上的该问题主席树可以维护,而到了树上,就考虑线段树合并

有两种写法,时间复杂度都是\(O(nlogn)\)

写法1:一次性

对于树\(v\to\)树$ u\(的合并,每次直接把\)v\(的结点作为\)u\(的儿子,递归处理,这样会导致\)u\(进行下一次合并时\)v\(的结构会被破坏,因此必须在\)DFS$合并后立刻访问

空间复杂度大概为\(O(n*20)\)

细节

线段树合并时,如果这么写:

	int mid=(l+r)>>1;
	if(!lc[now]&&lc[pre]) lc[now]=lc[pre];
	if(lc[now]&&lc[pre]) Merge(lc[now],lc[pre],l,mid);
	if(!rc[now]&&rc[pre]) rc[now]=rc[pre];
	if(rc[now]&&rc[pre]) Merge(rc[now],rc[pre],mid+1,r)

那么在进入第一个if后,lc[now]获得值,进入第二个if,导致出错,因此要用else分隔

写法2:可持久化

先和写法1一致,到并下一棵树时,如果有点值变化的点是\(v\)的结点,新建一个属于\(x\)的结点,把\(v\)的结点的性质拷贝过去另外做

空间复杂度大概为\(O(n*60)\)

复杂度分析

待办

应用

P4556 [Vani有约会]雨天的尾巴 /【模板】线段树合并

#3628. 「2021 集训队互测」树上的孤独

补充

对于支持线段树合并的题,都支持树链剖分(因为链和子树都在\(DFS\)序上连续),大概做法为剖询问变成\(O(logn)\)个,在\(DFS\)序数组上差分,然后扫描线/主席树

前者时间较优,后者空间较优

主席树

主席树即为可持久化线段树,思路就是对每一个历史版本都开一棵线段树,但是这样时间复杂度会很高。

由前面线段树合并可知,当点数较少时,用动态开点线段树比较优,则对于版本\(i-1\)到\(i\)的变化,如果单点变化,会有大量的节点状态不变,因此这两棵树可以共用这些节点的值,而变化的单点动态开点即可

求区间第k小值

沿用之前历史版本的思路,对每一个\([1,i]\)求一棵权值线段树,求答案时把第\(r\)棵和第\(l-1\)棵一起放进去跑线段树二分即可

可持久化数组

实际上为主席树的弱化版:对于单点修改的数组建立主席树,实际上就是只有叶子挂东西的线段树

细节

可持久化trie中叶子节点的更新是s[x]=s[pre]+1,不是s[x]++——这样写会丢失前面相同的值

P3293 [SCOI2016]美味

思考发现没有数据结构可以同时高效维护异或和加,考虑分位

我们从高位到低位考虑:要想取最大值,就要使高位尽量为\(1\),问题转化为能否存在\([l,r]\)中的数\(a_k\),使得当前第\(i\)位有\(bit_i(b)\oplus bit_i(a_k+x)=1\),假设\(bit_i(b)=0\),不难发现这样的\(a_k+x\)应在\([...\ \textcolor{red}{1}\ 00000...]\thicksim[...\ \textcolor{red}{1}\ 11111...]\)之间(\(\textcolor{red}{1}\)为第\(i\)位),找到这两个边界,记作\(l',r'\),即为查询\([l,r]\)中有没有\([l'-x,r'-x]\)中的数,对\(a[]\)建立权值主席树即可维护

时间复杂度\(O(n\log^2n)\),注意位运算玄学优先级

树套树

树套树实际上是一种思想——线段树的结点并不只能挂值,可以挂线段(李超树),线段树,平衡树,堆等等

一个经典问题就是二维线段树——对行开一个线段树,结点上挂统计处理\([l,r]\)这几行的信息的树

有时候第二维不一定是\(y\)坐标,也可以是时间维度,权值等

由于线段树只有\(O(\log n)\)层,在结点上开维护该区间的点的平衡树,空间复杂度为\(O(n\log n)\)(?)(动态开点线段树为\(O(n\log ^2n)\))

基于满二叉树的数据结构

zkw线段树

非递归版线段树,具有优秀的常数

考虑将一棵线段树底层结点补成\(2^k\)个,此时,底层结点,父亲,两个儿子的下标都可以快速获取

所以这棵线段树可以从下往上跑(普通线段树都是从上往下)

区间修改

由于从下往上跑,区间标记不好下传,考虑标记永久化

在往上跑时,如果自己的兄弟也在区间内,给兄弟也打上标记

区间查询

由于标记永久化,所有的询问都得跑到根,以获取全部标记(类似李超树)

猫树

满二叉树维护无修改区间查询,预处理复杂度\(O(n\log n)\),单次询问复杂度\(O(1)\)

先补全数组至\(2^k\),树分为\(O(\log n)\)层,每层的结点\(i\)记录\([i,mid]\)或\([mid+1,r]\)的区间值(取决于在\(mid\)的左边还是右边)

询问时跳到\(l,r\)被\(mid\)分隔的那一层,查询这两个点的值\([l,mid],[mid+1,r]\)即可,而层数是可以快速获取的—— \(dep[LCA(l,r)]=Log_2[pos[l]]-Log_2[pos[l]\ xor\ pos[r]]\)

猫树和zkw线段树底层思想差不多,都是基于快速访问下标来优化时间,但猫树和普通线段树结构又有区别——猫树空间是\(O(n\log n)\)的,因为每一层每个位置都要维护值,而线段树空间是\(O(n)\)的

标签:树状,int,线段,数组,区间,复杂度
From: https://www.cnblogs.com/zhone-lb/p/18518343

相关文章

  • DAY48|| 300.最长递增子序列 | 674. 最长连续递增序列 | 718. 最长重复子数组
     300.最长递增子序列300.最长递增子序列-力扣(LeetCode)给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。 示例......
  • 总结 JavaScript 中8种数组常用的操作 API,array.push,pop,shift,unshift,slice,splice
    前言JavaScript中数组是一个重要的数据结构,它相比于字符串有更多的方法,在一些算法题中我们经常需要将字符串转化为数组,使用数组里面的API进行操作。本篇文章总结了JavaScript中有许多数组常用的操作API,以下是一些常见的操作及其示例:1.push():在数组末尾添加一个或多个元素,并......
  • leetcode560 和为k的子数组
    leetcode560和为k的子数组packagejava2024_10.day30;importjava.util.HashMap;publicclassleetcode560{/*思路:前缀和+哈希表a[j]-a[i]=k即a[i]=a[j]-k遍历到下标j的时候,先判a[j]==k,相等就ans++,然后查哈希表中a[j]-k的数的个数,然后把a[j]放入哈希......
  • 字符串数组转换为整数数组
    在C#中,可以使用Array.ConvertAll方法来将字符串数组转换为整数数组。classProgram{staticvoidMain(string[]args){//案例1://使用Array.ConvertAll方法将字符串数组转换为整数数组//情况1:当确定每个数值......
  • (C语言)数组
    目录一维数组1>.  定义2>. 数组的下标3>. 数组的初始化4>. 计算数组的大小    1)strlen    2)sizeof二维数组1>. 定义2>. 初始化    1)只有一个{}    2)多个{}变长数组数组定义:为了存放多个相同类型的元素,创建了数组;......
  • 计蒜客:公告板(线段树)
     难点在于要把模型抽象出来。第一眼看到题面,想到的是以公告板的高度作为线段树的区间,但看到h<=10^9以后,感觉又开不了这么大的数组。但实际上,最多只有n块公告,所以最极端的情况下不过只有n行,所以区间的真正大小是[1,min(n,h)]。解决了区间的问题,再来考虑每个节点要维护的信息。......
  • 记录串口电脑往下发,没有写进数组的问题
    1voidHAL_UART_RxCpltCallback(UART_HandleTypeDef*huart)2{3/*Preventunusedargument(s)compilationwarning*/4UNUSED(huart);5if(RxCnt>=10)6{8RxCnt=0;10//将数组指向的地方的前sizeof内存用0X00替换,将数组初始化......
  • 未排序数组的树层去重
    491.递增子序列reference/*未排序+树层去重之前在进行树层去重时,我们都是先对元素排序,这样如果树层中的元素重复,它们的位置一定是相邻的,因此我们可以通过!st[i-1]来判断树层元素是否重复但现在我们不能对元素进行排序,该如何去重呢?其实也很简单,对于树中的每一层,我们只需......
  • 《贪婪算法实战:寻找最短无序连续子数组的深度解析与实现》
    ......
  • JavaScript 实现对 JSON 对象数组数据进行分页处理
    JavaScript实现对JSON对象数组数据进行分页处理在前端JavaScript中对JSON对象数组进行分页,可以通过以下方式实现:分页函数示例代码假设有一组JSON对象数据,比如一组用户信息:constdata=[{id:1,name:"Alice"},{id:2,name:"Bob"},{id:3,name:"......