二叉查找树是一种非常有用的数据结构。经过一定扩充，它可以支持的操作有：Insert（插入）、Find（查找）、Remove（删除）、GetMax（取最大）、GetMin（取最小）、Prev（取前驱）、Next（取后继）、Rank（取某元素的序号）、Select（按照序号取该元素）。如果数据是随机的话，以上操作可以保证在O(logn)的期望时间内完成。但是比赛中显然出题者会给出一些刁钻的数据让最普通的二叉查找树严重TLE，这便是平衡二叉树得以应用的时候了。平衡二叉树可以保证以上操作是严格（AVL）或均摊（Splay）或期望（Treap）的O(logn)的时间复杂度。 平衡二叉树的实现一般有三种情形：递归、Top-Down（自顶向下）、Buttom-Up（自底向上）。递归实现可能比较好写，比如Treap的递归实现就非常短，基本的插入删除二三十行就可以搞定。Splay的一种实现方法也是递归，但这种方法是不推荐使用的。因为Splay虽然保证均摊的时间复杂度，但并不保证高度（AVL保证高度是严格的O(logn)、Treap保证高度是期望O(logn)），这就造成面对某些刁钻的数据时虽时间上不会出问题，却可能由于递归层次过多造成栈溢出。（例如连续大量升序的插入会使Splay变成一条长链，此时访问最底端的节点就会造成栈溢出。）所以Splay比较好的编写方法还是Top-Down或者Buttom-Up，它们都是非递归的。其中Top-Down的核心Splay过程有大约三四十行，性能十分优异，虽然不太好理解但是强记住也是可取的。Buttom-Up的Splay我没写过，但我知道一切Buttom-Up的平衡树都需要维护每个节点的父指针，造成了一定的编程复杂度也容易出错（比如说最基本的旋转操作就比以前麻烦多了）。Treap也可以写成Buttom-Up，不过我觉得没必要——既然选择了Treap当然就是为了它的编程复杂度低，写Buttom-Up的Treap还不如写成Top-Down或Buttom-Up的Splay，没准行数还更少呢。但相对于递归实现以及Buttom-Up来说，Top-Down的缺点是很难维护每个节点的Size域（即这棵子树的节点数或者其左子树的节点数），事实上我一直认为Top-Down Splay是无法在均摊O(logn)的和不记录父指针的前提下加入维护size域的操作的——这两个前提若不满足则或失去了Splay的本质，或失去了Top-Down的精髓。综上所述呢，在考试时选择写哪种平衡树应该这样考虑：不需要Size且数据量极大时用Top-Down Splay，需要Size或数据量一般时用递归Treap，这两者我都有把握在15min内写对；Buttom-Up的唯一好处是既非递归又能维护Size，但似乎书写是最麻烦的，何况我没写过，所以就不考虑了。 下面说说平衡树的操作。Insert和Remove这种需要改变树中元素的操作因平衡方式而异，就不细说了。Find的基本方法就是不断比较待查找值与当前节点，若小于则向左，大于则向右，等于就找到了；Splay的Find有所不同，只要Splay这个值一下看看根部有没有就行了。 GetMax是从根一直向右走直至无法再走就找到了最大值，GetMin反之，注意Splay中还需要把找到的最值再Splay一下，否则无法保证均摊的复杂度。Prev是对当前值向左走一步然后一直向右，Next相反；对于Splay只要把它先伸展到根部再这样找就行了，但对于Treap，若它的左子树或右子树是空的，注意需要返回的反而是某个祖先节点，用递归实现或Buttom-Up比较简便。Rank操作只须记录每个节点的子树的大小，然后比较当前值与左子树的大小把它分到左边或者右边，如果分到右边要把左子树和当前节点的大小都加到答案里，一般就都采用非递归的实现了（反正是一个容易消除的尾递归）。Select基本与Rank类似，也是不断比较这个序号与左子树的大小，就能知道答案在左边还是右边了。 以上操作中GetMin、GetMax可以以每次操作相同的时间复杂度上界代替二叉堆，比单纯的二叉堆的优点是支持了方便的查找和删除，还可以同时找最大值和最小值。Prev、Next、Rank、Select等操作在很多题中也各有应用。 总的来说，对于这种用处广泛考察很多的数据结构来说，最好还是透彻地理解、熟练的背诵。
Wednesday, April 18, 2007
几周前终于做完了USACO Training的全部题目，感觉收获极丰，便有将这些题目做一总结的想法。 写时根据算法对题目进行分类，只求使自己从USACO中得到的知识条理化、系统化，并不求能给他人什么教诲。 笔耕数日，终于约一周前写完全部四篇初稿。又经过近日的几度增添润色和几位好友的帮忙校对，终能在省选的前夕发布所谓“正式版”。 本人自知水平有限，文中断少珠玑之言，而若此“心得”能为你的OI征程有所裨益，也不枉本人几周来的一番心血。 下载地址
Wednesday, April 18, 2007
首先还是忍不住要扯一下伊朗同学。伊朗同学很悲惨，由于伊朗严格男女分校，所以从小就没见过几个女生，特别是从未见过任何女生的头发。所以伊朗同学在我问到“Have you ever fell in love?”时才会好像很惊异的样子……他好像从来都没跟女生说过话，所以利用他要到伊朗MM的MSN的想法似乎也已经泡汤了…… 跟伊朗同学讨论了几道题目，有伊朗国家队选拔赛里的，还有一些OJ里的。有一次他问我“is internet in your country free?”，我不大知道怎么回答，因为GFW这东西不大好描述，然后我就简单的说“some websites are forbidden”。我以前听说伊朗对网络的管制比较严重…… 由于伊朗MM计划的泡汤，所以伊朗同学目前看来已经没有利用价值了，下面开始扯近日的事儿。21日星期六要在郑州比赛，计划在前一天也就是20日星期五下午出发。可是令人郁闷的是……学校的合唱比赛初赛在20日星期五下午五时左右开始。也就是说……本来作为本班首席指挥的我，由于时间冲突已经无法登台了，只能交给文艺委员MM来指挥。现在看看前几天发的帖子，突然觉得有点“一语成谶”的意味：我为啥要说成“高二13班首席指挥”，为啥不说“高二13班指挥”呢？难道我那时便已料定指挥不仅会有我一个还会有个准备接替我的？当然，这其实是扯淡。 还是想想越来越近的比赛吧。目前感觉从实力的角度我还是没问题的，各种题目都已见过做过，没什么知识上的盲区。最近做题状态也不错，能保证会了的题目都做对。到时候只要脑子活一点，不要思路错了还发懵死不悔改就行了。 我一定会成功的。
Wednesday, April 18, 2007
树状数组(Binary Indexed Tree)是又一种静态的树结构。它的首要用途是用于维护前缀和，也即：一数组a[1..n]，随时会改变其中某a[i]，还会询问s[i]=a[1]+a[2]+…+a[i]，树状数组可完美解决这一问题。 定义数组c[0..n]，其中c[i]=a[i-2^k+1]+a[i-a^k+2]+…+a[i]，其中k为i在二进制下末尾0的个数。当我们改变一个a[i]时，会有很多c[i]随之改变；若需查询某个s[i]，需要累加多个c[i]。好在确定需要改变或累加的元素都可以用比较简便的方法得出，这方法的核心就是lowbit值。 定义lowbit(x)=x&(x^(x-1))，它相当于将最右边的1左边的东西全部去掉。若需改变a[i]，则c[i]、c[i+lowbit(i)]、c[i+lowbit(i)+lowbit(i+lowbit(i)]……就是需要改变的c数组中的元素。若需查询s[i]，则c[i]、c[i-lowbit(i)]、c[i-lowbit(i)-lowbit(i-lowbit(i))]……就是需要累加的c数组中的元素。这看上去有些玄妙，我觉得其实也可以不用透彻理解。 一维的树状数组的每个操作的复杂度都是O(logn)的，非常高效。它可以扩充为n维，这样每个操作的复杂度就变成了O((logn)^n)，在n不大的时候仍然完全可以接受。扩充的方法就是将原来改变和查询的函数中的一个循环改成嵌套的n个循环在n维的c数组中操作。 要注意树状树组能处理的是下标为1..n的数组，绝对不能出现下标为0的情况。因为lowbit(0)=0，这样会陷入死循环。对于我这个从来都用C语言思考的家伙来说，这一点格外需要注意。 似乎树状数组也可以用来解决一些与前缀和关联不大的问题，例如NOI2004的cashier，但我还不太会（那题我只会用平衡树或线段树或虚二叉树解）。 示例程序：ural1470.cpp（三维的树状数组）
Wednesday, April 18, 2007
收缩有向图中的强连通分量大约是图论的线性算法中最具技巧性一种了。我们的首要目的是对于每个顶点设定一个Belong值，也就是它从属于哪个顶点所代表的强连通分量，至于重新建立图的边，不过是将所有边扫描一遍看是否在新图中出现而已，比较容易。 下面是利用一遍DFS求强连通分量的方法：对于每个顶点，设立Num、Low、Used、Alive四个属性，一个Stack保存当前正在被遍历的顶点；每访问一个顶点，将它的Num和Low设立为当前时间戳，Used、Alive设为True，并将顶点入栈，对于它的每条边，若边的终点未Used，则访问，而后用终点的Low值更新它的Low值，对于每个Used且Alive的终点，用它的Num值更新当前值；访问完毕当前顶点后，若Low与Num相等，说明找到了一个强连通分量，它包括栈中所有在当前顶点上方的顶点，将它们出栈并记下Belong值，出栈的顶点的Alive要置为false。 注意这里的Low值与求割顶和桥时的Low值的定义不太相同，它是与当前顶点双连通的最低顶点，所以才要用Alive来标记是否能到达当前顶点。 示例程序：cow.cpp （HAOI 2006 cow）