wuvin
Always take risks!
Toggle navigation
wuvin
主页
实验室的搬砖生活
机器学习
公开的学术内容
公开的其他内容
About Me
归档
标签
友情链接
ZYQN
ihopenot
enigma_aw
hzwer
杨宗翰
中级数据结构
? 知识点 ?
? 数据结构 ?
2017-03-19 19:20:39
569
1
0
wuvin
? 知识点 ?
? 数据结构 ?
这一些数据结构会在一些比较简单的数据结构题考到。作为纯数据结构题的话，noip不会考，省选和NOI又太简单，只有在校内考试或者网赛会遇到。 不过维护其他问题还是有用的。比如难一点的动归、几何。 ##值域线段树 就像把线段树建在了一个表上。一般我们计算一个区间中某个数出现多少次的时候会有b[a[i]]++;这样的动作。a数组就是原数组，b数组是他的值域数组。在b数组上建立线段树可以做到查询第k大、支持一些修改后的k大、插入一个整数查询一个整数是否存在。值域线段树没有用的节点可以不用先建立出来。自然也有值域数组。 ##线段树合并 要合并线段树要求两个线段树在结构上完全相同，详见黄嘉泰论文。可以做到n棵主席树nlogn的合并。在一些区间合并时合并对应的值域线段树有用。尤其是**维护树上信息**时相当有用。 ##可持久化线段树 又称主席树。可持久化的思想就是新建代替修改，保留原有版本。有两种方式：**path copy**和**fat node**。path copy常见于有指针建立的数据结构，而fat node就是用于一些必须用数组访问的数据结构。线段树一般采用path copy，对于一个修改二分下去之后每次到达的一个节点就复制该节点后修改。这样没有改变的部分就和原有节点共用。（不必担心共用节点会被更改，因为可持久化不改变原有节点。）这样就有了o(1)复制一个数组的能力（其实就是复制线段树根节点），然后log(n)的单点修改、查询。这样就可以在nlogn的时间内完成建立n个相似的值域线段树。这样就可以完成区间k大、众数之类的支持区间减法的值域数组干的事了。fat node就是给每个节点建立一个set，查询（版本号，数据）。 ##树状数组 没什么说的。只是可以拓展到高维而已。但是空间有点捉急。这时就可以上hash了。 ##平衡树 由排序二叉树衍生出来的许多树。比如Treap、Splay、替罪羊树、朝鲜树、重量平衡树等。
上一篇:
计算几何基础
下一篇:
简单数据结构
1
赞
569 人读过
新浪微博
微信
腾讯微博
QQ空间
人人网
提交评论
立即登录
, 发表评论.
没有帐号?
立即注册
0
条评论
More...
文档导航
wuvin
没有帐号? 立即注册