国家集训队2009论文集线段跳表——跳表的一

《国家集训队2009论文集线段跳表——跳表的一》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、线段跳表——跳表的一个拓展河北省石家庄二中李骥扬内容梗概跳表跳表的结构跳表的字典操作线段跳表跳表中的隐式线段树两类区间信息的维护优势与效率分析(ppt中略去)跳表跳表的结构跳表的字典操作跳表的结构跳表由多条链表L1……LN以及下行指针构成每条链表包含元素检索值单调递增，包含两个特殊节点-∞(起始节点)和+∞(终止节点)L1包含所有元素，对任意的i>0，Li+1是Li的子集，且Li+1中的每一个节点，有一个下行指针，指向Li中与之有相同索引值的节点。跳表的字典操作查找(以查找检索值为8的节点为例)跳表的字典操作插入v=8先

2、随机化得出插入的节点的高度hh=1h=h+1输出hp的几率(1-p)的几率得到h=2跳表的字典操作插入v=8插入前搜索v，设尝试过但没有走的边为红色然后向跳表的1至h=2层红色边插入检索值为v的节点Path(v)跳表的字典操作删除v=8类似插入，先查找v，标记检索值为v的节点为红色删除红色节点，维护跳表结构线段跳表跳表中的隐式线段树两类区间信息的维护跳表中的隐式线段树跳表中的隐式线段树进一步，将每个节点v的查找路径上节点都标记上v。即可得到：跳表中的隐式线段树再进一步，将标记值换成一个左闭右开的区间。再在第一层之下加入第

3、零层。向第一层节点添加下行指针。跳表中的隐式线段树我将这样包含区间信息的跳表称为"线段跳表"区间的左边界为该节点的索引值。而区间的右边界可以叙述如下：设搜索该节点过程中最后一次经历的纵向边为u->v，则该节点右边界为u的后继节点的索引值。该值不需额外存储，每次搜索过程中即可动态获得。两类区间信息的维护DP信息(DPi)：树形DP时存储的某一区间的信息。e.g.区间内的点的个数、最大值最小值等。特征是每一个节点都保存此信息，而这个信息是由区间的孩子(子区间)得出的。线段信息(SEGi)：线段树中存储的信息。e.g.区间的染色情

4、况等等。特征是并非所有的节点都需要保存此信息。添加信息时，选择尽量高的节点进行操作(染色等)。两类区间信息的维护插入两类区间信息的维护插入[4,5.5)Path(v)Path(v-ε)两类区间信息的维护插入1.沿Path(v)下分SEGi信息，并通过此过程，得出v节点的SEGi信息。2.插入检索值为v的块，并且设置底层节点的SEGi值为之前求出的SEGi值。3.沿Rev-Path(v)顺序更新路径上各节点的DPi信息。4.沿Rev-Path(v-ε)顺序更新路径上各节点的DPi信息。两类区间信息的维护删除1.清理被覆

5、盖的SEGi信息。2.判断要删除的节点是否为当前某一覆盖范围的端点。3.删除检索值为v的各个节点。4.沿Rev-Path(v)更新DPi信息。线段跳表，通过随机化得到一个相对平衡的结构，支持线段树与平衡树能够实现的功能。相比线段树，具有能够动态处理信息，支持在线询问的特点；相比平衡树，具有编写简便、代码精简的特点。当跳表进化为了线段跳表，它能够处理的信息也更加多样。跳表及其拓展，将在众多领域发挥更大的作用。总结谢谢大家欢迎提问