壓力測試完成~~~~~~~~~~

15 files changed, 659 insertions, 622 deletions

diff --git a/Makefile b/Makefile
index 7daa38c..e67d67a 100644
--- a/Makefile
+++ b/Makefile
@@ -6,7 +6,8 @@ ASCIIDOC_FLAGS = -a toc2 -a data-uri -a max-width=70em\
 		 -b html5 \
 		 --theme=volnitsky
 
-README = README.asciidoc
+README      = README.asciidoc
+README_HTML = README.html
 
 TEST  = _test
 TESTS = meowpp
@@ -17,14 +18,26 @@ all: $(TESTS)
 
 readme:
 	./readme_generate.py $(README)
-	$(ASCIIDOC) $(ASCIIDOC_FLAGS) $(README)
+	$(ASCIIDOC) $(ASCIIDOC_FLAGS) -o $(README_HTML) $(README)
+	
+$(TEST)/meowpp: $(TEST)/meowpp.o \
+	$(TEST)/meowpp_Colors.o \
+	$(TEST)/meowpp_DisjointSet.o \
+	$(TEST)/meowpp_KD_Tree.o \
+	$(TEST)/meowpp_SegmentTree.o \
+	$(TEST)/meowpp_MergeableHeap.o \
+	$(TEST)/meowpp_SplayTree.o \
 	
-$(TEST)/meowpp: $(TEST)/meowpp.cpp
 	$(CXX) -o $@ $(CXXFLAGS) $^
+	
+%.o: %.cpp
+	$(CXX) -c -o $@ $(CXXFLAGS) $^
 
 $(TESTS): %: $(TEST)/%
 	$^
 
 clean:
 	-rm -f $(foreach i,$(TESTS),$(TEST)/$i)
