1 files changed, 157 insertions, 0 deletions
diff --git a/meowpp.test/src/SegmentTree.cpp b/meowpp.test/src/SegmentTree.cpp
new file mode 100644
index 0000000..c795477
--- /dev/null
+++ b/meowpp.test/src/SegmentTree.cpp
@@ -0,0 +1,157 @@
+#include "meowpp/dsa/SegmentTree.h"
+#include "meowpp/utility.h"
+
+#include "dsa.h"
+
+#include <ctime>
+#include <algorithm>
+
+struct RangeMax{
+  int value;
+  //
+  RangeMax(){}
+  RangeMax(int _value): value(_value){ }
+  RangeMax(RangeMax const& b): value(b.value){ }
+  //
+  RangeMax operator*(size_t n) const{ return RangeMax(value); }
+  RangeMax operator|(RangeMax const& b) const{ return RangeMax(std::max(value, b.value)); }
+  RangeMax operator+(RangeMax const& b) const{ return RangeMax(b.value + value); }
+  bool operator==(RangeMax const& b) const{ return (value == b.value); }
+};
+struct RangeSum{
+  int value;
+  //
+  RangeSum(){}
+  RangeSum(int _value): value(_value){ }
+  RangeSum(RangeSum const& b): value(b.value){ }
+  //
+  RangeSum operator*(size_t n) const{ return RangeSum(n * value); }
+  RangeSum operator|(RangeSum const& b) const{ return RangeSum(value + b.value); }
+  RangeSum operator+(RangeSum const& b) const{ return RangeSum(b.value + value); }
+  bool operator==(RangeSum const& b) const{ return (value == b.value); }
+};
+
+meow::SegmentTree<RangeMax> s_max;
+meow::SegmentTree<RangeSum> s_sum;
+
+static int N = 1000000;
+
+std::vector<int> array;
+
+void override(int a, int b, int c){
+  for(int i = a; i <= b; i++)
+    array[i] = c;
+}
+void offset(int a, int b, int c){
+  for(int i = a; i <= b; i++)
+    array[i] += c;
+}
+int bmax(int a, int b){
+  int ret = array[a];
+  for(int i = a + 1; i <= b; i++)
+    ret = std::max(ret, array[i]);
+  return ret;
+}
+int bsum(int a, int b){
+  int sum = 0;
+  for(int i = a; i <= b; i++)
+    sum += array[i];
+  return sum;
+}
+
+void show(){
+  if(N <= 20){
+    printf("\n");
+    printf("Me : ");
+    for(int i = 0; i < N; i++){
+      printf("%4d ", array[i]);
+    }
+    printf("\n");
+    printf("Sum: ");
+    for(int i = 0; i < N; i++){
+      printf("%4d ", s_sum.query(i, i).value);
+    }
+    printf("\n");
+    printf("Max: ");
+    for(int i = 0; i < N; i++){
+      printf("%4d ", s_max.query(i, i).value);
+    }
+    printf("\n");
+  }
+}
+
+TEST(SegmentTree, "..."){
+  s_max.reset(N);
+  s_sum.reset(N);
+  s_max.override(0, N - 1, RangeMax(0));
+  s_sum.override(0, N - 1, RangeSum(0));
+  array.resize(N, 0);
+
+  for(int z = 0; z < 10; z++){
+    meow::messagePrintf(1, "test %d", z);
+    int tMe = 0, tSeg = 0, t0;
+    int NN = 1 + rand() % 100;
+    for(int i = 0; i < NN; i++){
+      int a = rand() % N;
+      int b = rand() % (N - a) + a;
+      int k = rand() % 20000 - 10000;
+      bool over = (rand() % 2 == 1);
+      if(over){
+        t0 = clock();
+        s_max.override(a, b, RangeMax(k));
+        s_sum.override(a, b, RangeSum(k));
+        tSeg += clock() - t0;
+        t0 = clock();
+        override(a, b, k);
+        tMe += clock() - t0;
+      }else{
+        t0 = clock();
+        s_max.offset(a, b, RangeMax(k));
+        s_sum.offset(a, b, RangeSum(k));
+        tSeg = clock() - t0;
+        t0 = clock();
+        offset(a, b, k);
+        tMe += clock() - t0;
+      }
+      /*
+      printf("\n");
+      printf("%s %d~%d with %d", over ? "override" : "offset", a, b, k);
+      show();
+      printf("max:"); s_max.print();
+      printf("sum:"); s_sum.print();
+      // */
+    }
+    NN = 1 + rand() % 100;
+    for(int i = 0; i < NN; i++){
+      int a = rand() % N;
+      int b = rand() % (N - a) + a;
+
+      t0 = clock();
+      RangeMax m(s_max.query(a, b));
+      RangeSum s(s_sum.query(a, b));
+      tSeg += clock() - t0;
+      t0 = clock();
+      int mm = bmax(a, b);
+      int ss = bsum(a, b);
+      tMe += clock() - t0;
+      if(m.value != mm){
+        printf("ask %d~%d, me %d/%d   seg %d/%d\n", a, b, mm, ss, m.value, s.value);
+        meow::messagePrintf(-1, "range-max query fail");
+        return false;
+      }
+      if(s.value != ss){
+        printf("ask %d~%d, max/sum = me %d/%d   seg %d/%d\n", a, b, mm, ss, m.value, s.value);
+        meow::messagePrintf(-1, "range-sum query fail");
+        return false;
+      }
+    }
+    meow::messagePrintf(-1, "ok, %.3f/%.3f",
+                        1.0 * tSeg / CLOCKS_PER_SEC,
+                        1.0 * tMe  / CLOCKS_PER_SEC);
+    s_max.reset(N);
+    s_sum.reset(N);
+    array.clear();
+    array.resize(N, 0);
+  }
+  return true;
+}