[Dr.Lib]Note:Data Structures – Size Balanced Tree – I

。。按惯例笔记贴都是摘抄、转载的……TAT看了半天貌似还是不会写的样子……滚回去复习主席树了

Via NOCOW http://www.nocow.cn/index.php/Size_Balanced_Tree

Size Balanced Tree(SBT)是一种平衡二叉查找树。它的论文由中国广东中山纪念中学的陈启峰于2006年底完成,并在Winter Camp 2007中发表。由于SBT的拼写很容易找到中文谐音,它常被中国的OIer们戏称为“傻X树”、“Super BT”等。但它的性能并不SB,编写起来也并不BT。恰恰相反,SBT易于实现,且据陈启峰论文中所言,“这是目前为止速度最快的高级二叉搜索树”。它能在O(logn)的时间内完成所有BST的相关操作。而且由于SBT赖以保持平衡的是Size域而不是其他“无用”的域,它可以很方便地实现动态顺序统计中的select和rank。

性质

Size Balanced Tree(SBT)是一种通过大小(Size)域来保持平衡的二叉搜索树,它也因此得名。它总是满足:
对于SBT的每一个结点 t:

  1. 性质(a) s[right[t] ]≥s[left[left[t]]],s[right[left[t]]]
  2. 性质(b) s[left[t] ]≥s[right[right[t]]],s[left[right[t]]]

即每棵子树的大小不小于其兄弟的子树大小。

 

 

 

 

Sbt1.PNG
如图(圈代表结点,三角代表SBT,下同):

 

 

 

 

  1. s[R] ≥ s[A],s[B]
  2. s[L] ≥ s[C],s[D]

旋转

SBT的旋转(Rotations)与其他许多高级BST相同。它是下面提到的Maintain操作的基础。
Sbt2.PNG

 

 

保持性质(Maintain)

