add BIT

3 files changed, 1353 insertions, 0 deletions

diff --git a/_test/meowpp_SplayTree_Range.cpp b/_test/meowpp_SplayTree_Range.cpp
new file mode 100644
index 0000000..870d91a
--- /dev/null
+++ b/_test/meowpp_SplayTree_Range.cpp
@@ -0,0 +1,575 @@
+#include "meowpp.h"
+
+#include <algorithm>
+#include <utility>
+#include <map>
+#include <cstdlib>
+#include <cmath>
+
+static int min_sum;
+struct Double{
+  double k;
+  Double(): k(0){ }
+  Double(double _k): k(0){ }
+  bool operator==(const Double& b) const{ fabs(k - b.k) <= 1e-9; }
+  bool operator!=(const Double& b) const{ fabs(k - b.k) >  1e-9; }
+  bool operator<(const Double& b) const{ return k < b.k; }
+  Double operator+(const Double& b) const{ return Double(k + b.k); }
+  Double operator*(size_t& b) const{
+    if(min_sum == 0) return Double(k);
+    else             return Double(k * b);
+  }
+  Double operator|(const Double& b) const{
+    if(min_sum == 0) return Double(std::min(k, b.k));
+    else             return Double(k + b.k);
+  }
+};
+
+static int N;
+
+static bool detail_fg;
+
+typedef typename  std::map      <int, Double>::        iterator IterN;
+typedef typename  std::map      <int, Double>::reverse_iterator IterR;
+typedef typename meow::SplayTree_Range<int, Double>::Element          IterS;
+
+static std::vector< std::map      <int, Double> > normal;
+static std::vector<meow::SplayTree_Range<int, Double> > splay;
+
+static void show(bool fg = false){
+  if(fg){
+    for(int i = 0; i < N; i++){
+      printf("normal %d-%lu: ", i, normal[i].size());
+      for(IterN it = normal[i].begin(); it != normal[i].end(); it++){
+        printf("%d/%.2f ", it->first, it->second.k);
+      }
+      printf("\n");
+      printf("splay  %d-%lu: ", i, splay[i].size());
+      bool bye = false;
+      for(int j = 0; j < splay[i].size(); j++){
+        IterS it = splay[i].order(j);
+        printf("%d/%.2f ", it->first, it->second.k);
+      }
+      printf("\n");
+    }
+    printf("\n");
+  }
+}
+
+static bool lowerBound(int i, int key, size_t* tN, size_t* tS){
+  size_t t0;
+  detail_fg && printf("============= lowerBound(%d, %d)\n", i, key);
+  t0 = clock(); IterS b = splay [i].lowerBound (key); (*tS) += clock() - t0;
+  t0 = clock(); IterN a = normal[i].lower_bound(key); (*tN) += clock() - t0;
+  detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n",
+                      (a == normal[i].end()) ? 0 : a->first,
+                      (b == splay[i].end()) ? 0 : b->first,
+                      (a == normal[i].end()) ? 0 : a->second.k,
+                      (b == splay[i].end()) ? 0 : b->second.k);
+  show(detail_fg);
+  if((a == normal[i].end()) != (b == splay[i].end())) return false;
+  if( a == normal[i].end()) return true;
+  return (a->first == b->first && a->second.k == b->second.k);
+}
+static bool upperBound(int i, int key, size_t* tN, size_t* tS){
+  size_t t0;
+  detail_fg && printf("============= upperBound(%d, %d)\n", i, key);
+  t0 = clock(); IterS b = splay [i].upperBound (key); (*tS) += clock() - t0;
+  t0 = clock(); IterN a = normal[i].upper_bound(key); (*tN) += clock() - t0;
+  detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n",
+                      (a == normal[i].end()) ? 0 : a->first,
+                      (b == splay [i].end()) ? 0 : b->first,
+                      (a == normal[i].end()) ? 0 : a->second.k,
+                      (b == splay [i].end()) ? 0 : b->second.k);
+  show(detail_fg);
+  if((a == normal[i].end()) != (b == splay[i].end())) return false;
+  if( a == normal[i].end()) return true;
+  return (a->first == b->first && a->second.k == b->second.k);
+}
+static bool rLowerBound(int i, int key, size_t* tN, size_t* tS){
+  size_t t0;
+  detail_fg && printf("============= rLowerBound(%d, %d)\n", i, key);
+  t0 = clock(); IterS b =   splay [i].rLowerBound(key); (*tS) += clock() - t0;
+  t0 = clock();
+  IterN a, z;
+  if(normal[i].size() == 0 || normal[i].begin()->first > key){
+    a = normal[i].end();
+  }else{
+    for(a = normal[i].begin(), z = a, z++; z != normal[i].end(); z++, a++){
+      if(z->first > key){
+        break;
+      }
+    }
+  }
+  detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n",
+                      (a == normal[i].end()) ? 0 : a->first,
+                      (b == splay[i].end()) ? 0 : b->first,
+                      (a == normal[i].end()) ? 0 : a->second.k,
+                      (b == splay[i].end()) ? 0 : b->second.k);
+  show(detail_fg);
+  if((a == normal[i].end()) != (b == splay[i].end())) return false;
+  if( a == normal[i].end()) return true;
+  return (a->first == b->first && a->second.k == b->second.k);
+}
+static bool rUpperBound(int i, int key, size_t* tN, size_t* tS){
+  size_t t0;
+  detail_fg && printf("============= rUpperBound(%d, %d)\n", i, key);
+  t0 = clock(); IterS b =   splay [i].rUpperBound(key); (*tS) += clock() - t0;
+  t0 = clock();
+  IterN a, z;
+  if(normal[i].begin() == normal[i].end()){
+    a = normal[i].end();
+  }else{
+    if(normal[i].begin()->first >= key) a = normal[i].end();
+    else{
+      for(a = normal[i].begin(), z = a, z++; z != normal[i].end(); a++, z++){
+        if(z->first >= key)
+          break;
+      }
+    }
+  }
+  detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n",
+                      (a == normal[i].end()) ? 0 : a->first,
+                      (b == splay[i].end()) ? 0 : b->first,
+                      (a == normal[i].end()) ? 0 : a->second.k,
+                      (b == splay[i].end()) ? 0 : b->second.k);
+  show(detail_fg);
+  if((a == normal[i].end()) != (b == splay[i].end())) return false;
+  if( a == normal[i].end()) return true;
+  return (a->first == b->first && a->second.k == b->second.k);
+}
+static bool find(int i, int key, size_t* tN, size_t* tS){
+  size_t t0;
+  detail_fg && printf("============= find(%d, %d)\n", i, key);
+  t0 = clock(); IterS b = splay [i].find(key); (*tS) += clock() - t0;
+  t0 = clock(); IterN a = normal[i].find(key); (*tN) += clock() - t0;
+  detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n",
+                      (a == normal[i].end()) ? 0 : a->first,
+                      (b == splay[i].end()) ? 0 : b->first,
+                      (a == normal[i].end()) ? 0 : a->second.k,
+                      (b == splay[i].end()) ? 0 : b->second.k);
+  show(detail_fg);
+  if((a == normal[i].end()) != (b == splay[i].end())) return false;
+  if( a == normal[i].end()) return true;
+  return (a->first == b->first && a->second.k == b->second.k);
+}
+static bool order(int i, int order, size_t* tN, size_t* tS){
+  size_t t0;
+  detail_fg && printf("============= order(%d, %d)\n", i, order);
+  t0 = clock(); IterS b = splay[i].order(order); (*tS) += clock() - t0;
+  t0 = clock();
+  IterN a = normal[i].begin();
+  for(int k = 0; k < order; k++) a++;
+  (*tN) += clock() - t0;
+  detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n",
+                      (a == normal[i].end()) ? 0 : a->first,
+                      (b == splay[i].end()) ? 0 : b->first,
+                      (a == normal[i].end()) ? 0 : a->second.k,
+                      (b == splay[i].end()) ? 0 : b->second.k);
+  show(detail_fg);
+  if((a == normal[i].end()) != (b == splay[i].end())) return false;
+  if( a == normal[i].end()) return true;
+  return (a->first == b->first && a->second.k == b->second.k);
+}
+static bool first_last(int i, size_t* tN, size_t* tS){
+  size_t t0;
+  detail_fg && printf("============= first_last(%d)\n", i);
+  IterN a;
+  t0 = clock(); IterS b = splay[i].first (); (*tS) += clock() - t0;
+  t0 = clock(); a = normal[i].begin(); (*tN) += clock() - t0;
+  detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n",
+                      (a == normal[i].end()) ? 0 : a->first,
+                      (b == splay[i].end()) ? 0 : b->first,
+                      (a == normal[i].end()) ? 0 : a->second.k,
+                      (b == splay[i].end()) ? 0 : b->second.k);
+  if((a == normal[i].end()) != (b == splay[i].end())) return false;
+  if( a == normal[i].end());
+  else{
+    if((a->first == b->first && a->second.k == b->second.k) == false){
+      return false;
+    }
+  }
+  t0 = clock(); b = splay[i].last   (); (*tS) += clock() - t0;
+  t0 = clock(); IterR r = normal[i].rbegin(); (*tN) += clock() - t0;
+  detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n",
+                      (r == normal[i].rend()) ? 0 : r->first,
+                      (b == splay[i].end()) ? 0 : b->first,
+                      (r == normal[i].rend()) ? 0 : r->second.k,
+                      (b == splay[i].end()) ? 0 : b->second.k);
+  if((r == normal[i].rend()) != (b == splay[i].end())) return false;
+  if(r == normal[i].rend());
+  else{
+    if((r->first == b->first && r->second.k == b->second.k) == false){
+      return false;
+    }
+  }
+  return true;
+}
+static bool insert(int i, int key, Double val, size_t* tN, size_t* tS){
+  size_t t0;
+  if(rand() & 1){
+    t0 = clock(); splay [i].insert(key, val); (*tS) += clock() - t0;
+    t0 = clock(); normal[i].insert(std::pair<int, Double>(key, val)); (*tN) += clock() - t0;
+  }else{
+    t0 = clock(); splay [i][key] = val; (*tS) += clock() - t0;
+    t0 = clock(); normal[i][key] = val; (*tN) += clock() - t0;
+  }
+  detail_fg && printf("============= insert(%d, %d)\n", i, key);
+  show(detail_fg);
+  return true;
+}
+static bool split(int i, int j, int key, size_t* tN, size_t* tS){
+  size_t t0;
+  if(i == j){
+    return true;
+  }
+  detail_fg && printf("============= split(%d, %d, %d)\n", i, j, key);
+  t0 = clock(); splay[i].splitOut(key, &splay[j]); *tS += clock() - t0;
+  t0 = clock();
+  normal[j].clear();
+  for(IterN it; (it = normal[i].upper_bound(key)) != normal[i].end(); ){
+    normal[j].insert(*it);
+    normal[i].erase(it);
+  }
+  *tN += clock() - t0;
+  show(detail_fg);
+  return true;
+}
+static bool merge(int i, int j, int key, size_t* tN, size_t* tS){
+  size_t t0;
+  if(i == j){
+    return true;
+  }
+  if(rand() & 1){
+    t0 = clock();
+    if(splay[i].size() > 0)
+      while(splay[j].size() > 0 &&
+            splay[j].first()->first <= splay[i].last()->first){
+        splay[j].erase(splay[j].first()->first);
+      }
+    *tS += clock() - t0;
+    t0 = clock();
+    if(normal[i].size() > 0)
+      while(normal[j].size() > 0 &&
+            normal[j].begin()->first <= normal[i].rbegin()->first)
+        normal[j].erase(normal[j].begin());
+    *tN += clock() - t0;
+  }
+  t0 = clock(); splay[i].merge(&splay[j]); *tS += clock() - t0;
+  t0 = clock();
+  if(normal[i].size() == 0 || normal[j].size() == 0 ||
+      normal[i].rbegin()->first < normal[j].begin()->first ||
+      normal[j].rbegin()->first < normal[i].begin()->first
+  ){
+    for(IterN it = normal[j].begin(); it != normal[j].end(); it++){
+      normal[i].insert(*it);
+    }
+    normal[j].clear();
+  }
+  *tN += clock() - t0;
+  detail_fg && printf("============= merge(%d, %d)\n", i, j, key);
+  show(detail_fg);
+  return true;
+}
+static bool erase(int i, int key, size_t* tN, size_t* tS){
+  size_t t0;
+  detail_fg && printf("============= erase(%d, %d)\n", i, key);
+  t0 = clock(); splay[i].erase(key); (*tS) += clock() - t0;
+  t0 = clock(); normal[i].erase(key); (*tN) += clock() - t0;
+  show(detail_fg);
+  return true;
+}
+static bool keyOffset(int i, int delta, size_t* tN, size_t* tS){
+  size_t t0;
+  detail_fg && printf("============= keyOffset(%d, %d)\n", i, delta);
+  t0 = clock(); splay[i].keyOffset(delta); (*tS) += clock() - t0;
+  t0 = clock();
+  std::map<int, Double> tmp = normal[i];
+  normal[i].clear();
+  for(IterN it = tmp.begin(); it != tmp.end(); it++){
+    normal[i].insert(std::pair<int, Double>(it->first + delta, it->second.k));
+  }
+  (*tN) += clock() - t0;
+  show(detail_fg);
+  return true;
+}
+static bool valueOffset(int i, Double delta, size_t* tN, size_t* tS){
+  size_t t0;
+  detail_fg && printf("============= valueOffset(%d, %f)\n", i, delta.k);
+  t0 = clock(); splay[i].valueOffset(delta); (*tS) += clock() - t0;
+  t0 = clock();
+  for(IterN it = normal[i].begin(); it != normal[i].end(); it++){
+    it->second = it->second + delta;
+  }
+  (*tN) += clock() - t0;
+  show(detail_fg);
+  return true;
+}
+static bool valueOverride(int i, Double value, size_t* tN, size_t* tS){
+  size_t t0;
+  detail_fg && printf("============= valueOverride(%d, %f)\n", i, value.k);
+  t0 = clock(); splay[i].valueOverride(value); (*tS) += clock() - t0;
+  t0 = clock();
+  for(IterN it = normal[i].begin(); it != normal[i].end(); it++){
+    it->second.k = value.k;
+  }
+  (*tN) += clock() - t0;
+  show(detail_fg);
+  return true;
+}
+static bool query(int i, int a, int b, size_t* tN, size_t* tS){
+  size_t t0;
+  detail_fg && printf("============= query(%d, %d, %d)\n", i, a, b);
+  Double ans1, ans2 = 0;
+  if(rand() & 3 == 3){
+    t0 = clock(); ans1 = splay[i].query(); (*tS) += clock() - t0;
+    t0 = clock();
+    for(IterN it = normal[i].begin(); it != normal[i].end(); it++){
+      ans2 = ans2 | it->second.k;
+    }
+  }else{
+    t0 = clock(); ans1 = splay[i].query(a, b); (*tS) += clock() - t0;
+    t0 = clock();
+    for(IterN it = normal[i].begin(); it != normal[i].end(); it++){
+      if(a <= it->first && it->first <= b)
+        ans2 = ans2 | it->second.k;
+    }
+  }
+  detail_fg && printf(">>get %f %f\n", ans1.k, ans2.k);
+  show(detail_fg);
+  return true;
+}
+static bool copy(int i, int j, size_t* tN, size_t* tS){
+  size_t t0;
+  detail_fg && printf("copy(%d, %d)\n", i, j);
+  t0 = clock(); splay[i] = splay[j]; (*tS) += clock() - t0;
+  t0 = clock(); normal[i] = normal[j]; (*tN) += clock() - t0;
+  show(detail_fg);
+  return true;
+}
+
+static bool check(){
+  for(int i = 0; i < N; i++){
+    if(normal[i].size() != splay[i].size()) return false;
+    int j = 0;
+    for(IterN it = normal[i].begin(); it != normal[i].end(); it++, j++){
+      if(it->first  != splay[i].order(j)->first ||
+         it->second.k != splay[i].order(j)->second.k)
+        return false;
+    }
+  }
+  return true;
+}
+
+TEST(SplayTree_Range){
+  detail_fg = false;
+  N = 5;
+  for(int i = 0; i < 10; i++){
+    normal.clear();
+    splay .clear();
+    normal.resize(N);
+    splay .resize(N);
+    size_t tn = 0, tm = 0;
+    int op = 1 + rand() % 2000000;
+    min_sum = rand() & 1;
+    meow::messagePrintf(1, "%d-th test, N = %d, op = %7d", i, N, op);
+    while(op--){
+      int wh = rand() % 100;
+      int i1 = rand() % N, i2, k = rand() % 60;
+      while((i2 = rand() % N) == i1);
+      switch(wh){
+        case  0:
+          if(lowerBound(i1, k, &tn, &tm) == false){
+            meow::messagePrintf(-1, "fail(%s)", "lowerBound");
+            //for(int z = 0; z < N; z++){ splay[z].print(); }
+            show(true);
+            return false;
+          }
+          break;
+        case  1:
+          if(rUpperBound(i1, k, &tn, &tm) == false){
+            meow::messagePrintf(-1, "fail(%s)", "rUpperBound");
+            //for(int z = 0; z < N; z++){ splay[z].print(); }
+            show(true);
+            return false;
+          }
+          break;
+        case  2:
+          if(rLowerBound(i1, k, &tn, &tm) == false){
+            meow::messagePrintf(-1, "fail(%s)", "rLowerBound");
+            //for(int z = 0; z < N; z++){ splay[z].print(); }
+            show(true);
+            return false;
+          }
+          break;
+        case  3:
+          if(upperBound(i1, k, &tn, &tm) == false){
+            meow::messagePrintf(-1, "fail(%s)", "upperBound");
+            //for(int z = 0; z < N; z++){ splay[z].print(); }
+            show(true);
+            return false;
+          }
+          break;
+        case  4:
+        case  5:
+        case  6:
+          if(find(i1, k, &tn, &tm) == false){
+            meow::messagePrintf(-1, "fail(%s)", "find");
+            //for(int z = 0; z < N; z++){ splay[z].print(); }
+            show(true);
+            return false;
+          }
+          break;
+        case  7:
+        case  8:
+        case  9:
+          if(normal[i1].size() > 0){
+            if(order(i1, rand() % normal[i1].size(), &tn, &tm) == false){
+              meow::messagePrintf(-1, "fail(%s)", "order");
+              //for(int z = 0; z < N; z++){ splay[z].print(); }
+              show(true);
+              return false;
+            }
+            break;
+          }
+        case 10:
+          if(first_last(i1, &tn, &tm) == false){
+            meow::messagePrintf(-1, "fail(%s)", "first_last");
+            //for(int z = 0; z < N; z++){ splay[z].print(); }
+            show(true);
+            return false;
+          }
+          break;
+        case 11:
+        case 12:
+        case 13:
+        case 14:
+        case 15:
+        case 16:
+        case 17:
+        case 18:
+        case 19:
+        case 20:
+          if(insert(i1, k, rand() * 1.0 / RAND_MAX * 50 + 1, &tn, &tm) == false){
+            meow::messagePrintf(-1, "fail(%s)", "insert");
+            //for(int z = 0; z < N; z++){ splay[z].print(); }
+            show(true);
+            return false;
+          }
+          break;
+        case 21:
+        case 22:
+        case 23:
+        case 24:
+        case 25:
+        case 26:
+          if(split(i1, i2, k, &tn, &tm) == false){
+            meow::messagePrintf(-1, "fail(%s)", "split");
+            //for(int z = 0; z < N; z++){ splay[z].print(); }
+            show(true);
+            return false;
+          }
+          break;
+        case 27:
+        case 28:
+        case 29:
+        case 30:
+        case 31:
+        case 32:
+        case 33:
+        case 34:
+        case 35:
+        case 36:
+          if(merge(i1, i2, k, &tn, &tm) == false){
+            meow::messagePrintf(-1, "fail(%s)", "merge");
+            //for(int z = 0; z < N; z++){ splay[z].print(); }
+            show(true);
+            return false;
+          }
+          break;
+        case 37:
+        case 38:
+        case 39:
+        case 40:
+          if(erase(i1, k, &tn, &tm) == false){
+            meow::messagePrintf(-1, "fail(%s)", "erase");
+            //for(int z = 0; z < N; z++){ splay[z].print(); }
+            show(true);
+            return false;
+          }
+          break;
+        case 41:
+        case 42:
+        case 43:
+        case 44:
+        case 45:
+        case 46:
+        case 47:
+        case 48:
+        case 49:
+          if(keyOffset(i1, ((rand() & 2) - 1) * k, &tn, &tm) == false){
+            meow::messagePrintf(-1, "fail(%s)", "keyOffset");
+            //for(int z = 0; z < N; z++){ splay[z].print(); }
+            show(true);
+            return false;
+          }
+          break;
+        case 50:
+        case 51:
+        case 52:
+          if(copy(i1, i2, &tn, &tm) == false){
+            meow::messagePrintf(-1, "fail(%s)", "copy");
+            //for(int z = 0; z < N; z++){ splay[z].print(); }
+            show(true);
+            return false;
+          }
+          break;
+        case 53:
+        case 54:
+        case 55:
+        case 56:
+        case 57:
+        case 58:
+        case 59:
+          if(valueOverride(i1, 1.0 * rand() / RAND_MAX * 100 + 1, &tn, &tm) == false){
+            meow::messagePrintf(-1, "fail(%s)", "valueOffset");
+            //for(int z = 0; z < N; z++){ splay[z].print(); }
+            show(true);
+            return false;
+          }
+          break;
+        case 60:
+        case 61:
+        case 62:
+        case 63:
+        case 64:
+        case 65:
+        case 66:
+          if(valueOffset(i1, 1.0 * rand() / RAND_MAX * 100 + 1, &tn, &tm) == false){
+            meow::messagePrintf(-1, "fail(%s)", "valueOffset");
+            //for(int z = 0; z < N; z++){ splay[z].print(); }
+            show(true);
+            return false;
+          }
+          break;
+        default:
+          if(query(i1, rand() % 200 - 100, rand() % 200 - 100, &tn, &tm) == false){
+            meow::messagePrintf(-1, "fail(%s)", "query");
+            //for(int z = 0; z < N; z++){ splay[z].print(); }
+            show(true);
+            return false;
+          }
+          break;
+      }
+    }
+    if(!check()){
+      meow::messagePrintf(-1, "fail");
+      show(true);
+      return false;
+    }
+    meow::messagePrintf(-1, "ok %.3f/%.3f",
+                        tm * 1.0 / CLOCKS_PER_SEC,
+                        tn * 1.0 / CLOCKS_PER_SEC);
+  }
+  return true;
+};
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);
+  }
+}
+