这里说的新年特指中国农历龙年，明天就是除夕夜，所以在此说说。很久不更新blog是因为的确没什么好更新的。我喜欢将自己的研究项目，解题报告发到博客上，可是，上了大学，这方面的事情少很多。要说研究还是有的，但是直观价值不大。我不想总结这一学期，ms是小小的延续了一下高中的状态。可是愈到期末愈好了。所以可以预见到下个学期会好很多。
要说我特别想说的就是，在某些方面有预见性的进步。对于个人能力，潜力我都表示无所顾忌。也不需要，不必要。能开心的“娱乐”、“玩”就很好了（想不到有什么其他更好的词了，如果想到我一定会写上的）。然后呢，说说成果，这个学期积累多成果少。这种状态就很不错，至少我比较满意了，比高中强。高中嘛积累不算少，成果也不多，可就是不及大学。
老规矩，不说点我认为有用的，我就认为这篇blog价值不大。什么是有用的？特指我认为有用的。
当然，在这里我不想附上 Cauchy不等式的证明，这个的价值还不如鬼谷子的数学难题价值大。网上有的是。也不想公布适用范围很小的某某定理。更不想证明连续数项和以及方和方差公式（估计以我国奥数水平小学生都会XD）。特别是，这些其实比较无聊。所以，就当是复习，论述一下二叉树吧。
二叉树的检索价值显而易见，原理就是二分检索。复杂度logN。我们在使用线性的二分检索时，不可避免的要使用有序化操作，考虑到一些抽象的离散模型，这个操作进行完成后，也就是有序化后从宏观角度看（如果是一系列数串）可以认定为最小（最大）表示。所以我个人认为也可看作是最小（大）表示法的离散抽象序列。
那么m次检索有O(MlogN).可是很少见实际问题中是有序的数列，所以加上排序O(NlogN+MlogN)=O(ClogN),M与N给定后视作一个较大的常数。所以乍一看，也不是logN阶的，是吧。要是二叉检索树（因为是线性二分，要是平面的四分，立体的8分另外考虑），插入是logN,其实每次插入N都不一样，每次的阶都是上次+1。所以呢插入后再去检索的时间复杂度的阶会有和线性二分一样的结果。一个特殊的例子是线段树，也是二叉树一大类的。
不过二叉检索树的一个巨大优势是他的在线效应。普通的二分是离线的，每次插入新的检索元都要重新排序造成不必要的损耗（有人说链表，链表实现二分会得不偿失的，Hash吧，不过不想讨论Hash）。这是一大弊端，可是他稳定。二叉树是不稳定的，有时会退化成一条链，这就是成了线性检索了= =。因此要让其平衡，最初有科学家发明了AVL，很强大的自平衡二叉树，之后什么红黑，什么AA什么BB都有了。可是偏偏我们要讨论一个性价比很高的Treap，Treap的诞生归功于实验，大量的实验表明随机的一串离散抽象数数据有超过96%的可能在构造二叉树时是平衡的，那么就让Treap有个权值假设是随机的赋予的，这样的话用构建堆的形式去建树就是理论上96%的可能是平衡树了。
这要归功于随机数，即便是伪随机，他的分布很均匀。事实上在用时，不止96%的可能（这个问题留给读者），那么显然要高于96%,说不定99%。实现简单是Treap的优点，因为Treap=BST+Heap。我国的一位OI界天才发明的SBT也是类似于Treap的非严格平衡树(AVL和红黑是严格平衡的)，不过SBT却结合了Splay（AVL的衍生，非严格）的优点，对于区间数据的操作很好，这是Treap没有的。
但是如果只是一般的检索而不是有什么特殊处理的话那些几十行上百行的代码可以替代为#include<set>
到此为止，一堆文字，祝愿大家龙年吉祥！