wuvin
Always take risks!
Toggle navigation
wuvin
主页
实验室的搬砖生活
机器学习
公开的学术内容
公开的其他内容
About Me
归档
标签
友情链接
ZYQN
ihopenot
enigma_aw
hzwer
杨宗翰
简单数据结构
? 知识点 ?
? 数据结构 ?
2017-03-19 19:18:14
224
0
0
wuvin
? 知识点 ?
? 数据结构 ?
这是对最近的一些学习的总结。 这一些数据结构是一般会在动归题、几何题用到的。 ##单调栈 维护一个栈的单调性，比如521的栈加入3后就应该弹出2 1，变成5 3.用途：一般用于一个序列中求右侧第一个比自己大的数是多少，或o(n)处理一些区间信息。 ##单调队列 相对于单调栈只是加了一个关键字。(a,b)，一般用于动归中求解最值。比如要维护比bi大的所有二元组中a最小的，这样的问题。 ##并查集 用于连通性、一些简单关系的处理。路径压缩或者启发合并都可以。 ##差分 应该归入概念。相关的题：松鼠的新家。 ##hash表 字符串骗分神器。也可以替代一个开不下的数组（一般开不下的东西都遍历不完）。 ##ST表 其实并没有什么用。知识学习一下2^k的思路而已。类似的有lca的倍增求解。那个到特有用。 ##树状数组 前缀拆分利器。据说数组数组的常数只有线段树的1/8.可以用来求一些前缀或者支持区间减法的比如区间和。 ##线段树 区间拆分利器。可以对于一个区间拆分成logn个区间之和。只需要支持区间加法即可。相关用途，区间加减乘除，最大和子序列、区间最值、区间取min和max。
上一篇:
中级数据结构
下一篇:
网络流构图准则
0
赞
224 人读过
新浪微博
微信
腾讯微博
QQ空间
人人网
提交评论
立即登录
, 发表评论.
没有帐号?
立即注册
0
条评论
More...
文档导航
wuvin
没有帐号? 立即注册