+	-rm -f $(TEST)/*.o
 	-rm -f $(README)
+	-rm -f $(README) $(README_HTML)
diff --git a/README.asciidoc b/README.asciidoc
index 3b3c9d7..d64ab13 100644
--- a/README.asciidoc
+++ b/README.asciidoc
@@ -155,7 +155,7 @@ approach this case by a simple way:
 * Let all the problem-solving classes inherit from
 `class ImplementInterface<T>` , and call the constructure with giving
 `identify` (type `T` ) .
-* Create an object, type `RegisterInterface<T>` , and register all your
+* Create an class inherit from `RegisterInterface<T>` , and register all your
 implement class to it by call `regImplement(pointer to the class)`.
 * Select which implement class you want by call `getImplement(identify)` ,
 which will return the pointer to the corresponding class.
@@ -226,34 +226,36 @@ you call `A.moveTo(&B)`
 
 '''
 
-=== meow:: *KD_Tree<Keys, Key, Value>* (C++ class)
+=== meow:: *KD_Tree<Vector, Scalar>* (C++ class)
 .Description
-`KD_Tree` is *K-dimension tree*, which is a dictionary(key->value).
-Where the type if key is a *K-dimension vector* .
+`KD_Tree` is *K-dimension tree*, which is a multiple set contain lots of
+vector with K dimension.
 
 .Template Request
-* `Keys` should has `operator[]` to allow the KD_Tree access the k-dimensions
-* `Key` should has `operator*`, `operator+`
+* `Vector` should has `operator[]` to allow the KD_Tree, `operator<` to
+compare when two vector are point to the same place, `operator==`
+access the k-dimensions
+* `Scalar` should has `operator*`, `operator+`, `operator<`
 
 .Support Methods
 * N <- numbers of element in the kd-tree
 * K <- dimensions
-* `Keys` is the tyepname of the vector
-* `Key` is the typename of the element in the vector
-* `Value` is the typename of value
+* `Vector` is the tyepname of the vector
+* `Vectors` is the typename of the std::vector<Vector>
 [options="header",width="100%",cols="1>,1<s,5<,1<,2<,10<",grid="rows"]
 |=======================================================================
 |Const?|Name| Parameters| Return Type| Time Complexity| Description
 |const|root|(size_t number)|size_t|very fast|
-||insert|(Key const& k, Value v)|void|O(1)|Insert a pair (k->v)
-|| build|()|void|O(KN logN) | Build the data structure(the `insert()` 
+||insert|(Vector const& v)|void|O(1)|Insert a vector
+||erase |(Vector const& v)|bool|O(N*x)| Find a vector which is the same
+as `v` and remove it from the KD_Tree, `x` in the Big-O time complex
+is cost by `Vector::operator==`.
+|| build|()|void|O(KN logN) if need | Build the data structure if need.
+|| forceBuild|()|void|O(KN logN) | Build the data structure(the `insert()` 
 method will not build the data structure immediately)
-|const|query|(Keys const& point, int k)|Value|O(kN ^1-1/k^ ) |
-Using Euclidean-Distance to find the k-nearest neighbor from `point` .
-And return the corrosponding value
-|const|query|(Keys const& point, int k)|std::vector<Value>|O(kN ^1-1/k^ ) |
-Using Euclidean-Distance to find all the x-nearest neighbor from `point` ,
-where x <= k. And return an array of all the corrosponding value.
+|const|query|(Vector const& v, int k)|Vectors|O(kN ^1-1/k^ ) |
+Using Euclidean-Distance to find the 1st to k-th nearest neighbor from `v` .
+And return;
 ||clear|()|O(1)|Clear all data
 ||reset|(size_t dimension)|O(1)|Clear all data and then
 set the this->dimension be `dimension`
diff --git a/README.html b/README.html
index 4e6b65d..e629055 100644
--- a/README.html
+++ b/README.html
@@ -1075,7 +1075,7 @@ Let all the problem-solving classes inherit from
 </li>

 <li>

 <p>

-Create an object, type <span class="monospaced">RegisterInterface&lt;T&gt;</span> , and register all your

+Create an class inherit from <span class="monospaced">RegisterInterface&lt;T&gt;</span> , and register all your

 implement class to it by call <span class="monospaced">regImplement(pointer to the class)</span>.

 </p>

 </li>

@@ -1291,18 +1291,20 @@ you call <span class="monospaced">A.moveTo(&amp;B)</span></td>
 <hr>

 </div>

 <div class="sect2">

-<h3 id="_meow_strong_kd_tree_lt_keys_key_value_gt_strong_c_class">meow:: <strong>KD_Tree&lt;Keys, Key, Value&gt;</strong> (C++ class)</h3>

-<div class="paragraph"><div class="title">Description</div><p><span class="monospaced">KD_Tree</span> is <strong>K-dimension tree</strong>, which is a dictionary(key&#8594;value).

-Where the type if key is a <strong>K-dimension vector</strong> .</p></div>

+<h3 id="_meow_strong_kd_tree_lt_vector_scalar_gt_strong_c_class">meow:: <strong>KD_Tree&lt;Vector, Scalar&gt;</strong> (C++ class)</h3>

+<div class="paragraph"><div class="title">Description</div><p><span class="monospaced">KD_Tree</span> is <strong>K-dimension tree</strong>, which is a multiple set contain lots of

+vector with K dimension.</p></div>

 <div class="ulist"><div class="title">Template Request</div><ul>

 <li>

 <p>

-<span class="monospaced">Keys</span> should has <span class="monospaced">operator[]</span> to allow the KD_Tree access the k-dimensions

+<span class="monospaced">Vector</span> should has <span class="monospaced">operator[]</span> to allow the KD_Tree, <span class="monospaced">operator&lt;</span> to

+compare when two vector are point to the same place, <span class="monospaced">operator==</span>

+access the k-dimensions

 </p>

 </li>

 <li>

 <p>

-<span class="monospaced">Key</span> should has <span class="monospaced">operator*</span>, <span class="monospaced">operator+</span>

+<span class="monospaced">Scalar</span> should has <span class="monospaced">operator*</span>, <span class="monospaced">operator+</span>, <span class="monospaced">operator&lt;</span>

 </p>

 </li>

 </ul></div>

@@ -1319,17 +1321,12 @@ K &#8592; dimensions
 </li>

 <li>

 <p>

-<span class="monospaced">Keys</span> is the tyepname of the vector

+<span class="monospaced">Vector</span> is the tyepname of the vector

 </p>

 </li>

 <li>

 <p>

-<span class="monospaced">Key</span> is the typename of the element in the vector

-</p>

-</li>

-<li>

-<p>

-<span class="monospaced">Value</span> is the typename of value

+<span class="monospaced">Vectors</span> is the typename of the std::vector&lt;Vector&gt;

 </p>

 </li>

 </ul></div>

@@ -1365,16 +1362,34 @@ width:100%;
 <tr>

 <td class="tableblock halign-right valign-top" ><p class="tableblock"></p></td>

 <td class="tableblock halign-left valign-top" ><p class="tableblock"><strong>insert</strong></p></td>

-<td class="tableblock halign-left valign-top" ><p class="tableblock">(Key const&amp; k, Value v)</p></td>

+<td class="tableblock halign-left valign-top" ><p class="tableblock">(Vector const&amp; v)</p></td>

 <td class="tableblock halign-left valign-top" ><p class="tableblock">void</p></td>

 <td class="tableblock halign-left valign-top" ><p class="tableblock">O(1)</p></td>

-<td class="tableblock halign-left valign-top" ><p class="tableblock">Insert a pair (k&#8594;v)</p></td>

+<td class="tableblock halign-left valign-top" ><p class="tableblock">Insert a vector</p></td>

+</tr>

+<tr>

+<td class="tableblock halign-right valign-top" ><p class="tableblock"></p></td>

+<td class="tableblock halign-left valign-top" ><p class="tableblock"><strong>erase</strong></p></td>

+<td class="tableblock halign-left valign-top" ><p class="tableblock">(Vector const&amp; v)</p></td>

+<td class="tableblock halign-left valign-top" ><p class="tableblock">bool</p></td>

+<td class="tableblock halign-left valign-top" ><p class="tableblock">O(N*x)</p></td>

+<td class="tableblock halign-left valign-top" ><p class="tableblock">Find a vector which is the same

+as <span class="monospaced">v</span> and remove it from the KD_Tree, <span class="monospaced">x</span> in the Big-O time complex

+is cost by <span class="monospaced">Vector::operator==</span>.</p></td>

 </tr>

 <tr>

 <td class="tableblock halign-right valign-top" ><p class="tableblock"></p></td>

 <td class="tableblock halign-left valign-top" ><p class="tableblock"><strong>build</strong></p></td>

 <td class="tableblock halign-left valign-top" ><p class="tableblock">()</p></td>

 <td class="tableblock halign-left valign-top" ><p class="tableblock">void</p></td>

+<td class="tableblock halign-left valign-top" ><p class="tableblock">O(KN logN) if need</p></td>

+<td class="tableblock halign-left valign-top" ><p class="tableblock">Build the data structure if need.</p></td>

+</tr>

+<tr>

+<td class="tableblock halign-right valign-top" ><p class="tableblock"></p></td>

+<td class="tableblock halign-left valign-top" ><p class="tableblock"><strong>forceBuild</strong></p></td>

+<td class="tableblock halign-left valign-top" ><p class="tableblock">()</p></td>

+<td class="tableblock halign-left valign-top" ><p class="tableblock">void</p></td>

 <td class="tableblock halign-left valign-top" ><p class="tableblock">O(KN logN)</p></td>

 <td class="tableblock halign-left valign-top" ><p class="tableblock">Build the data structure(the <span class="monospaced">insert()</span>

 method will not build the data structure immediately)</p></td>

@@ -1382,20 +1397,11 @@ method will not build the data structure immediately)</p></td>
 <tr>

 <td class="tableblock halign-right valign-top" ><p class="tableblock">const</p></td>

 <td class="tableblock halign-left valign-top" ><p class="tableblock"><strong>query</strong></p></td>

-<td class="tableblock halign-left valign-top" ><p class="tableblock">(Keys const&amp; point, int k)</p></td>

-<td class="tableblock halign-left valign-top" ><p class="tableblock">Value</p></td>

-<td class="tableblock halign-left valign-top" ><p class="tableblock">O(kN <sup>1-1/k</sup> )</p></td>

-<td class="tableblock halign-left valign-top" ><p class="tableblock">Using Euclidean-Distance to find the k-nearest neighbor from <span class="monospaced">point</span> .

-And return the corrosponding value</p></td>

-</tr>

-<tr>

-<td class="tableblock halign-right valign-top" ><p class="tableblock">const</p></td>

-<td class="tableblock halign-left valign-top" ><p class="tableblock"><strong>query</strong></p></td>

-<td class="tableblock halign-left valign-top" ><p class="tableblock">(Keys const&amp; point, int k)</p></td>

-<td class="tableblock halign-left valign-top" ><p class="tableblock">std::vector&lt;Value&gt;</p></td>

+<td class="tableblock halign-left valign-top" ><p class="tableblock">(Vector const&amp; v, int k)</p></td>

+<td class="tableblock halign-left valign-top" ><p class="tableblock">Vectors</p></td>

 <td class="tableblock halign-left valign-top" ><p class="tableblock">O(kN <sup>1-1/k</sup> )</p></td>

-<td class="tableblock halign-left valign-top" ><p class="tableblock">Using Euclidean-Distance to find all the x-nearest neighbor from <span class="monospaced">point</span> ,

-where x &#8656; k. And return an array of all the corrosponding value.</p></td>

+<td class="tableblock halign-left valign-top" ><p class="tableblock">Using Euclidean-Distance to find the 1st to k-th nearest neighbor from <span class="monospaced">v</span> .

+And return;</p></td>

 </tr>

 <tr>

 <td class="tableblock halign-right valign-top" ><p class="tableblock"></p></td>

@@ -1838,7 +1844,7 @@ plus <span class="monospaced">__value</span></p></td>
 <div id="footnotes"><hr></div>

 <div id="footer">

 <div id="footer-text">

-Last updated 2014-04-19 23:38:26 CST

+Last updated 2014-04-21 14:11:29 CST

 </div>

 </div>

 </body>

diff --git a/_test/.gitignore b/_test/.gitignore
index 1839056..4395672 100644
--- a/_test/.gitignore
+++ b/_test/.gitignore
@@ -1 +1,2 @@
 meowpp
+*.o
diff --git a/meowpp/Usage.hpp b/meowpp/Usage.hpp
index 40b933f..02f912b 100644
--- a/meowpp/Usage.hpp
+++ b/meowpp/Usage.hpp
@@ -174,11 +174,8 @@ namespace meow{
     description = stringReplace(d, "<value>", v);
   }
   inline Usage::String Usage::Value::getUsage() const {
-    if(description.length() > 0)
-      return stringPrintf("%8s%s : %s\n",
-                          " ", value.c_str(), description.c_str());
-    else
-      return "";
+    return stringPrintf("%8s%s : %s\n",
+                        " ", value.c_str(), description.c_str());
   }
   inline Usage::String Usage::Value::getValue() const {
     return value;
diff --git a/meowpp/colors/RGB.hpp b/meowpp/colors/RGB.hpp
index c2fd599..b5786f4 100644
--- a/meowpp/colors/RGB.hpp
+++ b/meowpp/colors/RGB.hpp
@@ -1,5 +1,4 @@
 #include <algorithm>
-#include <cstdint>
 
 namespace meow{
   template<class T>
diff --git a/meowpp/dsa/KD_Tree.h b/meowpp/dsa/KD_Tree.h
index 2e55d12..2ba81a1 100644
--- a/meowpp/dsa/KD_Tree.h
+++ b/meowpp/dsa/KD_Tree.h
@@ -4,100 +4,120 @@
 #include <list>
 #include <vector>
 #include <cstdlib>
+#include <queue>
+#include <utility.h>
 
 namespace meow{
-  template<class Keys, class Key, class Value>
+  template<class Vector, class Scalar>
   class KD_Tree{
     private:
       struct Node{
-        Keys    key;
-        Value   value;
-        ssize_t lChild;
-        ssize_t rChild;
-        Node(Keys _key, Value _value, ssize_t _l_child, ssize_t _r_child);
+        Vector  _vector;
+        ssize_t _lChild;
+        ssize_t _rChild;
+        //
+        Node(Vector __vector, ssize_t __lChild, ssize_t __rChild);
       };
       typedef std::vector<Node> Nodes;
+      //
       class Sorter{
         private:
-          Nodes const& nodes;
-          size_t       cmp;
+          Nodes const* _nodes;
+          size_t       _cmp;
         public:
-          Sorter(Nodes const& _nodes, size_t _cmp);
-          bool operator()(size_t const& a, size_t const& b) const;
+          Sorter(Nodes const* __nodes, size_t __cmp);
+          bool operator()(size_t const& __a, size_t const& __b) const;
       };
-      typedef std::vector<Value> Values;
       struct Answer{
-        Node const& node;
-        Key         dist2;
-        Answer(Node const& _node, Key _dist2);
-        bool operator<(Answer const& b) const;
+        ssize_t _index;
+        Scalar  _dist2;
+        //
+        Answer(ssize_t __index, Scalar __dist2);
+        Answer(Answer const& __answer2);
+      };
+      class AnswerCompare{
+        private:
+          Nodes const* _nodes;
+          bool         _cmpValue;
+        public:
+          AnswerCompare(Nodes const* __nodes, bool __cmpValue);
+          bool operator()(Answer const& __a, Answer const& __b) const;
       };
-      typedef typename std::list<Answer>    AnswerList;
-      typedef typename AnswerList::iterator AnswerListIterator;
+      typedef std::vector<Answer> AnswerV;
+      typedef std::priority_queue<Answer, AnswerV, AnswerCompare> Answers;
       //
-      const ssize_t NIL;
+      const ssize_t _NIL;
       //
-      Nodes  nodes;
-      size_t root;
-      bool   needRebuild;
-      size_t dimension;
+      Nodes  _nodes;
+      size_t _root;
+      bool   _needRebuild;
+      size_t _dimension;
       //
-      Key distance2(Keys const& k1, Keys const& k2) const;
-      size_t query(Keys const& key,
-                   size_t k,
-                   size_t index,
-                   int depth,
-                   std::vector<Key>& dist2_v,
-                   Key               dist2_s,
-                   AnswerList* ret) const;
-      ssize_t build(ssize_t beg,
-                    ssize_t end,
-                    std::vector<size_t>* orders,
-                    int depth);
+      Scalar distance2(Vector const& __v1, Vector const& __v2) const;
+      //
+      void query(Vector const&        __vector,
+                 size_t               __nearestNumber,
+                 AnswerCompare const& __answerCompare,
+                 size_t               __index,
+                 int                  __depth,
+                 std::vector<Scalar>& __dist2Vector,
+                 Scalar               __dist2Minimum,
+                 Answers             *__out) const;
+      ssize_t build(ssize_t              __beg,
+                    ssize_t              __end,
+                    std::vector<size_t>* __orders,
+                    int                  __depth);
     public:
+      typedef typename std::vector<Vector> Vectors;
+      //
       KD_Tree();
-      KD_Tree(size_t _dimension);
+      KD_Tree(size_t __dimension);
       ~KD_Tree();
       //
-      void   insert(Keys const& key, Value value);
-      void   build();
+      void insert(Vector const& __vector);
+      bool erase (Vector const& __vector);
+      void build();
+      void forceBuild();
       //
-      Value  query     (Keys const& point, int k) const;
-      Values rangeQuery(Keys const& point, int k) const;
+      Vectors query(Vector const& __vector,
+                    size_t        __nearestNumber,
+                    bool          __compareWholeVector) const;
       //
-      void   clear();
-      void   reset(size_t _dimension);
+      void clear();
+      void reset(size_t __dimension);
   };
   /*********************************************************
     @asciidoc
-    === meow:: *KD_Tree<Keys, Key, Value>* (C++ class)
+    === meow:: *KD_Tree<Vector, Scalar>* (C++ class)
     .Description
-    `KD_Tree` is *K-dimension tree*, which is a dictionary(key->value).
-    Where the type if key is a *K-dimension vector* .
-    
-   .Template Request
-   * `Keys` should has `operator[]` to allow the KD_Tree access the k-dimensions
-   * `Key` should has `operator*`, `operator+`
-    
-    .Support Methods
-    * N <- numbers of element in the kd-tree
-    * K <- dimensions
-    * `Keys` is the tyepname of the vector
-    * `Key` is the typename of the element in the vector
-    * `Value` is the typename of value
+    `KD_Tree` is *K-dimension tree*, which is a multiple set contain lots of
+    vector with K dimension.
+
+    .Template Request
+   * `Vector` should has `operator[]` to allow the KD_Tree, `operator<` to
+   compare when two vector are point to the same place, `operator==`
+   access the k-dimensions
+   * `Scalar` should has `operator*`, `operator+`, `operator<`
+
+   .Support Methods
+   * N <- numbers of element in the kd-tree
+   * K <- dimensions
+   * `Vector` is the tyepname of the vector
+   * `Vectors` is the typename of the std::vector<Vector>
    [options="header",width="100%",cols="1>,1<s,5<,1<,2<,10<",grid="rows"]
    |=======================================================================
    |Const?|Name| Parameters| Return Type| Time Complexity| Description
    |const|root|(size_t number)|size_t|very fast|
-   ||insert|(Key const& k, Value v)|void|O(1)|Insert a pair (k->v)
-   || build|()|void|O(KN logN) | Build the data structure(the `insert()` 
+   ||insert|(Vector const& v)|void|O(1)|Insert a vector
+   ||erase |(Vector const& v)|bool|O(N*x)| Find a vector which is the same
+   as `v` and remove it from the KD_Tree, `x` in the Big-O time complex
+   is cost by `Vector::operator==`.
+   || build|()|void|O(KN logN) if need | Build the data structure if need.
+   || forceBuild|()|void|O(KN logN) | Build the data structure(the `insert()` 
    method will not build the data structure immediately)
-   |const|query|(Keys const& point, int k)|Value|O(kN ^1-1/k^ ) |
-   Using Euclidean-Distance to find the k-nearest neighbor from `point` .
-   And return the corrosponding value
-   |const|query|(Keys const& point, int k)|std::vector<Value>|O(kN ^1-1/k^ ) |
-   Using Euclidean-Distance to find all the x-nearest neighbor from `point` ,
-   where x <= k. And return an array of all the corrosponding value.
+   |const|query|(Vector const& v, int k)|Vectors|O(kN ^1-1/k^ ) |
+   Using Euclidean-Distance to find the 1st to k-th nearest neighbor from `v` .
+   And return;
    ||clear|()|O(1)|Clear all data
    ||reset|(size_t dimension)|O(1)|Clear all data and then
    set the this->dimension be `dimension`
diff --git a/meowpp/dsa/KD_Tree.hpp b/meowpp/dsa/KD_Tree.hpp
index ac9f868..f0e97a9 100644
--- a/meowpp/dsa/KD_Tree.hpp
+++ b/meowpp/dsa/KD_Tree.hpp
@@ -2,196 +2,266 @@
 #include <list>
 #include <vector>
 #include <algorithm>
-#include <set>
-#include "utility.h"
+#include <queue>
+#include "../utility.h"
 
 namespace meow{
-  template<class Keys, class Key, class Value>
-  inline KD_Tree<Keys,Key,Value>::Node::Node(Keys _key,
-                                             Value _value,
-                                             ssize_t _l_child,
-                                             ssize_t _r_child):
-  key(_key), value(_value), lChild(_l_child), rChild(_r_child){ }
-  //
-  template<class Keys, class Key, class Value>
-  inline KD_Tree<Keys, Key, Value>::Sorter::Sorter(KD_Tree::Nodes const& _nodes,
-                                                   size_t _cmp):
-  nodes(_nodes), cmp(_cmp){ }
-  template<class Keys, class Key, class Value>
+  ////////////////////////////////////////////////////////////////////
+  //                          **# Node #**                          //
+  ////////////////////////////////////////////////////////////////////
+  template<class Vector, class Scalar>
+  inline
+  KD_Tree<Vector, Scalar>::Node::Node(Vector __vector,
+                                      ssize_t __lChild, ssize_t __rChild):
+  _vector(__vector), _lChild(__lChild), _rChild(__rChild){
+  }
+  ////////////////////////////////////////////////////////////////////
+  //                         **# Sorter #**                         //
+  ////////////////////////////////////////////////////////////////////
+  template<class Vector, class Scalar>
+  inline
+  KD_Tree<Vector, Scalar>::Sorter::Sorter(Nodes const* __nodes, size_t __cmp):
+  _nodes(__nodes), _cmp(__cmp){
+  }
+  template<class Vector, class Scalar>
   inline bool
-  KD_Tree<Keys, Key, Value>::Sorter::operator()(size_t const& a,
-                                                size_t const& b) const{
-    if(nodes[a].key[cmp] != nodes[b].key[cmp]){
-      return (nodes[a].key[cmp] < nodes[b].key[cmp]);
+  KD_Tree<Vector, Scalar>::Sorter::operator()(size_t const& __a,
+                                              size_t const& __b) const{
+    if((*_nodes)[__a]._vector[_cmp] != (*_nodes)[__b]._vector[_cmp]){
+      return ((*_nodes)[__a]._vector[_cmp] < (*_nodes)[__b]._vector[_cmp]);
     }
-    return (nodes[a].value < nodes[b].value);
+    return ((*_nodes)[__a]._vector < (*_nodes)[__b]._vector);
+  }
+  ////////////////////////////////////////////////////////////////////
+  //             **# Answer / Answer's Compare class #**            //
+  ////////////////////////////////////////////////////////////////////
+  template<class Vector, class Scalar>
+  inline
+  KD_Tree<Vector, Scalar>::Answer::Answer(ssize_t __index, Scalar __dist2):
+  _index(__index), _dist2(__dist2){
+  }
+  template<class Vector, class Scalar>
+  inline
+  KD_Tree<Vector, Scalar>::Answer::Answer(Answer const& __answer2):
+  _index(__answer2._index), _dist2(__answer2._dist2){
   }
   //
-  template<class Keys, class Key, class Value>
-  inline KD_Tree<Keys, Key, Value>::Answer::Answer(Node const& _node,
-                                                   Key _dist2):
-  node(_node), dist2(_dist2){ }
-  template<class Keys, class Key, class Value>
+  template<class Vector, class Scalar>
+  inline
+  KD_Tree<Vector, Scalar>::AnswerCompare::AnswerCompare(Nodes const* __nodes,
+                                                        bool __cmpValue):
+  _nodes(__nodes), _cmpValue(__cmpValue){
+  }
+  template<class Vector, class Scalar>
   inline bool
-  KD_Tree<Keys, Key, Value>::Answer::operator<(Answer const& b) const{
-    if(dist2 != b.dist2) return (dist2 < b.dist2);
-    return (node.value < b.node.value);
+  KD_Tree<Vector, Scalar>::AnswerCompare::operator()(Answer const& __a,
+                                                     Answer const& __b) const{
+    if(_cmpValue == true && __a._dist2 == __b._dist2){
+      return ((*_nodes)[__a._index]._vector < (*_nodes)[__b._index]._vector);
+    }
+    return (__a._dist2 < __b._dist2);
   }
-  //
-  template<class Keys, class Key, class Value>
-  inline Key KD_Tree<Keys, Key, Value>::distance2(Keys const& k1,
-                                                  Keys const& k2) const{
-    Key ret(0);
-    for(size_t i = 0; i < dimension; i++)
-      ret += squ(k1[i] - k2[i]);
+  ////////////////////////////////////////////////////////////////////
+  //                     **# distance2() #**                        //
+  ////////////////////////////////////////////////////////////////////
+  template<class Vector, class Scalar>
+  inline Scalar
+  KD_Tree<Vector, Scalar>::distance2(Vector const& __v1,
+                                     Vector const& __v2) const{
+    Scalar ret(0);
+    for(size_t i = 0; i < _dimension; i++){
+      ret += squ(__v1[i] - __v2[i]);
+    }
     return ret;
   }
-  template<class Keys, class Key, class Value>
-  inline size_t KD_Tree<Keys, Key, Value>::query(Keys const& key,
-                                                 size_t k,
-                                                 size_t index,
-                                                 int depth,
-                                                 std::vector<Key>& dist2_v,
-                                                 Key               dist2_s,
-                                                 KD_Tree::AnswerList* ret) const{
-    if(index == NIL){
-      return 0;
-    }
-    size_t cmp = depth % dimension;
-    ssize_t right_side, opposite, size;
-    ssize_t sz, other;
-    if(key[cmp] <= nodes[index].key[cmp]){
-      right_side = nodes[index].lChild;
-      opposite   = nodes[index].rChild;
+  ////////////////////////////////////////////////////////////////////
+  //                        **# query() #**                         //
+  ////////////////////////////////////////////////////////////////////
+  template<class Vector, class Scalar>
+  inline void
+  KD_Tree<Vector, Scalar>::query(Vector const& __vector,
+                                 size_t        __nearestNumber,
+                                 AnswerCompare const& __answerCompare,
+                                 size_t __index,
+                                 int    __depth,
+                                 std::vector<Scalar>& __dist2Vector,
+                                 Scalar               __dist2Minimum,
+                                 Answers *__out) const{
+    if(__index == _NIL) return ;
+    size_t cmp = __depth % _dimension;
+    ssize_t this_side, that_side;
+    if(!(_nodes[__index]._vector[cmp] < __vector[cmp])){
+      this_side = _nodes[__index]._lChild;
+      that_side = _nodes[__index]._rChild;
     }else{
-      right_side = nodes[index].rChild;
-      opposite   = nodes[index].lChild;
+      this_side = _nodes[__index]._rChild;
+      that_side = _nodes[__index]._lChild;
     }
-    size = query(key, k, right_side, depth + 1, dist2_v, dist2_s, ret);
-    Answer my_ans(nodes[index], distance2(nodes[index].key, key));
-    if(size < k || my_ans < *(ret->rbegin())){
-      KD_Tree::AnswerListIterator it = ret->begin();
-      while(it != ret->end() && !(my_ans < *it)) it++;
-      ret->insert(it, my_ans);
-      size++;
+    query(__vector, __nearestNumber, __answerCompare,
+          this_side, __depth + 1,
+          __dist2Vector, __dist2Minimum,
+          __out);
+    Answer my_ans(__index, distance2(_nodes[__index]._vector, __vector));
+    if(__out->size() < __nearestNumber ||
+       __answerCompare(my_ans, __out->top())){
+      __out->push(my_ans);
+      if(__out->size() > __nearestNumber) __out->pop();
     }
-    Key dist2_old = dist2_v[cmp];
-    dist2_v[cmp] = squ(nodes[index].key[cmp] - key[cmp]);
-    dist2_s     += dist2_v[cmp] - dist2_old;
-    if(size < k || (*(ret->rbegin())).dist2 >= dist2_s){
-      KD_Tree::AnswerList ret2;
-      size += query(key, k, opposite, depth + 1, dist2_v, dist2_s, &ret2);
-      KD_Tree::AnswerListIterator it1, it2;
-      for(it1 = ret->begin(), it2 = ret2.begin(); it2 != ret2.end(); it2++){
-        while(it1 != ret->end() && *it1 < *it2) it1++;
-        it1 = ++(ret->insert(it1, *it2));
-      }
+    Scalar dist2_old = __dist2Vector[cmp];
+    __dist2Vector[cmp] = squ(_nodes[__index]._vector[cmp] - __vector[cmp]);
+    Scalar dist2Minimum = __dist2Minimum + __dist2Vector[cmp] - dist2_old;
+    if(__out->size() < __nearestNumber ||
+       !(__out->top()._dist2 < dist2Minimum)){
+      query(__vector, __nearestNumber, __answerCompare,
+            that_side, __depth + 1,
+            __dist2Vector, dist2Minimum,
+            __out);
     }
-    if(size > k){
-      for(int i = size - k; i--; ){
-        ret->pop_back();
-      }
-      size = k;
-    }
-    dist2_v[cmp] = dist2_old;
-    return size;
-  }
-  template<class Keys, class Key, class Value>
-  inline ssize_t KD_Tree<Keys, Key, Value>::build(ssize_t beg,
-                                                  ssize_t end,
-                                                  std::vector<size_t>* orders,
-                                                  int depth){
-    if(beg > end){
-      return NIL;
+    __dist2Vector[cmp] = dist2_old;
+  }
+  ////////////////////////////////////////////////////////////////////
+  //                        **# build() #**                         //
+  ////////////////////////////////////////////////////////////////////
+  template<class Vector, class Scalar>
+  inline ssize_t
+  KD_Tree<Vector, Scalar>::build(ssize_t              __beg,
+                                 ssize_t              __end,
+                                 std::vector<size_t>* __orders,
+                                 int                  __depth){
+    if(__beg > __end) return _NIL;
+    size_t tmp_order  = _dimension;
+    size_t which_side = _dimension + 1;
+    ssize_t mid = (__beg + __end) / 2;
+    size_t  cmp = __depth % _dimension;
+    for(ssize_t i = __beg; i <= mid; i++){
+      __orders[which_side][__orders[cmp][i]] = 0;
     }
-    ssize_t mid = (beg + end) / 2;
-    size_t  cmp = depth % 2;
-    std::set<size_t> right;
-    for(ssize_t i = mid + 1; i <= end; i++){
-      right.insert(orders[cmp][i]);
+    for(ssize_t i = mid + 1; i <= __end; i++){
+      __orders[which_side][__orders[cmp][i]] = 1;
     }
-    for(int i = 0; i < dimension; i++){
+    for(int i = 0; i < _dimension; i++){
       if(i == cmp) continue;
-      size_t aa = beg, bb = mid + 1;
-      for(int j = beg; j <= end; j++){
-        if(orders[i][j] == orders[cmp][mid]){
-          orders[dimension][mid] = orders[i][j];
-        }else if(right.find(orders[i][j]) != right.end()){
-          orders[dimension][bb++] = orders[i][j];
+      size_t left = __beg, right = mid + 1;
+      for(int j = __beg; j <= __end; j++){
+        size_t ask = __orders[i][j];
+        if(ask == __orders[cmp][mid]){
+          __orders[tmp_order][mid] = ask;
+        }else if(__orders[which_side][ask] == 1){
+          __orders[tmp_order][right++] = ask;
         }else{
-          orders[dimension][aa++] = orders[i][j];
+          __orders[tmp_order][left++] = ask;
         }
       }
-      for(int j = beg; j <= end; j++){
-        orders[i][j] = orders[dimension][j];
+      for(int j = __beg; j <= __end; j++){
+        __orders[i][j] = __orders[tmp_order][j];
       }
     }
-    nodes[orders[cmp][mid]].lChild = build(beg, mid - 1, orders, depth + 1);
-    nodes[orders[cmp][mid]].rChild = build(mid + 1, end, orders, depth + 1);
-    return orders[cmp][mid];
-  }
-  template<class Keys, class Key, class Value>
-  inline KD_Tree<Keys, Key, Value>::KD_Tree():
-  NIL(-1), root(NIL), needRebuild(false), dimension(1){ }
-  template<class Keys, class Key, class Value>
-  inline KD_Tree<Keys, Key, Value>::KD_Tree(size_t _dimension):
-  NIL(-1), root(NIL), needRebuild(false), dimension(_dimension){ }
-  template<class Keys, class Key, class Value>
-  inline KD_Tree<Keys, Key, Value>::~KD_Tree(){ }
-  template<class Keys, class Key, class Value>
-  inline void KD_Tree<Keys, Key, Value>::insert(Keys const& key, Value value){
-    nodes.push_back(Node(key, value, NIL, NIL));
-    needRebuild = true;
-  }
-  template<class Keys, class Key, class Value>
-  inline void KD_Tree<Keys, Key, Value>::build(){
-    if(needRebuild){
-      std::vector<size_t> *orders = new std::vector<size_t>[dimension + 1];
-      for(int j = 0; j < dimension + 1; j++){
-        orders[j].resize(nodes.size());
-      }
-      for(int j = 0; j < dimension; j++){
-        for(size_t i = 0, I = nodes.size(); i < I; i++){
-          orders[j][i] = i;
+    _nodes[__orders[cmp][mid]]._lChild=build(__beg,mid-1,__orders,__depth+1);
+    _nodes[__orders[cmp][mid]]._rChild=build(mid+1,__end,__orders,__depth+1);
+    return __orders[cmp][mid];
+  }
+  ////////////////////////////////////////////////////////////////////
+  //             **# constructures/destructures #**                 //
+  ////////////////////////////////////////////////////////////////////
+  template<class Vector, class Scalar>
+  inline
+  KD_Tree<Vector, Scalar>::KD_Tree():
+  _NIL(-1), _root(_NIL), _needRebuild(false), _dimension(1){
+  }
+  template<class Vector, class Scalar>
+  inline
+  KD_Tree<Vector, Scalar>::KD_Tree(size_t __dimension):
+  _NIL(-1), _root(_NIL), _needRebuild(false), _dimension(__dimension){
+  }
+  template<class Vector, class Scalar>
+  inline
+  KD_Tree<Vector, Scalar>::~KD_Tree(){
+  }
+  ////////////////////////////////////////////////////////////////////
+  //                       **# insert, build #**                    //
+  ////////////////////////////////////////////////////////////////////
+  template<class Vector, class Scalar>
+  inline void
+  KD_Tree<Vector, Scalar>::insert(Vector const& __vector){
+    _nodes.push_back(Node(__vector, _NIL, _NIL));
+    _needRebuild = true;
+  }
+  template<class Vector, class Scalar>
+  inline bool
+  KD_Tree<Vector, Scalar>::erase(Vector const& __vector){
+    for(size_t i = 0, I = _nodes.size(); i < I; i++){
+      if(_nodes[i] == __vector){
+        if(i != I - 1){
+          std::swap(_nodes[i], _nodes[I - 1]);
         }
-        std::sort(orders[j].begin(), orders[j].end(), Sorter(nodes, j));
+        _needRebuild = true;
+        return true;
       }
-      root = build(0, (ssize_t)nodes.size() - 1, orders, 0);
-      needRebuild = false;
-      delete [] orders;
     }
+    return false;
   }
-  template<class Keys, class Key, class Value>
-  inline Value KD_Tree<Keys, Key, Value>::query(Keys const& point, int k) const{
-    ((KD_Tree*)this)->build();
-    KD_Tree::AnswerList ret;
-    std::vector<Key> tmp(dimension, Key(0));
-    query(point, k, root, 0, tmp, Key(0), &ret);
-    return (*(ret.rbegin())).node.value;
-  }
-  template<class Keys, class Key, class Value>
-  inline typename KD_Tree<Keys, Key, Value>::Values
-  KD_Tree<Keys, Key, Value>::rangeQuery(Keys const& point, int k) const{
+  template<class Vector, class Scalar>
+  inline void
+  KD_Tree<Vector, Scalar>::build(){
+    if(_needRebuild){
+      forceBuild();
+    }
+  }
+  template<class Vector, class Scalar>
+  inline void
+  KD_Tree<Vector, Scalar>::forceBuild(){
+    std::vector<size_t> *orders = new std::vector<size_t>[_dimension + 2];
+    for(int j = 0; j < _dimension + 2; j++){
+      orders[j].resize(_nodes.size());
+    }
+    for(int j = 0; j < _dimension; j++){
+      for(size_t i = 0, I = _nodes.size(); i < I; i++){
+        orders[j][i] = i;
+      }
+      std::sort(orders[j].begin(), orders[j].end(), Sorter(&_nodes, j));
+    }
+    _root = build(0, (ssize_t)_nodes.size() - 1, orders, 0);
+    delete [] orders;
+    _needRebuild = false;
+  }
+  ////////////////////////////////////////////////////////////////////
+  //                          **# query #**                         //
+  ////////////////////////////////////////////////////////////////////
+  template<class Vector, class Scalar>
+  inline typename KD_Tree<Vector, Scalar>::Vectors
+  KD_Tree<Vector, Scalar>::query(Vector const& __vector,
+                                 size_t        __nearestNumber,
+                                 bool          __compareWholeVector) const{
     ((KD_Tree*)this)->build();
-    KD_Tree::AnswerList ret;
-    std::vector<Key> tmp(dimension, Key(0));
-    query(point, k, root, 0, tmp, Key(0), &ret);
-    KD_Tree::Values ret_val(ret.size());
-    int i = 0;
-    for(KD_Tree::AnswerListIterator it = ret.begin(); it != ret.end(); it++){
-      ret_val[i++] = (*it).node.value;
+    AnswerCompare answer_compare(&_nodes, __compareWholeVector);
+    Answers       answer_set(answer_compare);
+    std::vector<Scalar> tmp(_dimension, 0);
+    query(__vector, __nearestNumber,
+          answer_compare,
+          _root, 0,
+          tmp, Scalar(0),
+          &answer_set);
+    Vectors ret(answer_set.size());
+    for(int i = (ssize_t)answer_set.size() - 1; i >= 0; i--){
+      ret[i] = _nodes[answer_set.top()._index]._vector;
+      answer_set.pop();
     }
-    return ret_val;
+    return ret;
   }
-  template<class Keys, class Key, class Value>
-  inline void KD_Tree<Keys, Key, Value>::clear(){
-    root = NIL;
-    nodes.clear();
-    needRebuild = false;
+  ////////////////////////////////////////////////////////////////////
+  //                       **# clear, reset #**                     //
+  ////////////////////////////////////////////////////////////////////
+  template<class Vector, class Scalar>
+  inline void
+  KD_Tree<Vector, Scalar>::clear(){
+    _root = _NIL;
+    _nodes.clear();
+    _needRebuild = false;
   }
-  template<class Keys, class Key, class Value>
-  inline void KD_Tree<Keys, Key, Value>::reset(size_t _dimension){
+  template<class Vector, class Scalar>
+  inline void
+  KD_Tree<Vector, Scalar>::reset(size_t __dimension){
     clear();
-    dimension = _dimension;
+    _dimension = __dimension;
   }
 }
diff --git a/meowpp/dsa/MergeableHeap.hpp b/meowpp/dsa/MergeableHeap.hpp
index 6e49a1c..be7dcea 100644
--- a/meowpp/dsa/MergeableHeap.hpp
+++ b/meowpp/dsa/MergeableHeap.hpp
@@ -5,16 +5,14 @@ namespace meow{
   //      **# MergeableHeap--Node-- constructor #**       //
   //////////////////////////////////////////////////////////
   template<class Element>
-  inline
-  MergeableHeap<Element>::Node::Node(Element const& _value):    // Node
+  inline MergeableHeap<Element>::Node::Node(Element const& _value): // Node
   value(_value), l_child(NULL), r_child(NULL), weight(1){ }
   
   //////////////////////////////////////////////////////////
   //      **# MergeableHeap -- clear, duplicate #**       //
   //////////////////////////////////////////////////////////
   template<class Element>
-  inline void
-  MergeableHeap<Element>::clear(Node* _node){                   //clear
+  inline void MergeableHeap<Element>::clear(Node* _node){           //clear
     if(_node != NULL){
       clear(_node->l_child);
       clear(_node->r_child);
@@ -59,18 +57,13 @@ namespace meow{
   //   **# MergeableHeap -- constrctors/destructors #**   //
   //////////////////////////////////////////////////////////
   template<class Element>
-  inline
-  MergeableHeap<Element>::MergeableHeap():              //MergeableHeap
+  inline MergeableHeap<Element>::MergeableHeap():       //MergeableHeap
   root(NULL){ }
   template<class Element>
-  inline
-  MergeableHeap<Element>::MergeableHeap(MergeableHeap const& _heap2):
-  root(NULL){
-    root = dup(_heap2.root);
-  }
+  inline MergeableHeap<Element>::MergeableHeap(MergeableHeap const& _heap2):
+  root(NULL){ root = dup(_heap2.root); }
   template<class Element>
-  inline
-  MergeableHeap<Element>::~MergeableHeap(){             //~MergeableHeap
+  inline MergeableHeap<Element>::~MergeableHeap(){      //~MergeableHeap
     clear(root);
   }
   
@@ -84,8 +77,7 @@ namespace meow{
     return *this;
   }
   template<class Element>
-  inline void
-  MergeableHeap<Element>::moveTo(MergeableHeap* _heap2){        // moveTo
+  inline void MergeableHeap<Element>::moveTo(MergeableHeap* _heap2){ // moveTo
     _heap2->clear();
     _heap2->root = root;
     root = NULL;
@@ -93,41 +85,30 @@ namespace meow{
   //////////////////////////////////////////////////////////
   //  **# MergeableHeap -- access: top, size, emtpy #**   //
   //////////////////////////////////////////////////////////
-  template<class Element>
-  inline Element const&
-  MergeableHeap<Element>::top() const{                          // top
-    return root->value;
-  }
-  template<class Element>
-  inline size_t
-  MergeableHeap<Element>::size() const{                         // size
+  template<class Element>                                   // top
+  inline Element const& MergeableHeap<Element>::top()const{return root->value;}
+  template<class Element>                                   // size
+  inline size_t MergeableHeap<Element>::size() const{
     return (root == NULL ? 0 : root->weight);
   }
-  template<class Element>
-  inline size_t
-  MergeableHeap<Element>::empty() const{                        // empty
-    return (size() == 0);
-  }
+  template<class Element>                                   // empty
+  inline size_t MergeableHeap<Element>::empty() const{ return (size() == 0); }
   //////////////////////////////////////////////////////////
   //  **# MergeableHeap -- update: push, pop, merge #**   //
   //////////////////////////////////////////////////////////
   template<class Element>
-  inline void
-  MergeableHeap<Element>::push(Element const& _value){          // push
-    Node* new_node = new Node(_value);
-    root = merge(root, new_node);
+  inline void MergeableHeap<Element>::push(Element const& _value){  // push
+    root = merge(root, new Node(_value));
   }
   template<class Element>
-  inline void
-  MergeableHeap<Element>::pop(){                                // pop
+  inline void MergeableHeap<Element>::pop(){                      // pop
     Node* l = root->l_child;
     Node* r = root->r_child;
     delete root;
     root = merge(l, r);
   }
   template<class Element>
-  inline void
-  MergeableHeap<Element>::merge(MergeableHeap* _heap2){         // merge
+  inline void MergeableHeap<Element>::merge(MergeableHeap* _heap2){ // merge
     root = merge(root, _heap2->root);
     _heap2->root = NULL;
   }
@@ -135,8 +116,7 @@ namespace meow{
   //      **# MergeableHeap -- refresh: clear #**         //
   //////////////////////////////////////////////////////////
   template<class Element>
-  inline void
-  MergeableHeap<Element>::clear(){                              // clear
+  inline void MergeableHeap<Element>::clear(){                // clear
     clear(root);
     root = NULL;
   }
diff --git a/meowpp/dsa/SegmentTree.h b/meowpp/dsa/SegmentTree.h
index 1aa396d..585ea5d 100644
--- a/meowpp/dsa/SegmentTree.h
+++ b/meowpp/dsa/SegmentTree.h
@@ -9,27 +9,19 @@ namespace meow{
         Value _value;
         Value _offset;
         bool  _sameFlag;
-        //
-        Node();
       };
       //
       size_t            _size;
       std::vector<Node> _nodes;
-      size_t const      _root;
       //
-      size_t  leftChild(size_t __parent) const;
-      size_t rightChild(size_t __parent) const;
-      //
-      void downUpdate(size_t __L, size_t __R, size_t __index);
-      void override(size_t __l, size_t __r,
-                    size_t __L, size_t __R,
-                    size_t __index, Value const& __value);
-      void offset(size_t __l, size_t __r,
-                  size_t __L, size_t __R,
-                  size_t __index, Value const& __delta);
-      Value query(size_t __l, size_t __r,
-                  size_t __L, size_t __R,
+      void update(size_t __index, size_t __size, Value const& __value,
+                  bool __override);
+      void update(size_t __l, size_t __r, size_t __L, size_t __R,
+                  size_t __index, Value const& __value,
+                  bool   __override);
+      Value query(size_t __l, size_t __r, size_t __L, size_t __R,
                   size_t __index);
+      //
       bool rangeCorrect(ssize_t* __first, ssize_t* __last) const;
     public:
       SegmentTree();
@@ -38,9 +30,28 @@ namespace meow{
       //
       void reset(size_t __size);
       //
-      Value query  (ssize_t __first, ssize_t __last) const;
-      void override(ssize_t __first, ssize_t __last, Value const& __value);
-      void offset  (ssize_t __first, ssize_t __last, Value const& __delta);
+      Value query   (ssize_t __first, ssize_t __last) const;
+      void  override(ssize_t __first, ssize_t __last, Value const& __value);
+      void  offset  (ssize_t __first, ssize_t __last, Value const& __delta);
+      void print(){
+        for(int i = 0; i < _size; i++){
+          query(i, i);
+        }
+        printf("\n");
+        for(int depth = 0, count = 1, size = _size, id = 0;
+            size > 0;
+            depth++, count *= 2, size /= 2){
+          for(int j = 0; j < count; j++, id++){
+            printf("[%3d%c%3d%*s]",
+                   _nodes[id]._value.value,
+                   _nodes[id]._sameFlag ? 's' : ' ',
+                   _nodes[id]._offset.value,
+                   size * 9 - 9,
+                   "");
+          }
+          printf("\n");
+        }
+      }
   };
   /*********************************************************
     @asciidoc
@@ -89,4 +100,6 @@ namespace meow{
    *********************************************************/
 }
 
