add BIT

2 files changed, 778 insertions, 0 deletions

diff --git a/meowpp/dsa/SplayTree_Range.h b/meowpp/dsa/SplayTree_Range.h
new file mode 100644
index 0000000..e5124c8
--- /dev/null
+++ b/meowpp/dsa/SplayTree_Range.h
@@ -0,0 +1,260 @@
+#ifndef   SplayTree_Range_h__
+#define   SplayTree_Range_h__
+
+#include "../utility.h"
+
+namespace meow{
+  //#
+  //#=== meow:: *SplayTree_Range<Key, Value>* (C++ class)
+  //#==== Description
+  //#  `SplayTree_Range` 是一種神乎其技的資料結構, 維護一堆 Key->Value. 並且支援
+  //#  一些 `std::map` 難以快速實踐的操作, 如 `split` , `merge` , `keyOffset`
+  //#
+  //#==== Template Class Operators Request
+  //#[options="header",width="70%",cols="1>m,1<,3<s,5<,3<,15<",grid="rows"]
+  //#|=====================================================================
+  //#|Const?|Typename| Operator| Parameters  | Return_Type| Description
+  //#|const |Key     |operator+|(Key    `k`) | Key        | 相加
+  //#|const |Key     |operator<|(Key    `k`) | bool       | 大小比較
+  //#|      |Key     |'Key'    |(int    `n`) |            | 建構子, `n` 永遠是0
+  //#|      |Value   | 'Value' |(          ) |            | 建構子
+  //#|=====================================================================
+  //#
+  template<class Key, class Value>
+  class SplayTree_Range{
+    private:
+      struct Node{
+        Key    _key;
+        Key    _keyOffset;
+        Value  _value;
+        Value  _valueOffset;
+        Value  _range;
+        bool   _same;
+        size_t _size;
+        Node*  _parent;
+        Node*  _child[2];
+        //
+        Node(Key const& __key, Value const& __value);
+        //
+        void keyOffset  (Key   const& __delta);
+        void valueUpdate(Value const& __delta, bool __over);
+        void syncDown() const;
+        void syncUp  () const;
+      };
+      //
+      Node* _root;
+      //
+      void        connect(Node const* __parent, size_t __left_right,
+                          Node const* __child) const;
+      Node const* splay  (Node const* __node) const;
+      //
+      void  clear(Node* __node);
+      Node*   dup(Node* __node);
+      //
+      Node const* findKey   (Node const* __node, Key const& __key    ) const;
+      Node const* findMinMax(Node const* __node, bool       __minimum) const;
+      Node const* findOrder (Node const* __node, size_t     __order  ) const;
+      //
+      void  split(Node* __root, Node** __left, Node** __right);
+      Node* merge(              Node*  __left, Node*  __right);
+      //
+      void print(Node* __now, int __depth) const;
+    public:
+      //#==== Custom Type Definitions
+      //#
+      //# * `Element` -> 用來當作回傳資料的媒介
+      //# ** 重定義 `operator->()` 到 `std::pair<Key const&, Value&>*` 
+      //# ** 重定義 `operator*()` 到 `std::pair<Key const&, Value&>&` 
+      //# ** 有 `operator==` , `operator!=`, `operator=` 可用
+      //# ** 可以直接用 `(*e).second = some_value` 來改變SplayTree_Range中的資料
+      //#
+      class Element{
+        private:
+          typedef std::pair<Key const&, Value&> Entry;
+          Entry* _entry;
+          Node * _node;
+          //
+          void reset(Node* __node);
+        public:
+          Element();
+          Element(Node* __node);
+          Element(Element const& __iterator2);
+          ~Element();
+          //
+          Element& operator=(Element const& __e2);
+          //
+          Entry* operator->();
+          Entry& operator *();
+          //
+          bool operator==(Element const& __e2) const;
+          bool operator!=(Element const& __e2) const;
+      };
+      //
+      SplayTree_Range();
+      SplayTree_Range(SplayTree_Range const& __tree2);
+      ~SplayTree_Range();
+      SplayTree_Range& operator=(SplayTree_Range const& __tree2);
+      //
+      //#==== Support Methods
+      //#
+      //# * N <- `this` 中擁有的資料數
+      //# * M <- `tree2` 中擁有的資料數
+      //#
+      //#[options="header",width="100%",cols="1>m,3>s,7<,3<,3^,20<",grid="rows"]
+      //#|=====================================================================
+      //#|Const?|Name | Parameters   | Return_Type| Time_Complexity| Description
+
+
+      //#||moveTo|(SplayTree_Range* `tree2`)|void|O(M)
+      //#|將 `this` 的資料複寫到 `tree2` 上面, 同時清空自己, 
+      //# 時間複雜度中的M是 `tree2` 所擁有的資料數
+      void moveTo(SplayTree_Range* __tree2);
+
+
+      //#|const|lowerBound|(Key const& `k`)|Element|O(logN)
+      //#|找出第一個(最小的) Element且 `k` <= 它的 Key, 並且回傳之.
+      //# 找不到的話回傳 `this->end()`
+      Element lowerBound(Key const& __key) const;
+
+
+      //#|const|lowerBound|(Key const& `k`)|Element|O(logN)
+      //#|找出第一個(最小的) Element且 `k` < 它的 Key, 並且回傳之.
+      //# 找不到的話回傳 `this->end()`
+      Element upperBound(Key const& __key) const;
+
+
+      //#|const|lowerBound|(Key const& `k`)|Element|O(logN)
+      //#|找出第一個(最小的) Element且 `k` >= 它的 Key, 並且回傳之.
+      //# 找不到的話回傳 `this->end()`
+      Element rLowerBound(Key const& __key) const;
+
+
+      //#|const|lowerBound|(Key const& `k`)|Element|O(logN)
+      //#|找出第一個(最小的) Element且 `k` > 它的 Key, 並且回傳之.
+      //# 找不到的話回傳 `this->end()`
+      Element rUpperBound(Key const& __key) const;
+
+
+      //#|const|find|(Key const& `k`)|Element|O(logN)
+      //#|找出 Key= `k` 的Elemenet 並回傳. 找不到的話回傳 `this->end()`
+      Element find(Key const& __key) const;
+      
+      
+      //#|const|query|()|Value|O(1)
+      //#|回傳整棵樹的區間Value
+      Value query() const;
+      
+      
+      //#|const|query|(Key const& `first` ,\Key const& `last`)|Value|O(logN)
+      //#|找出key介於 `first` \~ `last` 的區間Value
+      Value query(Key const& __first, Key const& __last) const;
+
+
+      //#|const|order|(size_t `ord`)|Element|O(logN)
+      //#|將Elements依照Key由小到大排序, 回傳第 `ord` 個Element (由0算起).
+      //# 其中如果 `ord` > N - 1, 則會回傳 `this->last()`
+      Element order(size_t __order) const;
+
+
+      //#|const|first|(size_t `ord`)|Element|O(logN)
+      //#|回傳Key最小的Element, 如果SplayTree_Range為空, 則回傳 `this->end()`
+      Element first() const;
+
+
+      //#|const|last|(size_t `ord`)|Element|O(logN)
+      //#|回傳Key最大的Element, 如果SplayTree_Range為空, 則回傳 `this->end()`
+      Element last() const;
+
+
+      //#|const|end|()|Element|O(1)
+      //#|回傳一個指向NULL的Element, 以供 `find` , `order` , `first`
+      //# , `last` 等判斷是否有找到相對應的Element
+      Element end() const;
+
+
+      //#|const|size|()|size_t|O(1)| 回傳資料數
+      size_t size() const;
+
+
+      //#|const|size|()|bool|O(1)| 回傳是否為空
+      bool empty() const;
+
+
+      //#||clear|()|void|O(N)| 清空資料
+      void clear();
+
+
+      //#||insert|(Key const& `key`,\Value const& `value`)|bool|O(logN)
+      //#|檢查是否已有Element的Key 為 `key`, 若有則回傳 `false` , 否則將
+      //# 一個 (Key -> Value) = (`key` -> `value`)的Element加入, 並回傳 `true`
+      //# 將所有Element的Key同加上 `delta`
+      bool insert(Key const& __key, Value const& __value);
+
+
+      //#||erase|(Key const& `key`)|bool|O(logN)
+      //#|檢查是否已有Element的Key 為 `key`, 若有則刪除之, 並回傳 `true`,
+      //# 否則則回傳 `false`
+      bool erase(Key const& __key);
+
+
+      //#||keyOffset|(Key const& `delta`)|void|O(1)
+      //#|將所有Element的Key同加上 `delta`
+      void keyOffset(Key const& __delta);
+      
+      
+      //#||valueOffset|(Value const& `delta`)|void|O(1)
+      //#|將所有Element的value同加上 `delta`
+      void valueOffset(Value const& __delta);
+      
+      
+      //#||valueOverride|(Value const& `vaule`)|void|O(1)
+      //#|將所有Element的value同變成 `value`
+      void valueOverride(Value const& __value);
+
+
+      //#||operator[]|(Key const& `key`)|Value&|O(logN)
+      //#|檢查是否已有Element的Key 為 `key`, 若有則回傳相對應的Value的Reference
+      //# 否則先執行 `insert(key, Value())` 再回傳相對應的Reference
+      Value& operator[](Key const& __key);
+
+
+      //#||splitOut|(Key const& `upper_bound`,\SplayTree_Range* `tree2`)|void
+      //#|O(logN) + O(M)
+      //#|將 `tree2` 清空, 再將所有Key > `upper_bound` 的Element都丟到 `tree2`
+      void splitOut(Key const& __upper_bound, SplayTree_Range* __right);
+
+
+      //#||mergeAfter|(SplayTree_Range* `tree2`)|void|O(logN) + O(logM)
+      //#|檢查是否 `this` 中的 Key 都小於 `tree2` 中的Key, 是的話把 `tree2` 
+      //# 中的 Element 都搬到 `this` , 同時清空 `tree2` , 回傳 `true`. 否則
+      //# 回傳 `false`
+      bool mergeAfter(SplayTree_Range* __tree2);
+
+
+      //#||merge|(SplayTree_Range* `tree2`)|void|O(logN) + O(logM)
+      //#|檢查是否 `this` 中的 Key 都小於 `tree2` 中的Key 或者
+      //# 是否 `this` 中的 Key 都大於 `tree2` 中的Key, 是的話把 `tree2` 
+      //# 中的 Element 都搬到 `this` , 同時清空 `tree2` , 回傳 `true`. 否則
+      //# 回傳 `false`
+      bool merge(SplayTree_Range* __tree2);
+
+
+      void print() const;
+      //#|=====================================================================
+  };
+  //#
+  //#[NOTE]
+  //#========================================
+  //# * 假設現在有兩個SplayTree_Range `A` 和 `B`,  則:
+  //# ** 執行 `B.moveTo(&A)` 後 `B` 會變成空的, `A` 原本擁有的資料也會覆蓋掉
+  //# ** 執行 `A.merge(&B)` 或 `A.mergeAfter(&B)` 後
+  //#    如果檢查發現確實可以merge, 則之後 `B` 會變成空的
+  //#========================================
+  //#
+  //# '''
+  //#
+}
+
+#include "SplayTree_Range.hpp"
+
+#endif // SplayTree_Range_h__
diff --git a/meowpp/dsa/SplayTree_Range.hpp b/meowpp/dsa/SplayTree_Range.hpp
new file mode 100644
index 0000000..1f216cf
--- /dev/null
+++ b/meowpp/dsa/SplayTree_Range.hpp
@@ -0,0 +1,518 @@
+
+namespace meow{
+  ///////////////////////////// **# Node #** /////////////////////////
+  //////////////////// **# Node -- Constructure #** //////////////////
+  template<class Key, class Value>
+  inline
+  SplayTree_Range<Key, Value>::Node::Node(Key const& __key,
+                                          Value const& __value):
+  _key(__key), _keyOffset(0), _value(__value), _valueOffset(0), _range(__value){
+    _same     = false;
+    _size     = 1;
+    _parent   = NULL;
+    _child[0] = NULL;
+    _child[1] = NULL;
+  }
+  ///////////////// **# Node -- Offset / Override #** ////////////////
+  template<class Key, class Value>
+  inline void
+  SplayTree_Range<Key, Value>::Node::keyOffset(Key const& __delta){
+    _key       = _key       + __delta;
+    _keyOffset = _keyOffset + __delta;
+  }
+  template<class Key, class Value>
+  inline void
+  SplayTree_Range<Key, Value>::Node::valueUpdate(Value const& __delta,
+                                                 bool __over){
+    if(__over){
+      _value       = __delta * _size;
+      _valueOffset = __delta;
+      _range       = __delta * _size;
+      _same = true;
+    }else{
+      _value       = _value       + __delta * _size;
+      _valueOffset = _valueOffset + __delta;
+      _range       = _range       + __delta * _size;
+    }
+  }
+  //////////////////////// **# Node -- sync #** //////////////////////
+  template<class Key, class Value>
+  inline void
+  SplayTree_Range<Key, Value>::Node::syncDown() const{
+    for(size_t i = 0; i < 2; i++){
+      if(_child[i] == NULL) continue;
+      _child[i]->keyOffset  (_keyOffset);
+      _child[i]->valueUpdate(_valueOffset, _same);
+    }
+    ((Node*)this)->_keyOffset   = Key(0);
+    ((Node*)this)->_valueOffset = Value(0);
+    ((Node*)this)->_same        = false;
+  }
+  template<class Key, class Value>
+  inline void
+  SplayTree_Range<Key, Value>::Node::syncUp() const{
+    ((Node*)this)->_size = 1;
+    Value* v[3] = {&(((Node*)this)->_value), NULL, NULL};
+    size_t vct = 1;
+    for(size_t i = 0; i < 2; i++){
+      if(_child[i] == NULL) continue;
+      ((Node*)this)->_size += _child[i]->_size;
+      v[vct++] = &(_child[i]->_range);
+    }
+    if     (vct == 1) ((Node*)this)->_range = (*v[0]);
+    else if(vct == 2) ((Node*)this)->_range = (*v[0]) | (*v[1]);
+    else              ((Node*)this)->_range = (*v[0]) | (*v[1]) | (*v[2]);
+  }
+  ////////////////////////// **# SplayTree_Range #** ///////////////////////
+  ///////////////////// **# connection, splay #** ////////////////////
+  template<class Key, class Value>
+  inline void
+  SplayTree_Range<Key, Value>::connect(Node const* __parent,
+                                       size_t __left_right,
+                                       Node const* __child) const{
+    Node* parent = (Node*)__parent;
+    Node* child  = (Node*)__child;
+    if(parent != NULL) parent->_child[__left_right] = child;
+    if(child  != NULL) child ->_parent              = parent;
+  }
+  template<class Key, class Value>
+  inline typename SplayTree_Range<Key, Value>::Node const*
+  SplayTree_Range<Key, Value>::splay(Node const* __node) const{
+    if(__node != NULL && __node->_parent != NULL){
+      for(const Node *g_grand, *grand, *parent, *child = __node; ; ){
+        g_grand = (grand = parent = child->_parent)->_parent;
+        size_t pc = (parent->_child[0] == child ? 0 : 1);
+        connect(parent,  pc, child->_child[!pc]);
+        connect(child , !pc, parent);
+        if(g_grand != NULL){
+          g_grand = (grand = g_grand)->_parent;
+          size_t gp = (grand->_child[0] == parent ? 0 : 1);
+          Node const* who = (pc == gp ? parent : child);
+          connect(grand,  gp, who->_child[!gp]);
+          connect(who  , !gp, grand);
+          grand->syncUp();
+        }
+        parent->syncUp();
+        child ->syncUp();
+        if(g_grand == NULL){
+          connect(NULL, 0, child);
+          break;
+        }
+        connect(g_grand, (g_grand->_child[0] == grand ?  0 : 1), child);
+      }
+    }
+    return (((SplayTree_Range*)this)->_root = (Node*)__node);
+  }
+  ///////////////////////// **# clear, dup #** ///////////////////////
+  template<class Key, class Value>
+  inline void
+  SplayTree_Range<Key, Value>::clear(Node* __node){
+    if(__node == NULL) return ;
+    clear(__node->_child[0]);
+    clear(__node->_child[1]);
+    delete __node;
+  }
+  template<class Key, class Value>
+  inline typename SplayTree_Range<Key, Value>::Node*
+  SplayTree_Range<Key, Value>::dup(Node* __node){
+    if(__node == NULL) return NULL;
+    __node->syncDown();
+    Node* node = new Node(__node->_key, __node->_value);
+    connect(node, 0, dup(__node->_child[0]));
+    connect(node, 1, dup(__node->_child[1]));
+    node->syncUp();
+    return node;
+  }
+  /////////////////////////// **# find #** ///////////////////////////
+  template<class Key, class Value>
+  inline typename SplayTree_Range<Key, Value>::Node const*
+  SplayTree_Range<Key, Value>::findKey(Node const* __node,
+                                       Key const& __key) const{
+    Node const* ret = __node;
+    while(__node != NULL){
+      __node->syncDown();
+      ret = __node;
+      if(!(__key < __node->_key)){
+        if(!(__node->_key< __key)) break;
+        __node = __node->_child[1];
+      }else{
+        __node = __node->_child[0];
+      }
+    }
+    return ret;
+  }
+  template<class Key, class Value>
+  inline typename SplayTree_Range<Key, Value>::Node const*
+  SplayTree_Range<Key, Value>::findMinMax(Node const* __node,
+                                          bool __minimum) const{
+    Node const* ret = __node;
+    for(int i = __minimum ? 0 : 1; __node != NULL; __node = __node->_child[i]){
+      __node->syncDown();
+      ret = __node;
+    }
+    return ret;
+  }
+  template<class Key, class Value>
+  inline typename SplayTree_Range<Key, Value>::Node const*
+  SplayTree_Range<Key, Value>::findOrder(Node const* __node,
+                                         size_t __order) const{
+    Node const* ret = __node;
+    while(__node != NULL){
+      __node->syncDown();
+      ret = __node;
+      size_t ord = 1 + (__node->_child[0]==NULL ? 0:__node->_child[0]->_size);
+      if     (ord == __order) return ret;
+      else if(ord <  __order){ __node = __node->_child[1]; __order -= ord; }
+      else                   { __node = __node->_child[0];                 }
+    }
+    return ret;
+  }
+  /////////////////////// **# split, merge #** ///////////////////////
+  template<class Key, class Value>
+  inline void
+  SplayTree_Range<Key, Value>::split(Node* __root, Node** __left,
+                                     Node** __right){
+    if(__root == NULL){ *__left  = NULL; *__right = NULL; return ; }
+    __root->syncDown();
+    *__left  = __root;
+    *__right = __root->_child[1];
+    if(*__right != NULL){
+      (*__left )->_child[1] = NULL;
+      (*__right)->_parent   = NULL;
+      (*__left )->syncUp();
+    }
+  }
+  template<class Key, class Value>
+  inline typename SplayTree_Range<Key, Value>::Node*
+  SplayTree_Range<Key, Value>::merge(Node* __left, Node* __right){
+    if(__left  == NULL) return __right;
+    if(__right == NULL) return __left ;
+    __left->syncDown();
+    connect(__left, 1, __right);
+    __left->syncUp();
+    return __left;
+  }
+  //
+  template<class Key, class Value>
+  inline void SplayTree_Range<Key, Value>::print(Node* __now,
+                                                 int __depth) const{
+    if(__now == NULL) return ;
+    printf("%*s [%llX]:(%lu)\tParent=%llX Left=%llX Right=%llX\n",
+           __depth * 2, "",
+           (long long unsigned)__now,
+           __now->_size,
+           (long long unsigned)__now->_parent,
+           (long long unsigned)__now->_child[0],
+           (long long unsigned)__now->_child[1]);
+    print(__now->_child[0], __depth + 1);
+    print(__now->_child[1], __depth + 1);
+  }
+  ///////////////////////// **# Element ##* //////////////////////////
+  template<class Key, class Value>
+  inline void SplayTree_Range<Key, Value>::Element::reset(Node* __node){
+    _node = __node;
+    delete _entry;
+    if(__node == NULL) _entry = NULL;
+    else               _entry = new Entry(__node->_key, __node->_value);
+  }
+  //
+  template<class Key, class Value>
+  inline
+  SplayTree_Range<Key, Value>::Element::Element():
+  _entry(NULL), _node(NULL){
+  }
+  template<class Key, class Value>
+  inline
+  SplayTree_Range<Key, Value>::Element::Element(Node* __node):
+  _entry(NULL), _node(NULL){
+    reset(__node);
+  }
+  template<class Key, class Value>
+  inline
+  SplayTree_Range<Key, Value>::Element::Element(Element const& __element2):
+  _entry(NULL), _node(NULL){
+    reset(__element2._node);
+  }
+  template<class Key, class Value>
+  inline
+  SplayTree_Range<Key, Value>::Element::~Element(){
+    delete _entry;
+  }
+  template<class Key, class Value>
+  inline typename SplayTree_Range<Key, Value>::Element&
+  SplayTree_Range<Key, Value>::Element::operator=(Element const& __e2){
+    reset(__e2._node);
+    return *this;
+  }
+  //////////////////// **# Element operations #** ////////////////////
+  template<class Key, class Value>
+  inline typename SplayTree_Range<Key, Value>::Element::Entry*
+  SplayTree_Range<Key, Value>::Element::operator->(){ return  _entry; }
+  template<class Key, class Value>
+  inline typename SplayTree_Range<Key, Value>::Element::Entry&
+  SplayTree_Range<Key, Value>::Element::operator*(){ return *_entry; }
+  //
+  template<class Key, class Value>
+  inline bool
+  SplayTree_Range<Key, Value>::Element::operator==(Element const& __e2) const{
+    return (_node == __e2._node);
+  }
+  template<class Key, class Value>
+  inline bool
+  SplayTree_Range<Key, Value>::Element::operator!=(Element const& __e2) const{
+    return (_node != __e2._node);
+  }
+  /////// **# Splay tree constructure/destructure/copy oper #** //////
+  template<class Key, class Value>
+  inline
+  SplayTree_Range<Key, Value>::SplayTree_Range(): _root(NULL){
+  }
+  template<class Key, class Value>
+  inline
+  SplayTree_Range<Key, Value>::SplayTree_Range(SplayTree_Range const& __tree2):
+  _root(NULL){
+    _root = dup((Node*)(__tree2._root));
+  }
+  template<class Key, class Value>
+  inline
+  SplayTree_Range<Key, Value>::~SplayTree_Range(){
+    clear(_root);
+  }
+  template<class Key, class Value>
+  inline SplayTree_Range<Key, Value>&
+  SplayTree_Range<Key, Value>::operator=(SplayTree_Range const& __tree2){
+    clear(_root);
+    _root = dup((Node*)(__tree2._root));
+    return *this;
+  }
+  template<class Key, class Value>
+  inline void
+  SplayTree_Range<Key, Value>::moveTo(SplayTree_Range* __tree2){
+    __tree2->clear();
+    __tree2->_root = _root;
+    _root = NULL;
+  }
+  //////////////////////// **# Bounding #** //////////////////////////
+  template<class Key, class Value>
+  inline typename SplayTree_Range<Key, Value>::Element
+  SplayTree_Range<Key, Value>::lowerBound(Key const& __key) const{
+    splay(findKey(_root, __key));
+    if(_root == NULL || !(_root->_key < __key)) return Element(_root);
+    if(_root->_child[1] == NULL) return Element(NULL);
+    splay(findMinMax(_root->_child[1], true));
+    return Element(_root);
+  }
+  template<class Key, class Value>
+  inline typename SplayTree_Range<Key, Value>::Element
+  SplayTree_Range<Key, Value>::upperBound(Key const& __key) const{
+    splay(findKey(_root, __key));
+    if(_root == NULL || __key < _root->_key) return Element(_root);
+    if(_root->_child[1] == NULL) return Element(NULL);
+    splay(findMinMax(_root->_child[1], true));
+    return Element(_root);
+  }
+  template<class Key, class Value>
+  inline typename SplayTree_Range<Key, Value>::Element
+  SplayTree_Range<Key, Value>::rLowerBound(Key const& __key) const{
+    splay(findKey(_root, __key));
+    if(_root == NULL || !(__key < _root->_key)) return Element(_root);
+    if(_root->_child[0] == NULL) return Element(NULL);
+    splay(findMinMax(_root->_child[0], false));
+    return Element(_root);
+  }
+  template<class Key, class Value>
+  inline typename SplayTree_Range<Key, Value>::Element
+  SplayTree_Range<Key, Value>::rUpperBound(Key const& __key) const{
+    splay(findKey(_root, __key));
+    if(_root == NULL || _root->_key < __key) return Element(_root);
+    if(_root->_child[0] == NULL) return Element(NULL);
+    splay(findMinMax(_root->_child[0], false));
+    return Element(_root);
+  }
+  ////////////// **# find / order / first / last / end #** ////////////
+  template<class Key, class Value>
+  inline typename SplayTree_Range<Key, Value>::Element
+  SplayTree_Range<Key, Value>::find(Key const& __key) const{
+    splay(findKey(_root, __key));
+    if(_root != NULL && !(__key < _root->_key) && !(_root->_key < __key)){
+      return Element(_root);
+    }
+    return Element(NULL);
+  }
+  template<class Key, class Value>
+  inline typename SplayTree_Range<Key, Value>::Element
+  SplayTree_Range<Key, Value>::order(size_t __order) const{
+    if(_root == NULL || __order >= _root->_size) return Element(NULL);
+    splay(findOrder(_root, __order + 1));
+    return Element(_root);
+  }
+  template<class Key, class Value>
+  inline typename SplayTree_Range<Key, Value>::Element
+  SplayTree_Range<Key, Value>::first() const{
+    splay(findMinMax(_root, true));
+    return Element(_root);
+  }
+  template<class Key, class Value>
+  inline typename SplayTree_Range<Key, Value>::Element
+  SplayTree_Range<Key, Value>::last() const{
+    splay(findMinMax(_root, false));
+    return Element(_root);
+  }
+  template<class Key, class Value>
+  inline typename SplayTree_Range<Key, Value>::Element
+  SplayTree_Range<Key, Value>::end() const{ return Element(NULL); }
+  //////////////////// **# query, range query #** ////////////////////
+  template<class Key, class Value>
+  inline Value
+  SplayTree_Range<Key, Value>::query() const{
+    if(_root == NULL) return Value(0);
+    return _root->_range;
+  }
+  template<class Key, class Value>
+  inline Value
+  SplayTree_Range<Key, Value>::query(Key const& __first,
+                                     Key const& __last) const{
+    SplayTree_Range* self = (SplayTree_Range*)this;
+    Node* tmp;
+    rUpperBound(__first);
+    self->split(self->_root, &tmp, &(self->_root));
+    upperBound(__last);
+    Value ret(0);
+    if(_root != NULL && _root->_child[0] != NULL){
+      ret = _root->_child[0]->_range;
+    }
+    self->_root = self->merge(tmp, self->_root);
+    return ret;
+  }
+  //////////////////// **# size, empty, clear #** ////////////////////
+  template<class Key, class Value>
+  inline size_t SplayTree_Range<Key, Value>::size() const{
+    return (_root == NULL ? 0 : _root->_size);
+  }
+  template<class Key, class Value>
+  inline bool SplayTree_Range<Key, Value>::empty() const{
+    return (size() == 0);
+  }
+  //
+  template<class Key, class Value>
+  inline void SplayTree_Range<Key, Value>::clear(){
+    clear(_root);
+    _root = NULL;
+  }
+  ////////////// **# insert, erase, keyOffset, oper[] #** ////////////
+  template<class Key, class Value>
+  inline bool SplayTree_Range<Key, Value>::insert(Key const& __key,
+                                                  Value const& __value){
+    if(_root == NULL){
+      _root = new Node(__key, __value);
+    }else{
+      Node* parent = (Node*)findKey(_root, __key);
+      if(!(parent->_key < __key) && !(__key < parent->_key)){
+        splay(parent);
+        return false;
+      }
+      Node* new_node = new Node(__key, __value);
+      connect(parent, (parent->_key < __key ? 1 : 0), new_node);
+      parent->syncUp();
+      splay(new_node);
+    }
+    return true;
+  }
+  template<class Key, class Value>
+  inline bool SplayTree_Range<Key, Value>::erase(Key const& __key){
+    if(_root == NULL) return false;
+    Node* body = (Node*)findKey(_root, __key);
+    if(body->_key < __key || __key < body->_key){
+      splay(body);
+      return false;
+    }
+    Node* ghost;
+    if(body->_child[1] == NULL){
+      ghost = body->_child[0];
+      if(ghost != NULL) ghost->syncDown();
+    }else{
+      ghost = (Node*)findMinMax(body->_child[1], true);
+      connect(ghost, 0, body->_child[0]);
+      if(ghost != body->_child[1]){
+        connect(ghost->_parent, 0, ghost->_child[1]);
+        connect(ghost, 1, body->_child[1]);
+        for(Node* a = ghost->_parent; a != ghost; a = a->_parent)
+          a->syncUp();
+      }
+      ghost->syncUp();
+    }
+    Node* parent = body->_parent;
+    connect(parent, parent != NULL && parent->_child[0] == body ? 0 : 1,
+            ghost);
+    delete body;
+    splay(ghost != NULL ? ghost : parent);
+    return true;
+  }
+  template<class Key, class Value>
+  inline void SplayTree_Range<Key, Value>::keyOffset(Key const& __delta){
+    if(_root != NULL){
+      _root->keyOffset(__delta);
+    }
+  }
+  template<class Key, class Value>
+  inline void SplayTree_Range<Key, Value>::valueOffset(Value const& __delta){
+    if(_root != NULL){
+      _root->valueUpdate(__delta, false);
+    }
+  }
+  template<class Key, class Value>
+  inline void SplayTree_Range<Key, Value>::valueOverride(Value const& __value){
+    if(_root != NULL){
+      _root->valueUpdate(__value, true);
+    }
+  }
+  template<class Key, class Value>
+  inline Value&
+  SplayTree_Range<Key, Value>::operator[](Key const& __key){
+    if(find(__key) == end()) insert(__key, Value());
+    return _root->_value;
+  }
+  /////////////////////// **# split, merge #** ///////////////////////
+  template<class Key, class Value>
+  inline void
+  SplayTree_Range<Key, Value>::splitOut(Key const& __upper_bound, SplayTree_Range* __right){
+    __right->clear();
+    if(rLowerBound(__upper_bound) != end()){
+      split(_root, &_root, &(__right->_root));
+    }else{
+      __right->_root = _root;
+      _root = NULL;
+    }
+  }
+  template<class Key, class Value>
+  inline bool
+  SplayTree_Range<Key, Value>::mergeAfter(SplayTree_Range* __tree2){
+    if(_root == NULL || __tree2->_root == NULL ||
+       last()->first < __tree2->first()->first){
+      _root = merge(_root, __tree2->_root);
+      __tree2->_root = NULL;
+      return true;
+    }
+    return false;
+  }
+  template<class Key, class Value>
+  inline bool
+  SplayTree_Range<Key, Value>::merge(SplayTree_Range* __tree2){
+    if(_root == NULL || __tree2->_root == NULL ||
+       last()->first < __tree2->first()->first){
+      _root = merge(_root, __tree2->_root);
+    }else if(__tree2->last()->first < first()->first){
+      _root = merge(__tree2->_root, _root);
+    }else{
+      return false;
+    }
+    __tree2->_root = NULL;
+    return true;
+  }
+  template<class Key, class Value>
+  inline void
+  SplayTree_Range<Key, Value>::print() const{
+    print(_root, 0);
+  }
+}
+