数据结构总结
FourteenObsidian · · 个人记录
数据结构常见知识点
-
栈、队列、链表、哈希表（单调栈、单调队列）
-
并查集（扩展域，边带权）
-
堆（*可并）
-
分块、莫队
-
ST 表
-
trie(01trie)
-
树状数组
-
线段树（主席树、线段树分治）
-
*平衡树
-
*树链剖分
-
点分治
-
*cdq 分治
-
*树套树
-
*K-D Tree
trick
-
做数据结构题的时候，我们可以考虑当前能组合出哪些基础操作，然后再考虑把这些操作拼起来。
-
如果一个变量解决不了问题，那就用两个。
-
分析时分预处理、修改、查询三部分分析。
-
二维数点的转换
-
关于“在过去的多少秒内XXX”的问题可以按序列维排序所有操作，再把时间维插入数据结构。如序列。
-
上面的做法同样可以用在值域与序列的关系上。
-
换根，dfs 序最多也只会裂成两段。
-
时间戳。可以做题（NOI2021D1T1），也可以用于清空数据结构。
-
观察总方案数，然后做离散化之类的操作（本质上也是利用均摊）。
-
出现次数，
\sum\limits_x cnt_x=n ，可以考虑对于所有x ，把1\cdot x,2\cdot x,\ldots,cnt_x\cdot x 放在一起维护。 -
模意义下相同，或出现次数相同，之类的子段，可以转化成找两个模意义下/出现次数相同的前后缀。比如 HNOI2016 大数。
-
重排回文串
\rightarrow 出现的奇偶性\rightarrow 异或。 -
维护一个东西，序列静态，那么在分治结构上，可以基于分治处理出满足一些条件下的答案，求答案的时候就只要根据满足条件的情况计算。
-
区间 chkmin ，最后求每个点的值，可以直接类似标记永久化，但要类似 ST 表拆出两个区间，最后用大区间推到小区间即可
O(q)-O(n\log n) 。
technology
高维离散化
对于一个数
开个 vector 在 v[1],v[2]...v[y] 中都 push_back(x)，然后对于每个 vector 分别进行离散化。
保证了空间线性。
线段树&平衡树
线段树五问：
1、每个区间需要记录哪些值？
2、需要哪些标记？
3、如何叠加标记（在原有标记的区间增加新的标记？）
4、如何对区间进行整体修改？
5、如何合并区间？
打上各种 tag
这个不用多说。区间加、区间乘、区间推平、区间翻转、区间
维护前缀、后缀和整体信息
比如最大子段和。一般用于处理最优子段问题。
拆式子
面对难以维护的式子，我们可以考虑把它拆开分别维护，比如区间方差、区间
维护很多维的信息
当我们发现题目中一个方面难以维护但相关维度的数据范围较小的话，我们可以考虑直接维护这些信息。比如那个五维的曼哈顿距离
观察所求东西在分治结构中的贡献
比如说区间询问所有数两两乘积之和，这个当然可以拆成和的平方减平方的和再除以
与二分结合
这个其实有很多东西的，在这里数据结构做的事大概是求值并判定。
二维数点
二位的信息可以向二维数点的方向思考。
静态的话可以尝用主席树做
均摊
常见的有颜色段均摊，这个就是 ODT。
还有值域上减小次数的均摊。注意证明复杂度。同时，可以考虑最坏情况下总体完整的操作次数来达到均摊。
在值域均摊的同也可以考虑颜色段均摊，如 UOJ228。
减少状态
可以利用一些性质，如单调性来减少需要维护的信息数量。
其他的东西
- 维护合法的答案端点
分块&莫队
分块和莫队有着较强的问题处理能力，能解决许多分治结构难以处理的问题。
动态分块：
暴力维护+打tag
。。。
块内维护有序数组
区间加法操作时，整块打标记，零散块归并重构。
各种根号平衡 。。。
莫队
理想莫队信息：维护一个子集的信息，支持
莫队是
套用根号平衡
莫队相当于有
所以在每次询问的时候可以套用大量
尝试降维
把高维莫队降成低维的！
常见降维方法：差分。
莫队二次离线
维护的是可差分的信息。
转化为前缀相减的问题。
树上莫队
用括号序维护，（：插入，）：删除。
带修莫队
加上时间线，升维一下就好了
自然根号
- 总和为
O(n) 的数列本质不同的出现次数为O(\sqrt n) 。
不自然的根号
- 光速幂