标签 - 数据结构

? 数据结构 ?    2017-03-20 07:24:47    332    0    0

%%%whx

我们称LCT上是轻边而且正常树剖结果中也是轻边的边为轻轻边
LCT上是轻边而且正常树剖中是重边的边为轻重边

单次Access的重轻切换次数等于该路径上轻轻边轻重边的和。
轻轻边的复杂度是有保证的,不超过logn条。

我们采用势能分析轻重边的总量变。

每次一条轻重边会变成重重边,然而重重边只有在Access到相邻这个点上的时候才能被变成轻重边。所以我们每次把轻轻边重轻边的时候支付多余的一次时间费用。由于轻轻边是有保证的,所以重轻边也是有保证的。

于是总共的切换次数不超过nlogn

有点绕,不过还能看。。。。(别打我

继续去问武爷如何把logn卡满,然后武爷给了一个特别妙的主意——

建一颗满二叉树,每次插入时从根往下沿着虚边走,然后就可以了。

? 数据结构 ?    2017-03-19 20:29:11    552    0    0

我为什么要写Splay的启发式合并呢?因为这个总体的均摊复杂度是nlogn的。

只有一个log

是不是随便怎么合并都是一个logn的呢?当然不是。小树往大树先序遍历合并。

为什么要这样呢?一次splay之后可以把一棵树分成两棵树,就可以递归下去合并了,这样越合并树越小,据证明(反正我不会证)这样就可以了!^O^

? 知识点 ? ? 数据结构 ?    2017-03-19 19:20:39    497    1    0
  1. 这一些数据结构会在一些比较简单的数据结构题考到。作为纯数据结构题的话,noip不会考,省选和NOI又太简单,只有在校内考试或者网赛会遇到。

不过维护其他问题还是有用的。比如难一点的动归、几何。

值域线段树

就像把线段树建在了一个表上。一般我们计算一个区间中某个数出现多少次的时候会有b[a[i]]++;这样的动作。a数组就是原数组,b数组是他的值域数组。在b数组上建立线段树可以做到查询第k大、支持一些修改后的k大、插入一个整数查询一个整数是否存在。值域线段树没有用的节点可以不用先建立出来。自然也有值域数组。

线段树合并

要合并线段树要求两个线段树在结构上完全相同,详见黄嘉泰论文。可以做到n棵主席树nlogn的合并。在一些区间合并时合并对应的值域线段树有用。尤其是维护树上信息时相当有用。

可持久化线段树

又称主席树。可持久化的思想就是新建代替修改,保留原有版本。有两种方式:path copyfat node。path copy常见于有指针建立的数据结构,而fat node就是用于一些必须用数组访问的数据结构。线段树一般采用path copy,对于一个修改二分下去之后每次到达的一个节点就复制该节点后修改。这样没有改变的部分就和原有节点共用。(不必担心共用节点会被更改,因为可持久化不改变原有节点。)这样就有了o(1)复制一个数组的能力(其实就是复制线段树根节点),然后log(n)的单点修改、查询。这样就可以在nlogn的时间内完成建立n个相似的值域线段树。这样就可以完成区间k大、众数之类的支持区间减法的值域数组干的事了。fat node就是给每个节点建立一个set,查询(版本号,数据)。

树状数组

没什么说的。只是可以拓展到高维而已。但是空间有点捉急。这时就可以上hash了。

平衡树

由排序二叉树衍生出来的许多树。比如Treap、Splay、替罪羊树、朝鲜树、重量平衡树等。

? 知识点 ? ? 数据结构 ?    2017-03-19 19:18:14    169    0    0
  1. 这是对最近的一些学习的总结。
  2. 这一些数据结构是一般会在动归题、几何题用到的。

单调栈

维护一个栈的单调性,比如521的栈加入3后就应该弹出2 1,变成5 3.用途:一般用于一个序列中求右侧第一个比自己大的数是多少,或o(n)处理一些区间信息。

单调队列

相对于单调栈只是加了一个关键字。(a,b),一般用于动归中求解最值。比如要维护比bi大的所有二元组中a最小的,这样的问题。

并查集

用于连通性、一些简单关系的处理。路径压缩或者启发合并都可以。

差分

应该归入概念。相关的题:松鼠的新家。

hash表

字符串骗分神器。也可以替代一个开不下的数组(一般开不下的东西都遍历不完)。

ST表

其实并没有什么用。知识学习一下2^k的思路而已。类似的有lca的倍增求解。那个到特有用。

树状数组

前缀拆分利器。据说数组数组的常数只有线段树的1/8.可以用来求一些前缀或者支持区间减法的比如区间和。

线段树

区间拆分利器。可以对于一个区间拆分成logn个区间之和。只需要支持区间加法即可。相关用途,区间加减乘除,最大和子序列、区间最值、区间取min和max。