数据结构方法总结
上个世纪,Niklaus Wirth 提出:程序=算法+数据结构(初赛要考qaq)
数据结构是一种处理数据的方法,很明显是必不可少的。
oi中的数据结构,除去数组,栈,队列等sb数据结构,根据复杂度可大致分为 log 结构和 sqrt 结构(我自己胡的说法,很明显不严谨)。其中log以线段树,平衡树,树套树为代表,而sqrt以分块,莫队为代表。
而这里,我们讨论一个更高层的问题:如何综合的运用这些东西。
转化
很多问题是不能直接做的,都需要转化。转化问题这件事,往往是做题的第一步/前几步。
转化有多种多样的,在数据结构题中,所做的转化需要围绕着 方便维护 来转化。
-
loj2873:“单峰序列” -> 从中间开始,递减的往两边加数,自然就会形成一个“峰”
-
loj2346:斜向操作 -> 水平竖直的操作(转坐标轴)
-
区间中不同的数 -> 只统计pre<l的数
-
区间中只出现一次 -> pre<l,suf>r
注:pre,suf是解决 “本质不同” “出现次数” 等问题的有力工具
我们联合
很多题目是不能靠一个算法搞定的,通常需要几个算法配合解决。
数据结构方面的算法,通常可以快速/块速的维护一些东西,以起到优化复杂度的作用。
有的题目甚至可以直接在数据结构上做,我没见过
比如,在线段树上跑树形dp,我纯口胡的,没见过
- CF809D:注意到这个dp有 (f_i=f_{i-1}+...) 的形式,即区间平移后区间加,用平衡树的插入与lazytag来优化
- CF573E:推出本题的贪心策略之后,用平衡树维护
- 经典应用:SAM+线段树合并
- CF833B:用上面的pre转化后,注意到 (f) 的转移相当于一个区间+区间max,线段树维护
- 经典应用:线段树优化建图
- 经典应用:树套树(这个相当于两种数据结构互相配合)
常见应用
- 区间取min:seg-beats
- 区间平移/翻转:平衡树
- 来来回回区间贡献:线段树+脑子
- 部分非强制在线题:扫描线+线段树
- 已知一个数,选一个数,max xor:trie
- 不好做的区间信息:分块
怎么只有这么点东西啊
做题少,抱歉啊qaq