伸展树 Splay Tree

• 相比于线段树，Splay的优势在于可以动态的插入和删除、标记区间的翻转、与求空间第K大。由于记录的东西比较多，空间复杂度其实优势不太大。
• 相比于如AVL、Treap、SBT等自平衡的动态树，Splay的区间操作更容易。
• Splay本质上就是通过树的左旋和右旋将区间旋转到树的根节点的右孩子的左孩子处，通过zig-zig操作确保最新被查询的点总是接近根节点，再通过lazy进行区间的操作和询问。
• 为了保证上面条件通常需要加入左右边界，在对整个区间进行操作时，根节点就是左边界，根节点的右孩子就是右边界。
• 如果一次插入一整段区间，可以用二分递归的方法建树，是初始二叉树趋近于平衡。

  POJ 3468 A Simple Problem with Integers

  • 成段更新，求区间和。使用Splay的话需要lazy、添加、查询三种操作。
  • Splay代码长度是线段树的3倍左右。

    HDU 1754 I Hate It

    • 单点更新，求区间最大值。没什么需要注意的地方。

      POJ 2761 Feed the dog

      • 求区间第K小，Splay的一个重要应用。
      • 记录节点对应子树的数量，对询问区间排序后依次处理。
      • 通过二叉排序树的结构可以轻松的获得第K小元素，或找出当前点是第几小。
      • 其它解法
      • 样例演示

        HDU 1890 Robotic Sort

        • 涉及了区间的旋转操作，两次旋转可以抵消，用lazy记录是否旋转。

          HDU 3487 Play with Chain

          • 体现了两棵Splay树的合并。
          • CUT a b c，旋转出[a, b]区间删除，c旋转到根，c+1旋转到右子树，将[a, b]区间与c相连。
          • FLIP a b，翻转[a, b]区间，lazy标记。
          • 输出用中序遍历。

            POJ 3580 SuperMemo

            • 一共六种操作：
            • ADD x y D，将x到y区间加上D。
            • REVERSE x y，反转x到y区间。
            • REVOLVE x y T，将x到y区间循环右移T次，可以看做DELETE和INSERT的综合，两次区间操作。也可以看做三次区间旋转操作。
            • INSERT x P，在x位置后插入P。
            • DELETE x，删除x位置的数。
            • MIN x y，求x到y区间中的最小值。

              HDU 2475 Box

              • 每一个矩形相当于一个括号，记录起点和终点的下标。
              • 需要Splay的森林，每个根矩形建一棵Splay树。
              • 判断是否合法，将x的区间旋转出来，如果y的祖先中有x右端的左孩子则非法。
              • 插入，将y区间左端旋转出来，将x对应区间子树插入。
              • 找根，Splay树最小值就是根。

                BZOJ 1507 NOI2003 Editor

                • 乱搞。

                  SPOJ4487 Can you answer these queries VI

                  • 见GSS系列。