首页 > 编程语言 > 详细

线段树与树状数组的综合运用

时间:2018-07-13 00:40:40      阅读:33      评论:0      收藏:0      [点我收藏+]

标签:两个   遇到   省选   情况   莫队   erl   lib   答案   rmq   

前言:线段树树状数组是高级数据结构最基本的部分,数据结构又是省选最基本的部分,所以从他开始整理一下。

题目以洛谷和bz为基底

1.基础运用

数据结构最基本的问题就是操作和询问的问题,

修改可以分为点修改(包括点的函数运算) 区间运算 区间最大最小和取模 区间set

其中点修改就是领出树上的一条长链,对其末端进行花式操作

区间修改就有点意思了

{

写过线段树再过来看寒文的人大概都烂熟lazy tag 这个东西刚学的时候确实还是一个障碍。

刘汝佳的蓝书上提到了区间set 这其实并不难只是难写吧(区间maxmin和区间set一样 下传标记加个if就可以)

区间取模我还是在一个PDF里学的 其精髓是保存节点附加信息的时候多三个——maxsumofmaxsecondmax(看名字能理解吧)然后

我们来试着打一打补丁。

下面为引用

 ? 对线段树上的每一个区间维护区间最大值mx,这个区间中最大值出 现的次数t,区间次大值se,当然还要维护区间和sum ? 现在考虑打上区间取min标记x

 ? 如果mx<=x,那么对sum就没有修改。

 ? 如果se<x<mx,那么sum=sum-(mx-x)×t

? 如果x<=se<mx,那么…  

? 如果遇到这种情况,我们分别DFS这个节点的两个孩子,如果当前 DFS的过程中遇到了前两种情况,就直接修改打上标记然后退出,否 则就继续DFS

}

查询则有点查询(因为毫无意义实在不常见)区间和查询 区间查询运算答案 区间最大最小值 历史最大最小值

由于点修改点查询是数组的运用。。。。于是就从区间查询开始

·区间和查询

这是最基本的一种线段树(树状数组运用)建议一个月写一下保持手感

洛谷p3374就很好不过线段树只能打70,无视就好

另外p3372线段树模板1P2023 [AHOI2009]维护序列都不错

·区间运算。这个其实还分很多种,不过都是在节点信息上做手脚(注意lazytag运用结合律的姿势)

P3373线段树模板2

·区间最大最小值

RMQRMQRMQMRMQ问题。。。。。。请线段树只是处理动态问题的rmq,极为好写因为这其实是点查询。。。。。。

P3865ST表(线段树还是70,无视即可)

·历史查询最大值。

我们把修改映射到树上。

比如12345的树我们观察到查询的节点(记录下来)发生了+a,+b,=0,=c,-d,+e……的操作,求得就是这个东西的区间最大。

如果有乘除模和函数运算,就不大好弄了(有待更新

这其实是一个小应用,它包含的是下面的思想但是我们观察到树高度达不到1000

所以m(query times)log^2 n的动规解决也可以,这个复杂度虽然容易被卡但是n1000000,m1000000的数据还是很大概率可以的,动规加点卡常也许就很稳了。

·动态数列区间最大子段和

蓝书上的例题9 LA3938援引洛杉矶大学题库里的。

线段树,建树过程中要标记

max_all:最大连续和

max_prefix:最大前缀和

max_suffix:最大后缀和

pre_r:最大前缀的结束位置

suf_l:最大后缀的开始位置

sum:区间总和

对于更新,由于要x尽量小与y尽量小,所以在更新的时候我们要确定好更新的顺序,也就是l先尽量小,然后才是y尽量小

更新有5种状况,那么按顺序就是

1.左边的sum+右区间的max_prefix;

2.左区间max_all

3.左边的max_suffix+右边的max_prefix

4.左边的max_suffix+右边的sum

5.右边的max_all

可以说是很有首创难度思维难度。

 

题目:有待更新

 

2.改变存点方式。

印象最深的改变点的信息就是主席树了。。。。

La4329不错

这个东西其实是一类大型题目(考烂了)

分块莫队都可以解决

P2184贪婪大陆

P1972HH的项链

P1908逆序对

这类题目都可以用桶子数组前缀和的方式解决

什么意思呢,就是离散化保存set,加入就改它的对应位置+1,这个时候解决的就是区间个数差问题(前缀和思想)

3.有待发现

学习无止境~~~~~~~~~

 

线段树与树状数组的综合运用

标签:两个   遇到   省选   情况   莫队   erl   lib   答案   rmq   

原文:https://www.cnblogs.com/iboom/p/9302544.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号