[Dr.Lib]Note:Data Structures – Bottom-up SPLAY

Let us play!

Let u splay!

 

BST 平均 O(logn)

Treap 期望 O(logn)

Splay 均摊 O(logn)

AVL 严格 O(logn)

SBT 严格 O(logn)

AVL不大指望能在赛场写出来,SBT在绝大多数时候是个不错的选择,Treap…嗯……但偏偏Splay被人看成是BST中的万金油……为什么呐?

Splay一个最大的特点就是:每一个操作都要splay一下……除此之外没了……

Splay

splay操作的作用就是把某一节点旋转到根,以加快之后的访问速度。它还可以在旋转过程中维持树的基本平衡。

  1. zig: 当目标节点是根节点的 左子节点 或 右子节点 时,进行一次zig,将目标节点调整到根节点的位置。
    709px-Splay_tree_zig.svg
  2. zig-zig:当目标节点是根节点的 左(右)子节点的左(右)子节点 时,进行一次zig-zig,将目标节点调整到根节点位置。
    Zigzig
  3. zig-zag:当目标节点是根节点的 左(右)子节点的右(左)子节点 时,进行一次zig-zag,将目标节点调整到根节点位置。
    Zigzag

 

重复这几种操作直到目标节点为根。

一次zig、zig-zig、zig-zag又可以分解为几次单旋。

Search/Insert/Rank/Select

与BST相同,只不过记得把插入的节点Splay到根。

Join

作用是把两棵子树S1,S2连成一个Splay,其中S1中所有元素小于S2。

先找到S1中的最大节点x,Splay到S1的根,再把x的右子树链接到S2。

Delete

先找到目标节点,Splay到根,执行Join操作即可。

代码

 

 

 

[Dr.Lib]Note:Algorithm – SSSP