+#include "SegmentTree.hpp"
+
 #endif
diff --git a/meowpp/dsa/SegmentTree.hpp b/meowpp/dsa/SegmentTree.hpp
index 24efcdd..a2b74e8 100644
--- a/meowpp/dsa/SegmentTree.hpp
+++ b/meowpp/dsa/SegmentTree.hpp
@@ -1,172 +1,111 @@
-#ifndef   SegmentTree_H__
-#define   SegmentTree_H__
+#include "../utility.h"
 
-namespace meow{
-  template<class Value>
-  inline SegmentTree<Value>::Node::Node(){ }
+#include <algorithm>
 
-  template<class Value>
-  inline size_t
-  SegmentTree<Value>::leftChild(size_t __parent) const {
-    return __parent * 2 + 1;
-  }
-  template<class Value>
-  inline size_t
-  SegmentTree<Value>::rightChild(size_t __parent) const {
-    return __parent * 2 + 2;
-  }
-
-  template<class Value>
-  inline void
-  SegmentTree<Value>::downUpdate(size_t __L, size_t __R, size_t __index){
-    size_t mid = (__L + __R) / 2;
-    Value& val = _nodes[__index]._value;
-    Value& off = _nodes[__index]._offset;
-    if(_nodes[__index]._sameFlag){
-      if(__L < __R){
-        override(__L    , mid, __L    , mid,  leftChild(__index), val);
-        override(mid + 1, __R, mid + 1, __R, rightChild(__index), val);
-      }
-      _nodes[__index]._sameFlag = false;
-      _nodes[__index]._offset = 0;
-    }else if(!(_nodes[__index]._offset == Value(0))){
-      if(__L < __R){
-        offset(__L    , mid, __L    , mid,  leftChild(__index), off);
-        offset(mid + 1, __R, mid + 1, __R, rightChild(__index), off);
-      }
-      _nodes[__index]._offset = 0;
-    }
-  }
+namespace meow{
+  
   template<class Value>
   inline void
-  SegmentTree<Value>::override(size_t __l, size_t __r,
-                               size_t __L, size_t __R,
-                               size_t __index, Value const& __value){
-    if(__l == __L && __r == __R){
-      _nodes[__index]._value    = __value * (__R - __L + 1);
-      _nodes[__index]._offset   = 0;
-      _nodes[__index]._sameFlag = true;
-      return ;
-    }
-    downUpdate(__L, __R, __index);
-    size_t mid = (__L + __R) / 2;
-    if(__r <= mid){
-      override(__l, __r, __L    , mid,  leftChild(__index), __value);
-    }else if(mid + 1 <= __l){
-      override(__l, __r, mid + 1, __R, rightChild(__index), __value);
+  SegmentTree<Value>::update(size_t __i, size_t __size, Value const& __value,
+                             bool __over){
+    if(__over){
+      _nodes[__i]._value    = __value * __size;
+      _nodes[__i]._offset   = __value;
+      _nodes[__i]._sameFlag = true;
     }else{
-      override(__l    , mid, __L    , mid,  leftChild(__index), __value);
-      override(mid + 1, __r, mid + 1, __R, rightChild(__index), __value);
+      _nodes[__i]._value  = _nodes[__i]._value  + __value * __size;
+      _nodes[__i]._offset = _nodes[__i]._offset + __value;
     }
-    _nodes[__index]._value = (  _nodes[ leftChild(__index)]._value
-                              | _nodes[rightChild(__index)]._value);
   }
   template<class Value>
   inline void
-  SegmentTree<Value>::offset(size_t __l, size_t __r,
-                             size_t __L, size_t __R,
-                             size_t __index, Value const& __delta){
+  SegmentTree<Value>::update(size_t __l, size_t __r, size_t __L, size_t __R,
+                             size_t __i, Value const& __value,
+                             bool   __over){
     if(__l == __L && __r == __R){
-      _nodes[__index]._value = _nodes[__index]._value + __delta*(__R-__L+1);
-      if(!_nodes[__index]._sameFlag){
-        _nodes[__index]._offset = _nodes[__index]._offset + __delta;
-      }
+      update(__i, __R - __L + 1, __value, __over);
       return ;
     }
-    downUpdate(__L, __R, __index);
     size_t mid = (__L + __R) / 2;
-    if(__r <= mid){
-      offset(__l, __r, __L    , mid,  leftChild(__index), __delta);
-    }else if(mid + 1 <= __l){
-      offset(__l, __r, mid + 1, __R, rightChild(__index), __delta);
-    }else{
-      offset(__l    , mid, __L    , mid,  leftChild(__index), __delta);
-      offset(mid + 1, __r, mid + 1, __R, rightChild(__index), __delta);
+    if(__L < __R){
+      update(__i*2+1, mid-__L+1, _nodes[__i]._offset, _nodes[__i]._sameFlag);
+      update(__i*2+2, __R - mid, _nodes[__i]._offset, _nodes[__i]._sameFlag);
+      _nodes[__i]._offset = Value(0);
+      _nodes[__i]._sameFlag = false;
+    }
+    if     (__r   <= mid) update(__l,__r, __L  ,mid, __i*2+1, __value, __over);
+    else if(mid+1 <= __l) update(__l,__r, mid+1,__R, __i*2+2, __value, __over);
+    else{
+      update(__l,mid       , __L,mid  ,      __i*2+1, __value, __over);
+      update(    mid+1, __r,     mid+1, __R, __i*2+2, __value, __over);
     }
-    _nodes[__index]._value = (  _nodes[ leftChild(__index)]._value
-                              | _nodes[rightChild(__index)]._value);
+    _nodes[__i]._value = (
+      (_nodes[__i * 2 + 1]._value | _nodes[__i * 2 + 2]._value)
+      + _nodes[__i]._offset
+    );
   }
   template<class Value>
   inline Value
-  SegmentTree<Value>::query(size_t __l, size_t __r,
-                            size_t __L, size_t __R,
-                            size_t __index){
-    if((__l == __L && __r == __R) || _nodes[__index]._sameFlag){
-      return _nodes[__index]._value;
-    }
+  SegmentTree<Value>::query(size_t __l, size_t __r, size_t __L, size_t __R,
+                            size_t __i){
+    if(__l == __L && __r == __R) return _nodes[__i]._value;
+    Value off = _nodes[__i]._offset * (__r - __l + 1);
+    if(_nodes[__i]._sameFlag) return off;
     size_t mid = (__L + __R) / 2;
-    Value& off = _nodes[__index]._offset;
-    if(__r <= mid){
-      return query(__l, __r, __L    , mid,  leftChild(__index)) + off;
-    }else if(mid + 1 <= __l){
-      return query(__l, __r, mid + 1, __R, rightChild(__index)) + off;
-    }else{
-      return (  query(__l    , mid, __L    , mid,  leftChild(__index))
-              | query(mid + 1, __r, mid + 1, __R, rightChild(__index))) + off;
+    if     (__r   <= mid) return query(__l,__r, __L  , mid, __i*2+1) + off;
+    else if(mid+1 <= __l) return query(__l,__r, mid+1, __R, __i*2+2) + off;
+    else{
+      return (  query(__l, mid       , __L,  mid,        __i*2+1)
+              | query(     mid+1, __r,       mid+1, __R, __i*2+2)
+              ) + off;
     }
   }
+  //
   template<class Value>
   inline bool
   SegmentTree<Value>::rangeCorrect(ssize_t* __first, ssize_t* __last) const{
-    if(*__last < *__first){
-      return false;
-    }
-    if(*__last < 0 || _size - 1 < *__first){
-      return false;
-    }
+    if(*__last<*__first || *__last<0 || _size-1<*__first) return false;
     *__first = inRange((ssize_t)0, (ssize_t)_size - 1, *__first);
     *__last  = inRange((ssize_t)0, (ssize_t)_size - 1, *__last );
     return true;
   }
-
+  //
   template<class Value>
-  inline
-  SegmentTree<Value>::SegmentTree(): _size(0), _root(0) {
-  }
+  inline SegmentTree<Value>::SegmentTree(){ reset(1); }
   template<class Value>
-  inline
-  SegmentTree<Value>::SegmentTree(size_t __size): _size(0), _root(0){
-    reset(__size);
-  }
+  inline SegmentTree<Value>::SegmentTree(size_t __size){ reset(__size); }
   template<class Value>
-  inline
-  SegmentTree<Value>::SegmentTree(SegmentTree const& __tree2):
-  _size(__tree2._size), _nodes(__tree2._nodes), _root(0){ }
+  inline SegmentTree<Value>::SegmentTree(SegmentTree const& __tree2):
+  _size(__tree2._size), _nodes(__tree2._nodes){ }
   //
   template<class Value>
   inline void
   SegmentTree<Value>::reset(size_t __size){
-    _size = __size;
+    _size = std::max(__size, (size_t)1);
     _nodes.resize(__size * 4);
-    _nodes[_root]._sameFlag = true;
-    _nodes[_root]._value = Value(0);
+    _nodes[0]._sameFlag = true;
+    _nodes[0]._value  = Value(0);
+    _nodes[0]._offset = Value(0);
   }
   template<class Value>
   inline Value
   SegmentTree<Value>::query(ssize_t __first, ssize_t __last) const{
-    if(rangeCorrect(&__first, &__last) == false){
-      return Value();
-    }
-    return ((SegmentTree*)this)->query(__first, __last, 0, _size - 1, _root);
+    if(rangeCorrect(&__first, &__last) == false) return Value();
+    return ((SegmentTree*)this)->query(__first, __last, 0, _size - 1, 0);
   }
   template<class Value>
   inline void
   SegmentTree<Value>::override(ssize_t __first, ssize_t __last,
                                Value const& __value){
-    if(rangeCorrect(&__first, &__last) == false){
-      return ;
-    }
-    override(__first, __last, 0, _size - 1, _root, __value);
+    if(rangeCorrect(&__first, &__last) == false) return ;
+    update(__first, __last, 0, _size - 1, 0, __value, true);
   }
   template<class Value>
   inline void
   SegmentTree<Value>::offset(ssize_t __first, ssize_t __last,
                              Value const& __delta){
-    if(rangeCorrect(&__first, &__last) == false){
-      return ;
-    }
-    offset(__first, __last, 0, _size - 1, _root, __delta);
+    if(rangeCorrect(&__first, &__last) == false) return ;
+    update(__first, __last, 0, _size - 1, 0, __delta, false);
   }
 }
 
-#endif
diff --git a/meowpp/dsa/SplayTree.h b/meowpp/dsa/SplayTree.h
index 3d2d2e3..f738ded 100644
--- a/meowpp/dsa/SplayTree.h
+++ b/meowpp/dsa/SplayTree.h
@@ -26,9 +26,10 @@ namespace meow{
       void sizeUpdate   (Node* __node                    ) const;
       void connectLChild(Node* __parent, Node* __child   ) const;
       void connectRChild(Node* __parent, Node* __child   ) const;
+      Node const* setRoot(Node* __node) const;
       //
-      Node* clear(Node* __node);
-      Node* dup  (Node* __node);
+      Node* clear  (Node* __node);
+      Node* dup    (Node* __node);
       //
       void rotate(               Node* __parent, Node* __child) const;
       void rotate(Node* __grand, Node* __parent, Node* __child) const;
diff --git a/meowpp/dsa/SplayTree.hpp b/meowpp/dsa/SplayTree.hpp
index 835664f..47615db 100644
--- a/meowpp/dsa/SplayTree.hpp
+++ b/meowpp/dsa/SplayTree.hpp
@@ -12,16 +12,19 @@ namespace meow{
   _rChild(NULL){ }
   //
   template<class Key, class Value>
-  inline void SplayTree<Key, Value>::offsetAdd(Node* __node,
-                                               Key const& __delta) const{
+  inline void
+  SplayTree<Key, Value>::offsetAdd(Node* __node, Key const& __delta) const{
     __node->_key       = __node->_key       + __delta;
     __node->_keyOffset = __node->_keyOffset + __delta;
   }
   template<class Key, class Value>
-  inline void SplayTree<Key, Value>::sizeUpdate(Node* __node) const{
-    __node->_size = 1;
-    if(__node->_lChild != NULL) __node->_size += __node->_lChild->_size;
-    if(__node->_rChild != NULL) __node->_size += __node->_rChild->_size;
+  inline void
+  SplayTree<Key, Value>::sizeUpdate(Node* __node) const{
+    if(__node != NULL){
+      __node->_size = 1;
+      if(__node->_lChild != NULL) __node->_size += __node->_lChild->_size;
+      if(__node->_rChild != NULL) __node->_size += __node->_rChild->_size;
+    }
   }
   template<class Key, class Value>
   inline void
@@ -32,14 +35,14 @@ namespace meow{
   }
   //
   template<class Key, class Value>
-  inline void SplayTree<Key, Value>::connectLChild(Node* __parent,
-                                                   Node* __child) const{
+  inline void
+  SplayTree<Key, Value>::connectLChild(Node* __parent, Node* __child) const{
     if(__parent != NULL) __parent->_lChild = __child;
     if(__child  != NULL) __child ->_parent = __parent;
   }
   template<class Key, class Value>
-  inline void SplayTree<Key, Value>::connectRChild(Node* __parent,
-                                                   Node* __child) const{
+  inline void
+  SplayTree<Key, Value>::connectRChild(Node* __parent, Node* __child) const{
     if(__parent != NULL) __parent->_rChild = __child;
     if(__child  != NULL) __child ->_parent = __parent;
   }
@@ -55,19 +58,26 @@ namespace meow{
     return NULL;
   }
   template<class Key, class Value>
-  inline typename SplayTree<Key, Value>::Node* SplayTree<Key, Value>::dup(Node* __node){
-    if(__node == NULL){
-      return NULL;
-    }
-    Node* node = Node(__node->_key, __node->_value);
+  inline typename SplayTree<Key, Value>::Node*
+  SplayTree<Key, Value>::dup(Node* __node){
+    if(__node == NULL) return NULL;
+    offsetDown(__node);
+    Node* node = new Node(__node->_key, __node->_value);
     connectLChild(node, dup(__node->_lChild));
     connectRChild(node, dup(__node->_rChild));
+    sizeUpdate(node);
     return node;
   }
+  template<class Key, class Value>
+  inline typename SplayTree<Key, Value>::Node const*
+  SplayTree<Key, Value>::setRoot(Node* __node) const{
+    connectLChild(NULL, (((SplayTree*)this)->_root = __node));
+    return _root;
+  }
   //
   template<class Key, class Value>
-  inline void SplayTree<Key, Value>::rotate(Node* __parent,
-                                            Node* __child) const{
+  inline void
+  SplayTree<Key, Value>::rotate(Node* __parent, Node* __child) const{
     if(__parent->_lChild == __child){
       connectLChild(__parent, __child->_rChild);
       connectRChild(__child , __parent);
@@ -79,9 +89,10 @@ namespace meow{
     sizeUpdate(__child );
   }
   template<class Key, class Value>
-  inline void SplayTree<Key, Value>::rotate(Node* __grand,
-                                            Node* __parent,
-                                            Node* __child) const{
+  inline void
+  SplayTree<Key, Value>::rotate(Node* __grand,
+                                Node* __parent,
+                                Node* __child) const{
     if(__grand->_lChild == __parent){
       if(__parent->_lChild == __child){
         connectLChild(__grand , __parent->_rChild);
@@ -112,10 +123,9 @@ namespace meow{
     sizeUpdate(__child );
   }
   template<class Key, class Value>
-  inline typename SplayTree<Key, Value>::Node* SplayTree<Key, Value>::splay(Node* __node) const{
-    if(__node == NULL){
-      return NULL;
-    }
+  inline typename SplayTree<Key, Value>::Node*
+  SplayTree<Key, Value>::splay(Node* __node) const{
+    if(__node == NULL) return NULL;
     for(Node *parent, *grand, *child = __node; child->_parent != NULL; ){
       parent = child ->_parent;
       grand  = parent->_parent;
@@ -125,26 +135,23 @@ namespace meow{
       }else{
         Node* g_grand = grand->_parent;
         rotate(grand, parent, child);
-        if(g_grand == NULL){
-          break;
-        }
+        if(g_grand == NULL) break;
         if(g_grand->_lChild == grand) connectLChild(g_grand, child);
         else                          connectRChild(g_grand, child);
       }
     }
+    sizeUpdate(__node);
     return __node;
   }
   template<class Key, class Value>
-  inline typename SplayTree<Key, Value>::Node* SplayTree<Key, Value>::findKey(Node* __node,
-                                              Key const& __key) const{
+  inline typename SplayTree<Key, Value>::Node*
+  SplayTree<Key, Value>::findKey(Node* __node, Key const& __key) const{
     Node* ret = __node;
-    for(Key offset_sum = 0; __node != NULL; offset_sum += ret->_keyOffset){
+    while(__node != NULL){
       offsetDown(__node);
       ret = __node;
-      if(!(__key < offset_sum + __node->_key)){
-        if(!(offset_sum + __node->_key< __key)){
-          break;
-        }
+      if(!(__key < __node->_key)){
+        if(!(__node->_key< __key)) break;
         __node = __node->_rChild;
       }else{
         __node = __node->_lChild;
@@ -153,8 +160,8 @@ namespace meow{
     return ret;
   }
   template<class Key, class Value>
-  inline typename SplayTree<Key, Value>::Node* SplayTree<Key, Value>::findMinMax(Node* __node,
-                                                 bool minimum) const{
+  inline typename SplayTree<Key, Value>::Node*
+  SplayTree<Key, Value>::findMinMax(Node* __node, bool minimum) const{
     Node* ret = __node;
     while(__node != NULL){
       offsetDown(__node);
@@ -164,32 +171,23 @@ namespace meow{
     return ret;
   }
   template<class Key, class Value>
-  inline typename SplayTree<Key, Value>::Node* SplayTree<Key, Value>::findOrder(Node* __node,
-                                                size_t __order) const{
+  inline typename SplayTree<Key, Value>::Node*
+  SplayTree<Key, Value>::findOrder(Node* __node, size_t __order) const{
     Node* ret = __node;
     while(__node != NULL){
       offsetDown(__node);
       ret = __node;
       size_t ord = 1 + (__node->_lChild == NULL ? 0 : __node->_lChild->_size);
-      if(ord == __order){
-        return ret;
-      }else if(ord < __order){
-        __node = __node->_rChild;
-        __order -= ord;
-      }else{
-        __node = __node->_lChild;
-      }
+      if     (ord == __order) return ret;
+      else if(ord <  __order){ __node = __node->_rChild; __order -= ord; }
+      else                   { __node = __node->_lChild;                 }
     }
     return ret;
   }
   template<class Key, class Value>
-  inline void SplayTree<Key, Value>::split(Node* __root,
-                                           Node** __left, Node** __right){
-    if(__root == NULL){
-      *__left  = NULL;
-      *__right = NULL;
-      return ;
-    }
+  inline void
+  SplayTree<Key, Value>::split(Node* __root, Node** __left, Node** __right){
+    if(__root == NULL){ *__left  = NULL; *__right = NULL; return ; }
     offsetDown(__root);
     *__left  = __root;
     *__right = __root->_rChild;
@@ -200,7 +198,8 @@ namespace meow{
     }
   }
   template<class Key, class Value>
-  inline typename SplayTree<Key, Value>::Node* SplayTree<Key, Value>::merge(Node* __left, Node* __right){
+  inline typename SplayTree<Key, Value>::Node*
+  SplayTree<Key, Value>::merge(Node* __left, Node* __right){
     if(__left  == NULL) return __right;
     if(__right == NULL) return __left ;
     offsetDown(__left);
@@ -211,9 +210,10 @@ namespace meow{
   template<class Key, class Value>
   inline void SplayTree<Key, Value>::print(Node* __now, int __depth) const{
     if(__now == NULL) return ;
-    printf("%*s [%llX]:\tParent=%llX Left=%llX Right=%llX\n",
+    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->_lChild,
            (long long unsigned)__now->_rChild);
@@ -225,24 +225,18 @@ namespace meow{
   inline void SplayTree<Key, Value>::Element::reset(Node* __node){
     _node = __node;
     delete _entry;
-    if(__node == NULL){
-      _entry = NULL;
-    }else{
-      _entry = new Entry(__node->_key, __node->_value);
-    }
+    if(__node == NULL) _entry = NULL;
+    else               _entry = new Entry(__node->_key, __node->_value);
   }
   template<class Key, class Value>
   inline SplayTree<Key, Value>::Element::Element():
-  _entry(NULL),
-  _node(NULL){ }
+  _entry(NULL), _node(NULL){ }
   template<class Key, class Value>
   inline SplayTree<Key, Value>::Element::Element(Node* __node):
-  _entry(NULL),
-  _node(NULL){ reset(__node); }
+  _entry(NULL), _node(NULL){ reset(__node); }
   template<class Key, class Value>
   inline SplayTree<Key, Value>::Element::Element(Element const& __element2):
-  _entry(NULL),
-  _node(NULL){ reset(__element2._node); }
+  _entry(NULL), _node(NULL){ reset(__element2._node); }
   template<class Key, class Value>
   inline SplayTree<Key, Value>::Element::~Element(){ delete _entry; }
   //
@@ -254,9 +248,11 @@ namespace meow{
   }
   //
   template<class Key, class Value>
-  inline typename SplayTree<Key, Value>::Element::Entry* SplayTree<Key, Value>::Element::operator->(){ return  _entry; }
+  inline typename SplayTree<Key, Value>::Element::Entry*
+  SplayTree<Key, Value>::Element::operator->(){ return  _entry; }
   template<class Key, class Value>
-  inline typename SplayTree<Key, Value>::Element::Entry& SplayTree<Key, Value>::Element::operator*(){ return *_entry; }
+  inline typename SplayTree<Key, Value>::Element::Entry&
+  SplayTree<Key, Value>::Element::operator*(){ return *_entry; }
   //
   template<class Key, class Value>
   inline bool
@@ -270,117 +266,94 @@ namespace meow{
   }
   //
   template<class Key, class Value>
-  inline SplayTree<Key, Value>::SplayTree():
-  _root(NULL){ }
+  inline SplayTree<Key, Value>::SplayTree(): _root(NULL){ }
   template<class Key, class Value>
   inline SplayTree<Key, Value>::SplayTree(SplayTree const& __tree2):
-  _root(NULL){
-    _root = dup(__tree2._root);
-  }
+  _root(NULL){ setRoot(dup(__tree2._root)); }
   template<class Key, class Value>
-  inline SplayTree<Key, Value>::~SplayTree(){
-    clear(_root);
-  }
+  inline SplayTree<Key, Value>::~SplayTree(){ clear(_root); }
   template<class Key, class Value>
-  inline SplayTree<Key, Value>& SplayTree<Key, Value>::operator=(SplayTree const& __tree2){
+  inline SplayTree<Key, Value>&
+  SplayTree<Key, Value>::operator=(SplayTree const& __tree2){
     clear(_root);
-    _root = dup(__tree2._root);
+    setRoot(dup(__tree2._root));
     return *this;
   }
   //
   template<class Key, class Value>
-  inline typename SplayTree<Key, Value>::Element SplayTree<Key, Value>::lowerBound(Key const& __key) const{
+  inline typename SplayTree<Key, Value>::Element
+  SplayTree<Key, Value>::lowerBound(Key const& __key) const{
     SplayTree* me = (SplayTree*)this;
-    me->_root = splay(findKey(me->_root, __key));
-    me->_root->_parent = NULL;
-    if(_root == NULL || !(_root->_key < __key)){
-      return Element(_root);
-    }
-    if(_root->_rChild == NULL){
-      return NULL;
-    }
-    me->_root = splay(findMinMax(me->_root->_rChild, true));
-    me->_root->_parent = NULL;
+    setRoot(splay(findKey(me->_root, __key)));
+    if(_root == NULL || !(_root->_key < __key)) return Element(_root);
+    if(_root->_rChild == NULL)                  return Element(NULL);
+    setRoot(splay(findMinMax(me->_root->_rChild, true)));
     return Element(_root);
   }
   template<class Key, class Value>
-  inline typename SplayTree<Key, Value>::Element SplayTree<Key, Value>::upperBound(Key const& __key) const{
+  inline typename SplayTree<Key, Value>::Element
+  SplayTree<Key, Value>::upperBound(Key const& __key) const{
     SplayTree* me = (SplayTree*)this;
-    me->_root = splay(findKey(me->_root, __key));
-    me->_root->_parent = NULL;
-    if(_root == NULL || __key < _root->_key){
-      return Element(_root);
-    }
-    if(_root->_rChild == NULL){
-      return NULL;
-    }
-    me->_root = splay(findMinMax(me->_root->_rChild, true));
-    me->_root->_parent = NULL;
+    setRoot(splay(findKey(me->_root, __key)));
+    if(_root == NULL || __key < _root->_key) return Element(_root);
+    if(_root->_rChild == NULL) return Element(NULL);
+    setRoot(splay(findMinMax(me->_root->_rChild, true)));
     return Element(_root);
   }
   template<class Key, class Value>
-  inline typename SplayTree<Key, Value>::Element SplayTree<Key, Value>::rLowerBound(Key const& __key) const{
+  inline typename SplayTree<Key, Value>::Element
+  SplayTree<Key, Value>::rLowerBound(Key const& __key) const{
     SplayTree* me = (SplayTree*)this;
-    me->_root = splay(findKey(me->_root, __key));
-    me->_root->_parent = NULL;
-    if(_root == NULL || !(__key < _root->_key)){
-      return Element(_root);
-    }
+    setRoot(splay(findKey(me->_root, __key)));
+    if(_root == NULL || !(__key < _root->_key)) return Element(_root);
     if(_root->_lChild == NULL){
       return NULL;
     }
-    me->_root = splay(findMinMax(me->_root->_lChild, false));
-    me->_root->_parent = NULL;
+    setRoot(splay(findMinMax(me->_root->_lChild, false)));
     return Element(_root);
   }
   template<class Key, class Value>
-  inline typename SplayTree<Key, Value>::Element SplayTree<Key, Value>::rUpperBound(Key const& __key) const{
+  inline typename SplayTree<Key, Value>::Element
+  SplayTree<Key, Value>::rUpperBound(Key const& __key) const{
     SplayTree* me = (SplayTree*)this;
-    me->_root = splay(findKey(me->_root, __key));
-    me->_root->_parent = NULL;
-    if(_root == NULL || _root->_key < __key){
-      return Element(_root);
-    }
-    if(_root->_lChild == NULL){
-      return NULL;
-    }
-    me->_root = splay(findMinMax(me->_root->_lChild, false));
-    me->_root->_parent = NULL;
+    setRoot(splay(findKey(me->_root, __key)));
+    if(_root == NULL || _root->_key < __key) return Element(_root);
+    if(_root->_lChild == NULL)               return Element(NULL);
+    setRoot(splay(findMinMax(me->_root->_lChild, false)));
     return Element(_root);
   }
   template<class Key, class Value>
-  inline typename SplayTree<Key, Value>::Element SplayTree<Key, Value>::find(Key const& __key) const{
+  inline typename SplayTree<Key, Value>::Element
+  SplayTree<Key, Value>::find(Key const& __key) const{
     SplayTree* me = (SplayTree*)this;
-    me->_root = splay(findKey(me->_root, __key));
-    me->_root->_parent = NULL;
-    if(_root != NULL && _root->_key == __key){
-      return Element(_root);
-    }
+    setRoot(splay(findKey(me->_root, __key)));
+    if(_root != NULL && _root->_key == __key) return Element(_root);
     return Element(NULL);
   }
   template<class Key, class Value>
-  inline typename SplayTree<Key, Value>::Element SplayTree<Key, Value>::order(size_t __order) const{
+  inline typename SplayTree<Key, Value>::Element
+  SplayTree<Key, Value>::order(size_t __order) const{
     SplayTree* me = (SplayTree*)this;
-    me->_root = splay(findOrder(me->_root, __order + 1));
-    me->_root->_parent = NULL;
+    setRoot(splay(findOrder(me->_root, __order + 1)));
     return Element(_root);
   }
   template<class Key, class Value>
-  inline typename SplayTree<Key, Value>::Element SplayTree<Key, Value>::first() const{
+  inline typename SplayTree<Key, Value>::Element
+  SplayTree<Key, Value>::first() const{
     SplayTree* me = (SplayTree*)this;
-    me->_root = splay(findMinMax(me->_root, true));
-    me->_root->_parent = NULL;
+    setRoot(splay(findMinMax(me->_root, true)));
     return Element(_root);
   }
   template<class Key, class Value>
-  inline typename SplayTree<Key, Value>::Element SplayTree<Key, Value>::last() const{
+  inline typename SplayTree<Key, Value>::Element
+  SplayTree<Key, Value>::last() const{
     SplayTree* me = (SplayTree*)this;
-    me->_root = splay(findMinMax(me->_root, false));
-    me->_root->_parent = NULL;
+    setRoot(splay(findMinMax(me->_root, false)));
     return Element(_root);
   }
   template<class Key, class Value>
-  inline typename SplayTree<Key, Value>::Element SplayTree<Key, Value>::end() const{ return Element(NULL); }
+  inline typename SplayTree<Key, Value>::Element
+  SplayTree<Key, Value>::end() const{ return Element(NULL); }
   template<class Key, class Value>
   inline size_t SplayTree<Key, Value>::size() const{
     return (_root == NULL ? 0 : _root->_size);
@@ -403,87 +376,96 @@ namespace meow{
   inline bool SplayTree<Key, Value>::insert(Key const& __key,
                                             Value const& __value){
     if(_root == NULL){
-      _root = new Node(__key, __value);
+      setRoot(new Node(__key, __value));
       return true;
     }
     Node* parent = findKey(_root, __key);
     Node* new_node;
     if(parent->_key < __key){
       connectRChild(parent, new_node = new Node(__key, __value));
+      sizeUpdate(parent);
     }else if(__key < parent->_key){
       connectLChild(parent, new_node = new Node(__key, __value));
+      sizeUpdate(parent);
     }else{
-      _root = splay(parent);
-      _root->_parent = NULL;
+      setRoot(splay(parent));
       return false;
     }
-    _root = splay(new_node);
-    _root->_parent = NULL;
+    setRoot(splay(new_node));
     return true;
   }
   template<class Key, class Value>
   inline bool SplayTree<Key, Value>::erase(Key const& __key){
-    if(_root == NULL){
-      return false;
-    }
+    if(_root == NULL) return false;
     Node* body = findKey(_root, __key);
     if(body->_key < __key || __key < body->_key){
+      setRoot(splay(body));
       return false;
     }
     Node* ghost;
     if(body->_rChild == NULL){
       ghost = body->_lChild;
+      if(ghost != NULL) offsetDown(ghost);
     }else{
       ghost = findMinMax(body->_rChild, true);
       connectLChild(ghost, body->_lChild);
       if(ghost != body->_rChild){
-        connectLChild(ghost->_parent, ghost->_lChild);
-        connectLChild(ghost, body->_rChild);
+        connectLChild(ghost->_parent, ghost->_rChild);
+        connectRChild(ghost, body->_rChild);
+        for(Node* acestor = ghost->_parent;
+            acestor != ghost;
+            acestor = acestor->_parent){
+          sizeUpdate(acestor);
+        }
       }
+      sizeUpdate(ghost);
     }
     if(body->_parent != NULL && body->_parent->_lChild == body){
       connectLChild(body->_parent, ghost);
     }else{
       connectRChild(body->_parent, ghost);
     }
-    _root = splay(ghost != NULL ? ghost : body->_parent);
-    _root->_parent = NULL;
+    setRoot(splay(ghost != NULL ? ghost : body->_parent));
     return true;
   }
   template<class Key, class Value>
-  inline Value& SplayTree<Key, Value>::operator[](Key const& __key){
-    if(find(__key) == end()){
-      insert(__key, Value());
-    }
+  inline Value&
+  SplayTree<Key, Value>::operator[](Key const& __key){
+    if(find(__key) == end()) insert(__key, Value());
     return find(__key)->second;
   }
   template<class Key, class Value>
-  inline void SplayTree<Key, Value>::splitOut(Key const& __upper_bound,
-                                              SplayTree* __right){
+  inline void
+  SplayTree<Key, Value>::splitOut(Key const& __upper_bound, SplayTree* __right){
     __right->clear();
-    rLowerBound(__upper_bound);
-    split(_root, &_root, &(__right->_root));
+    if(rLowerBound(__upper_bound) != Element(NULL)){
+      split(_root, &_root, &(__right->_root));
+    }else{
+      __right->_root = _root;
+      _root = NULL;
+    }
   }
   template<class Key, class Value>
-  inline bool SplayTree<Key, Value>::mergeAfter(SplayTree* __tree2){
+  inline bool
+  SplayTree<Key, Value>::mergeAfter(SplayTree* __tree2){
     if(_root == NULL || __tree2->_root == NULL ||
        last()->first < __tree2->first()->first){
-      _root = merge(_root, __tree2->_root);
+      setRoot(merge(_root, __tree2->_root));
       __tree2->_root = NULL;
       return true;
     }
     return false;
   }
   template<class Key, class Value>
-  inline bool SplayTree<Key, Value>::merge(SplayTree* __tree2){
+  inline bool
+  SplayTree<Key, Value>::merge(SplayTree* __tree2){
     if(_root == NULL || __tree2->_root == NULL){
-      _root = merge(_root, __tree2->_root);
+      setRoot(merge(_root, __tree2->_root));
     }else{
       if(last()->first < __tree2->first()->first){
-        _root = merge(_root, __tree2->_root);
-        __tree2->_root = NULL;
+        setRoot(merge(_root, __tree2->_root));
       }else if(__tree2->last()->first < first()->first){
-        _root = merge(__tree2->_root, _root);
+        setRoot(merge(__tree2->_root, _root));
       }else{
         return false;
       }
@@ -492,11 +474,13 @@ namespace meow{
     return true;
   }
   template<class Key, class Value>
-  inline void SplayTree<Key, Value>::print() const{
+  inline void
+  SplayTree<Key, Value>::print() const{
     print(_root, 0);
   }
   template<class Key, class Value>
-  inline void SplayTree<Key, Value>::moveTo(SplayTree* __tree2){
+  inline void
+  SplayTree<Key, Value>::moveTo(SplayTree* __tree2){
     __tree2->clear();
     __tree2->_root = _root;
     _root = NULL;
diff --git a/meowpp/oo/Register_Implement.h b/meowpp/oo/Register_Implement.h
index dd496fa..2e8ca32 100644
--- a/meowpp/oo/Register_Implement.h
+++ b/meowpp/oo/Register_Implement.h
@@ -2,6 +2,7 @@
 #define   REGISTER_IMPLEMENT_H_
 
 #include <map>
+#include <vector>
 
 namespace meow{
   template<class T>
@@ -25,6 +26,7 @@ namespace meow{
       virtual bool                   regImplement(ImplementInterface<T>*imp);
       virtual ImplementInterface<T>* getImplement(T const& identify);
       virtual ~RegisterInterface(){ }
+      std::vector<T> getIdentifys() const;
   };
   /*******************************************************************
     @asciidoc
@@ -38,7 +40,7 @@ namespace meow{
    * Let all the problem-solving classes inherit from
    `class ImplementInterface<T>` , and call the constructure with giving
    `identify` (type `T` ) .
-   * Create an object, type `RegisterInterface<T>` , and register all your
+   * Create an class inherit from `RegisterInterface<T>` , and register all your
    implement class to it by call `regImplement(pointer to the class)`.
    * Select which implement class you want by call `getImplement(identify)` ,
    which will return the pointer to the corresponding class.
diff --git a/meowpp/oo/Register_Implement.hpp b/meowpp/oo/Register_Implement.hpp
index 34d9129..206b0a3 100644
--- a/meowpp/oo/Register_Implement.hpp
+++ b/meowpp/oo/Register_Implement.hpp
@@ -1,5 +1,5 @@
-
 #include <map>
+#include <vector>
 
 namespace meow{
   template<class T>
@@ -20,4 +20,14 @@ namespace meow{
     }
     return implements[identify];
   }
+  template<class T>
+  inline std::vector<T>
+  RegisterInterface<T>::getIdentifys() const{
+    std::vector<T> ret;
+    for(typename std::map<T, ImplementInterface<T>*>::const_iterator
+        it = implements.begin(); it != implements.end(); it++){
+      ret.push_back(it->first);
+    }
+    return ret;
+  }
 }