# [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，将目标节点调整到根节点的位置。
2. zig-zig:当目标节点是根节点的 左（右）子节点的左（右）子节点 时，进行一次zig-zig，将目标节点调整到根节点位置。
3. zig-zag:当目标节点是根节点的 左（右）子节点的右（左）子节点 时，进行一次zig-zag，将目标节点调整到根节点位置。

Posted on | 评论

# [Dr.Lib]Note:Algorithm – SSSP

## SPFA

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

Posted on | 评论

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

。。也没什么好说的了，《Size Balanced Tree》（CQF WC 2006）说的很清楚了……

Posted on | 评论

# [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

Posted on | 评论

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

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

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）域来保持平衡的二叉搜索树，它也因此得名。它总是满足：

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]]]

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

## 旋转

SBT的旋转（Rotations）与其他许多高级BST相同。它是下面提到的Maintain操作的基础。

## 保持性质(Maintain)

1. 第一种情况：s[left[left[t]]>s[right[t]]
如图3，执行完Insert(left[t],v)后发生S[A]>S[R]，我们可以执行以下的指令来修复SBT：
1. 首先执行Right-Ratote(t)，这个操作让图3变成图4；
2. 在这之后，有时候这棵树还仍然不是一棵SBT，因为 s[C]>s[B] 或者 s[D]>s[B] 也是可能发生的。所以就有必要继续调用Maintain(T)。
3. 结点L的右子树有可能被连续调整，因为有可能由于性质的破坏需要再一次运行Maintain(L)。
2. 第二种情况：s[right[left[t]]>s[right[t]]
在执行完Insert(left[t],v)后发生s[B]>s[R]，如图5，这种调整要比情况1复杂一些。我们可以执行下面的操作来修复：
1. 在执行完Left-Ratote(L)后，图5就会变成下面图6那样了。
2. 然后执行Right-Ratote(T)，最后的结果就会由图6转变成为下面的图7。
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对称。

……且听下回分解