最短路是图论中的基础,单源最短路SSSP是基础的基础(2333自己发明的名言……

关于图论算法之前只说了存图……唔今天先复习一下SSSP的几个算法。

Dijkstra

 SPFA

SPFA不仅是SSSP的一个算法,而更多的是一种思想。

国家集训队2009论文集SPFA算法的优化及应用

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

。。也没什么好说的了,《Size Balanced Tree》(CQF WC 2006)说的很清楚了……

今晚(昨晚?手敲的代码……不知道如何……

 

[Dr.Lib]Note:Math – Iverson bracket

In mathematics, the Iverson bracket, named after Kenneth E. Iverson, is a notation that denotes a number that is 1 if the condition in square brackets is satisfied, and 0 otherwise. More exactly,

\( [P] = \begin{cases} 1 & \text{if } P \text{ is true;} \\ 0 & \text{otherwise.} \end{cases} \)

where P is a statement that can be true or false. This notation was introduced by Kenneth E. Iverson in his programming language APL,while the specific restriction to square brackets was advocated by Donald Knuth to avoid ambiguity in parenthesized logical expressions.

The Iverson bracket converts a Boolean value to an integer value through the natural map \( \textbf{false}\mapsto 0; \textbf{true}\mapsto1 \), which allows counting to be represented as summation. For instance, the Euler phi function that counts the number of positive integers up to n which are coprime to n can be expressed by

\( \phi(n)=\sum_{i=1}^{n}[\gcd(i,n)=1],\qquad\text{for }n\in\mathbb N^+. \)

More generally the notation allows moving boundary conditions of summations (or integrals) as a separate factor into the summand, freeing up space around the summation operator, but more importantly allowing it to be manipulated algebraically. For example

\( \sum_{1\le i \le 10} i^2 = \sum_{i} i^2[1 \le i \le 10]. \)

In the first sum, the index \( i \) is limited to be in the range 1 to 10. The second sum is allowed to range over all integers, but where i is strictly less than 1 or strictly greater than 10, the summand is 0, contributing nothing to the sum. Such use of the Iverson bracket can permit easier manipulation of these expressions.

Another use of the Iverson bracket is to simplify equations with special cases. For example, the formula

\( \sum_{1\le k\le n \atop \gcd(k,n)=1}\!\!k = \frac{1}{2}n\varphi(n) \)

which is valid for n > 1 but which is off by 1/2 for n = 1. To get an identity valid for all positive integers n (i.e., all values for which \(\phi(n) \) is defined), a correction term involving the Iverson bracket may be added:

\( \sum_{1\le k\le n \atop \gcd(k,n)=1}\!\!k = \frac{1}{2}n(\varphi(n)+[n=1]) \)

 -By Wikipedia https://en.wikipedia.org/wiki/Iverson_bracket

Via Ivy – End  http://www.ivy-end.com/archives/1064

闲来无事,逛逛Mathematics。看到一道关于数列的题目,不妨拿来研究一下。原题地址

题目是这么说的,计算\[\left ( 1+\frac{1}{2}+\cdots + \frac{1}{n} \right )^{2}+\cdots + \left ( \frac{1}{n-1}+\frac{1}{n} \right )^{2}+\left ( \frac{1}{n} \right )^{2}.\]各位可以自己动笔计算一下。

下面我们主要讨论一下给出的两种种解法。

法一:

令\(S_{n}=\left ( 1+\frac{1}{2}+\cdots + \frac{1}{n} \right )^{2}+\cdots + \left ( \frac{1}{n-1}+\frac{1}{n} \right )^{2}+\left ( \frac{1}{n} \right )^{2}\)。

则\[S_{n}-S_{n-1}=\left [\left ( 1+\frac{1}{2}+\cdots + \frac{1}{n} \right )^{2}+\cdots + \left ( \frac{1}{n-1}+\frac{1}{n} \right )^{2}+\left ( \frac{1}{n} \right )^{2} \right ]\\-\left [\left ( 1+\frac{1}{2}+\cdots + \frac{1}{n-1} \right )^{2}+\cdots + \left ( \frac{1}{n-2}+\frac{1}{n-1} \right )^{2}+\left ( \frac{1}{n-1} \right )^{2} \right ].\]整理得\[S_{n}-S_{n-1}=\left [\left ( 1+\frac{1}{2}+\cdots + \frac{1}{n-1} \right )^{2}+2\cdot\left ( 1+\frac{1}{2}+\cdots + \frac{1}{n-1} \right )\cdot\left ( \frac{1}{n} \right )+\left ( \frac{1}{n} \right )^{2} \right ]\\ + \left [ \left ( \frac{1}{2}+\frac{1}{3}+\cdots + \frac{1}{n-1} \right )^{2}+2\cdot\left ( \frac{1}{2}+\frac{1}{3}+\cdots + \frac{1}{n-1} \right )\cdot\left ( \frac{1}{n} \right )+\left ( \frac{1}{n} \right )^{2} \right ]\\ + \cdots + \left [ \left ( \frac{1}{n-1} \right )^{2}+2\cdot\left ( \frac{1}{n-1} \right )\cdot\left ( \frac{1}{n} \right )+\left ( \frac{1}{n} \right )^{2} \right ]+\left [ \left ( \frac{1}{n} \right )^{2} \right ]\\-\left [\left ( 1+\frac{1}{2}+\cdots + \frac{1}{n-1} \right )^{2}+\cdots + \left ( \frac{1}{n-2}+\frac{1}{n-1} \right )^{2}+\left ( \frac{1}{n-1} \right )^{2} \right ].\]化简得\[S_{n}-S_{n-1}=n\cdot\left ( \frac{1}{n} \right )^{2}+2\cdot\frac{1}{n}\cdot\left [ 1+2\cdot\frac{1}{2}+3\cdot\frac{1}{3}+\cdots +\left ( n-1 \right )\cdot\frac{1}{n-1} \right ].\]即\[S_{n}-S_{n-1}=\frac{1}{n}+\frac{2\left ( n-1 \right )}{n}=2-\frac{1}{n}.\]运用累加法求和即可得到\[S_{n}=2n-H_{n}.\]其中\(H_{n}=1+\frac{1}{2}+\frac{1}{2}+\cdots +\frac{1}{n}.\)

法二:

这种方法比第一种方法高明很多,它需要用到一个引理——Iverson Bracket。简单的介绍一下这个引理,它的符号是中括号,当且仅当中括号里的表达式成立时,其值为\(1\),否则为\(0\)。例如\(\left [ 1 < 2 \right ]=1\),而\(\left [ 1 > 2 \right ]=0\)。

下面我们就用Iverson Bracket来求解这个问题\[S_{n}=\sum_{k}\left ( \sum_{i}\frac{1}{i}\cdot\left [ k \leq i \right ] \right )^{2}=\sum_{k}\sum_{i,j}\frac{1}{ij}\cdot\left [ k \leq i, k \leq j \right ]=\sum_{i,j}\frac{1}{ij}\sum_{k}\left [ k \leq \min\left ( i,j \right ) \right ].\]即\[S_{n}=\sum_{i,j}\frac{1}{ij}\cdot\min\left ( i,j \right )=\sum_{i,j}\frac{1}{\max\left ( i,j \right )}=\sum_{m}\frac{1}{m}\sum_{i,j}\left [ \max\left ( i,j \right )=m \right ].\]即\[S_{n}=\sum_{m}\frac{1}{m}\cdot\left ( 2m-1 \right )=2n-\sum_{m}\frac{1}{m}=2-H_{n}.\]

[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)被省略了呢?

……且听下回分解