当我们插入或删除一个结点后,SBT的大小就发生了改变。这种改变有可能导致性质(a)或(b)被破坏。这时,我们需要用Maintain操作来修复这棵树。Maintain操作是SBT中最具活力的一个独特过程;Maintain(T)用于修复以T为根的 SBT。调用Maintain(T)的前提条件是T的子树都已经是SBT了。
我们需要讨论的有4种情况。由于性质a和性质b是对称的,所以我们仅仅详细的讨论性质a。

  1. 第一种情况:s[left[left[t]]>s[right[t]]
    Sbt1.PNG
    如图3,执行完Insert(left[t],v)后发生S[A]>S[R],我们可以执行以下的指令来修复SBT:
    1. 首先执行Right-Ratote(t),这个操作让图3变成图4;
      Sbt4.PNG
    2. 在这之后,有时候这棵树还仍然不是一棵SBT,因为 s[C]>s[B] 或者 s[D]>s[B] 也是可能发生的。所以就有必要继续调用Maintain(T)。
    3. 结点L的右子树有可能被连续调整,因为有可能由于性质的破坏需要再一次运行Maintain(L)。
  2. 第二种情况:s[right[left[t]]>s[right[t]]
    Sbt5.PNG
    在执行完Insert(left[t],v)后发生s[B]>s[R],如图5,这种调整要比情况1复杂一些。我们可以执行下面的操作来修复:
    1. 在执行完Left-Ratote(L)后,图5就会变成下面图6那样了。
      Sbt6.PNG
    2. 然后执行Right-Ratote(T),最后的结果就会由图6转变成为下面的图7。
      Sbt7.PNG
    3. 在第1步和第2步过后,整棵树就变得非常不可预料了。万幸的是,在图7中,子树A、E、F和R仍就是SBT,所以我们可以调用Maintain(L)和Maintain(T)来修复结点B的子树。
    4. 在第3步之后,子树都已经是SBT了,但是在结点B上还可能不满足性质a或性质b,因此我们需要再一次调用Maintain(B)。
  3. 第三种情况:s[right[right[t]]>s[left[t]]
    与情况1对称。
  4. 第四种情况:s[left[right[t]]>s[left[t]]
    与情况2对称。

通过前面的分析,很容易写出一个普通的Maintain。

前面的标准过程的伪代码有一点复杂和缓慢。通常我们可以保证性质a和性质b的满足,因此我们只需要检查情况1和情况2或者情况3和情况4,这样可以提高速度。所以在那种情况下,我们需要增加一个布尔(boolean)型变量:flag,来避免毫无意义的判断。如果flag是false,那么检查情况1和情况2;否则检查情况3和情况4。

为什么Maintain(left[t],true)和Maintain(right[t],false)被省略了呢?

……且听下回分解

[Dr.Lib]Note:Data Structures – 主席树 via 函数式线段树

偶然间翻PDF时看到了FHQ神犇的WC论文……看了一遍没记住什么……除了函数式编程其他也……就那样吧……顺手把CLJ的论文也看了一遍……//可持久化做法很多,函数式是种比较科学的实现……暴力复制、wzk树什么的就不说了……

然后函数式编程早就接触过但从来没有研究过TAT显然函数式线段树最成功的应用(之一?)就是主席树了……

函数式编程

修改元素是数据结构的一个基本操作,平常的实践中我们比较常见的就是直接改储存的值,而函数式编程中,我们从不去修改值,而是再定义一个。

对应在线段树操作中,我们每次修改值,都不会去修改任何节点,而是返回一棵新的树。

函数式Treap假想图 函数式线段树

图片来自范_wc2012

因为保证所有节点都不会被修改,所以我们可以重用未受影响的节点。显然,函数式线段树中,插入操作的时间、空间复杂度都是O(log n),其他操作与正常线段树无异。

主席树

主席树是一种利用函数式线段树维护数列的数据结构,一般用来解决区间第K大数问题。设数列长度为NN,数据范围为n,已离散化。

不支持修改的主席树(前缀和主席树)

……不支持修改的主席树在我的笔记中记为前缀和主席树…自己取的名字。。。

前缀和主席树由N棵线段树组成,第i棵Ti是对于[1,i]建一棵以序列里的值为下标,储存区间里出现该值的次数的线段树,也可以看作是Ti-1插入a[i]后的线段树。

注意到所有的树是同构(?)的,Ts-1和Tt可以直接相减得到T[s,t],在树上进行二分就可以得到区间K大值。

当然,所有的线段树都指函数式线段树。

代码:Via http://www.cnblogs.com/Rlemon/archive/2013/05/23/3094635.html 我自己码的实现惨不忍睹…这是和我的风格最接近的一个…以下是按我的笔记格式码的…

 

支持修改的主席树(树状主席树)

还记得当年学数据结构时如何维护带修改区间[s,t]的区间和吗?

树状数组,简单高效。既然我们维护的是一个线段树的前缀和,何不用树状数组维护呢?

脑补一棵树状数组,每个节点是一棵线段树 。修改时,我们仅需修改log n棵线段树即可。

//貌似只有我叫它树状主席树……正解是树状数组套主席树。

代码

 

临时建立节点的主席树

//待补完
参见clj的wc论文

[Dream YOLO]NOIP2013提高组酱油报告

370/600。
还不错的成绩。
但。。。怨念的是。。D1T2的10分。。
D1
T1
显然是快速幂。。
T2
显然当上下两序列同序(对应数字排名相同时和最小。
由于要求同序所以说序列一的顺序是无关紧要的,按序列一排序后我们只需再把序列二排序即可。由于交换一次至多消除一个逆序对,答案就是按序列一排序后的逆序对数。
至今不知哪写傻了,10分。
T3
当时写了一个裸并查集。。60。。
和YY聊了聊才发现应该先跑一个最大生成树的。。
D2
T1&T2都是喜闻乐见的题型。
n^2可以做,nlogn可以做,线性也可以做。。
我们那考场一位大神两题写了五个线段树(T1真的很像线段树操作喂。。
T1推了15分钟差分,5分钟码代码,10分钟对拍。
T2第一眼看过去是DP,看了下数据范围不大对了。
思考了五分钟,发现可以用数据结构优化。
先码了一个裸DP,试了一下貌似还可以,于是又推了一会题目,没看出什么东西来。
然后看了看第三题,我估计只会爆搜了,于是发呆5分钟开始重新码T2。
稳妥起见先码了一个离散化,把h搞到1~n(还有一个原因是h=0的话zkw线段树会囧。。。这是我后来才发现的。)
写了俩zkw分别记录当前处理到的这一棵是目标序列中奇数位和偶数位的情况。然后两种情况分别算一次。
然后写树的时候开闭区间没注意。。调了20分钟。。七弄八弄就交卷了囧。D2倒是A了两题……

发自 WordPress for Android

[Dr.Lib]Note:Data Structures – 关于存图

想当年,我只会用邻接矩阵,MLE的感人肺腑啊!

看最短路算法时,很多遍历边的方法我都看不懂。于是专门刷了一下存图……在此做个回顾总结。

部分来源于NOCOW。在此感谢。

邻接矩阵

作为图的一种储存方式,实际上就是一个二维数组。即为记为map[i][j],map[i][j]为节点i到节点j之间的边的权值,若不存在边,则为-1或其他。

这种储存方式的优势是书写方便,但缺点是非稠密图空间效率不高。相比之下,稍微麻烦点的前向星,邻接表等结构更加快速。

邻接表

邻接表是图的一种链式存储结构,在邻接表中,对图中每个顶点建立一个单链表,n个顶点,就要建n个链表。

第i个单链表中的结点表示依赖于顶点vi的边。单链表中每一个结点称为表结点,应包括三个域邻接点域、链域和数据域。邻接点域,用以存放与vi相邻接的顶点序号;链域用以指向与vi邻接的下一个结点,数据域存储和边或弧有关的的信息。

但是,为什么一定要链表呢?

有vector为什么不用呢?

前向星

前向星构造方法如下:

读入每条边的信息

将边存放在数组中

把数组中的边按照起点顺序排序

链式前向星

嗯,排序,快排,nlogn。

你看看人家存边只要O(n)……(如果你会计数排序的话……也行

那么……链式前向星。

还有吗……

十字链表和邻接多重表……在OI中还真没怎么见过

[Dr.Lib]Note:Data Structures – C++ STL

本着不重新发明轮子的原则,我很少手码快排和其他数据结构……基本都是拖STL出来用……

STL中还是有不少实用的数据结构的……set,bitset,priority_queue,queue,vector,map……

bitset

Via http://www.cplusplus.com/reference/bitset/bitset/

Member functions

(constructor)
Construct bitset (public member function )
applicable operators
Bitset operators (function )

 

Bit access

operator[]
Access bit (public member function )
count
Count bits set (public member function )
size
Return size (public member function )
test
Return bit value (public member function )
any
Test if any bit is set (public member function )
none
Test if no bit is set (public member function )
all 
Test if all bits are set (public member function )

 

Bit operations

set
Set bits (public member function )
reset
Reset bits (public member function )
flip
Flip bits (public member function )

 

Bitset operations

to_string
Convert to string (public member function )
to_ulong
Convert to unsigned long integer (public member function )
to_ullong 
Convert to unsigned long long (public member function )

在一些模拟中……bitset还是不错的……不过用处也不是很大……

priority_queue

Member functions

(constructor)
Construct priority queue (public member function )
empty
Test whether container is empty (public member function )
size
Return size (public member function )
top
Access top element (public member function )
push
Insert element (public member function )
emplace 
Construct and insert element (public member function )
pop
Remove top element (public member function )
swap 
Swap contents (public member function )

优先队列的用处就比较多了,据说优先队列优化dij秒爆SPFA[来源请求]……

只要定义了 operator< ,就可以用优先队列来做成大顶堆。小顶堆……要么改operator<,要么

priority_queue<T, vector<T>, greater<T> >

queue

Member functions

(constructor)
Construct queue (public member function )
empty
Test whether container is empty (public member function )
size
Return size (public member function )
front
Access next element (public member function )
back
Access last element (public member function )
push
Insert element (public member function )
emplace 
Construct and insert element (public member function )
pop
Remove next element (public member function )
swap 
Swap contents (public member function )

有优先队列优化的dij,就有队列优化的Bellman-Ford……

vector

Member functions

(constructor)
Construct vector (public member function )
(destructor)
Vector destructor (public member function )
operator=
Assign content (public member function )

Iterators:

begin
Return iterator to beginning (public member function )
end
Return iterator to end (public member function )
rbegin
Return reverse iterator to reverse beginning (public member function )
rend
Return reverse iterator to reverse end (public member function )
cbegin 
Return const_iterator to beginning (public member function )
cend 
Return const_iterator to end (public member function )
crbegin 
Return const_reverse_iterator to reverse beginning (public member function )
crend 
Return const_reverse_iterator to reverse end (public member function )

Capacity:

size
Return size (public member function )
max_size
Return maximum size (public member function )
resize
Change size (public member function )
capacity
Return size of allocated storage capacity (public member function )
empty
Test whether vector is empty (public member function )
reserve
Request a change in capacity (public member function )
shrink_to_fit 
Shrink to fit (public member function )

Element access:

operator[]
Access element (public member function )
at
Access element (public member function )
front
Access first element (public member function )
back
Access last element (public member function )
data 
Access data (public member function )

Modifiers:

assign
Assign vector content (public member function )
push_back
Add element at the end (public member function )
pop_back
Delete last element (public member function )
insert
Insert elements (public member function )
erase
Erase elements (public member function )
swap
Swap content (public member function )
clear
Clear content (public member function )
emplace 
Construct and insert element (public member function )
emplace_back 
Construct and insert element at the end (public member function )

Allocator:

get_allocator
Get allocator (public member function )

vector是个好东西,妈妈再也不用担心我的内存!

数组开大了爆内存,开小了爆下标……WTF……

还用的着担心邻接表MLE?vector没有压力。

map

Member functions

(constructor)
Construct multimap (public member function )
(destructor)
Multimap destructor (public member function )
operator=
Copy container content (public member function )

Iterators:

begin
Return iterator to beginning (public member function )
end
Return iterator to end (public member function )
rbegin
Return reverse iterator to reverse beginning (public member function )
rend
Return reverse iterator to reverse end (public member function )
cbegin 
Return const_iterator to beginning (public member function )
cend 
Return const_iterator to end (public member function )
crbegin 
Return const_reverse_iterator to reverse beginning (public member function )
crend 
Return const_reverse_iterator to reverse end (public member function )

Capacity:

empty
Test whether container is empty (public member function )
size
Return container size (public member function )
max_size
Return maximum size (public member function )

Modifiers:

insert
Insert element (public member function )
erase
Erase elements (public member function )
swap
Swap content (public member function )
clear
Clear content (public member function )
emplace 
Construct and insert element (public member function )
emplace_hint 
Construct and insert element with hint (public member function )

Observers:

key_comp
Return key comparison object (public member function )
value_comp
Return value comparison object (public member function )

Operations:

find
Get iterator to element (public member function )
count
Count elements with a specific key (public member function )
lower_bound
Return iterator to lower bound (public member function )
upper_bound
Return iterator to upper bound (public member function )
equal_range
Get range of equal elements (public member function )

Allocator:

get_allocator
Get allocator (public member function )

map用在一些需要存储键值对的地方……在一些需要维护数据的地方用这个偷懒一下也不错……

别忘了multimap。