POJ 2761 Feed the dogs

• 数据结构测试题，以下方法可做：
• Binary Indexed Tree
• Segment Tree
• BST
• Splay Tree
• Treap
• AVL Tree
• SBT
• Red-Black Tree
• Partition Tree
• Leftist Tree
• ……

  对比实验

  • 都采用最朴素的实现，未使用模板。
  • 大括号占一行且不省略大括号。

    数据结构	时间	空间	代码行数	代码长度
    Binary Search Tree	TLE	No Data	248	7497B
    Segment Tree	3844MS	5376K	168	3437B
    Splay Tree	2766MS	3460K	276	7012B
    Adelson-Velskii and Landis' Tree	2422MS	3852K	271	6863B
    Treap	2125MS	3852K	246	6031B
    Size Balanced Tree	1969MS	3460K	325	8409B
    Binary Indexed Tree	1579MS	2684K	140	2731B

    代码实现

    Binary Search Tree

    • 区间排序，单点插入，单点删除。
    • 超时。

      Segment Tree

      • 离散化二分答案。

        Splay Tree

        • 区间排序，单点插入，单点删除。

          Adelson-Velskii and Landis' Tree

          • 区间排序，单点插入，单点删除。

            Treap

            • 区间排序，单点插入，单点删除。

              SBT

              • 区间排序，单点插入，单点删除。
              • 维护使用的是普通的维护，未加优化。

                Binary Indexed Tree

                • 离散化二分答案。