1 files changed, 92 insertions, 0 deletions
diff --git a/meowpp/dsa/SegmentTree.h b/meowpp/dsa/SegmentTree.h
new file mode 100644
index 0000000..1aa396d
--- /dev/null
+++ b/meowpp/dsa/SegmentTree.h
@@ -0,0 +1,92 @@
+#ifndef   SegmentTree_H__
+#define   SegmentTree_H__
+
+namespace meow{
+  template<class Value>
+  class SegmentTree{
+    private:
+      struct Node{
+        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,
+                  size_t __index);
+      bool rangeCorrect(ssize_t* __first, ssize_t* __last) const;
+    public:
+      SegmentTree();
+      SegmentTree(size_t __size);
+      SegmentTree(SegmentTree const& __tree2);
+      //
+      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);
+  };
+  /*********************************************************
+    @asciidoc
+    === meow:: *SegmentTree<Value>* (C++ class)
+    .Description
+    `SegmentTree` is a data structure that can maintain an array, and
+    support *range update* , *range query*
+    
+   .Template Request
+   * `Value` should has
+   ** `operator+(Value)` offset
+   ** `operator|(Value)` merge two nodes
+   ** `operator*(size_t)` ??
+   
+   For example, if you want to maintain *range minimum*
+   
+   * `Value::operator+(Value v2)` will be `this->realValue + v2.realValue`
+   * `Value::operator|(Value v2)` will be `std::min(this->realValue, v2.realValue)`
+   * `Value::operator*(size_t n)` will be `this->realValue`
+   
+   If you want to maintain *range sum*
+   
+   * `Value::operator+(Value v2)` will be `this->realValue + v2.realValue`
+   * `Value::operator|(Value v2)` will be `this->realValue + v2.realValue)`
+   * `Value::operator*(size_t n)` will be `this->realValue * n`
+
+    .Support methods
+   * N <- array size
+   [options="header",width="100%",cols="1>,1<s,3<,1<,1<,10<",grid="rows"]
+   |=======================================================================
+   |Const?|Name| Parameters| Return Type| Time Complexity| Description
+   ||reset|(size_t N)|void|O(1)|
+   Clear and reset the array size to N (from `0` to `N - 1`)
+   |const|query|(ssize_t __first, ssize_t __last)|Value|O(logN)|
+   Range query
+   ||override|(ssize_t __first, ssize_t __last, Value const& __value)|void|
+   O(logN)| Let the element in the array index from `__first` to `__last`
+   be `__value`
+   ||offset|(ssize_t __first, ssize_t __last, Value const& __value)|void|
+   O(logN)| Let the element in the array index from `__first` to `__last`
+   plus `__value`
+   |=======================================================================
+
+'''
+@asciidoc-
+   *********************************************************/
+}
+
+#endif