big chnage

1 files changed, 184 insertions, 90 deletions

diff --git a/meowpp/dsa/SegmentTree.h b/meowpp/dsa/SegmentTree.h
index 52d5a6f..b2fa749 100644
--- a/meowpp/dsa/SegmentTree.h
+++ b/meowpp/dsa/SegmentTree.h
@@ -1,100 +1,194 @@
 #ifndef   dsa_SegmentTree_H__
 #define   dsa_SegmentTree_H__
 
-#include <cstdlib>
+#include "../math/utility.h"
 
 #include <vector>
+#include <algorithm>
+
+#include <cstdlib>
 
-namespace meow{
-  //#
-  //#=== meow:: *SegmentTree<Value>* (C++ class)
-  //#==== Description
-  //#  維護一個陣列, 並且讓user可以有區間查詢, 區間修改的小東東
-  //#
-  //#==== 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 |Value   |operator+  |(Value  `v`)|Value      | 相加(位移)
-  //#|const |Value   |operator*  |(size_t `n`)|Value      | 每個Value都一樣,
-  //#                                                       長為 `n` 的區間的值
-  //#|const |Value   |operator{b}|(Value  `v`)|Value      | 區間合併後的值
-  //#|=====================================================================
-  //#
-  //# * 若要維護區間最小值, 即每次都是詢問範圍 `[a, b]` 的最小值, 則可以定義
-  //# ** `operator+` 為 '回傳相加值'
-  //# ** `operator*` 為 '回傳*this'
-  //# ** `operator|` 為 '回傳std::min(*this, v)'
-  //# * 若要維護區間最總和, 即每次都是詢問範圍 `[a, b]` 的總和, 則可以定義
-  //# ** `operator+` 為 '回傳相加值'
-  //# ** `operator*` 為 '回傳(*this) * n'
-  //# ** `operator|` 為 '回傳相加值'
-  //#
-  template<class Value>
-  class SegmentTree{
-    private:
-      struct Node{
-        Value _value;
-        Value _offset;
-        bool  _sameFlag;
-      };
-      //
-      size_t            _size;
-      std::vector<Node> _nodes;
-      //
-      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();
-      SegmentTree(size_t __size);
-      SegmentTree(SegmentTree const& __tree2);
-      //
-      //#==== Support Methods
-      //#
-      //# * N <- `this` 所維護的陣列長度
-      //#
-      //#[options="header",width="100%",cols="1>m,2>s,7<,3<,3^,20<",grid="rows"]
-      //#|=====================================================================
-      //#|Const?|Name | Parameters   | Return_Type| Time_Complexity| Description
-      
-      
-      //#||reset|(size_t `size`)|void|O(1)
-      //#|將資料清空且設定維護範圍是 `0~size - 1` 其中時間複雜度確切多少未知
-      //# 要看 `std::vector::resize()` 的效率
-      void reset(size_t __size);
-      
-      
-      //#|const|query|(ssize_t `first`,\ssize_t `last`)|Value|O(logN)
-      //#|回傳區間 `[first,last]` (邊界都含) 的區間值
-      Value query   (ssize_t __first, ssize_t __last) const;
-      
-      
-      //#||override|(ssize_t `first`,\ssize_t `last`,\Value const& `value`)
-      //#|void|O(logN)
-      //#|將區間 `[first,last]` 全部都設定成 `value`
-      void  override(ssize_t __first, ssize_t __last, Value const& __value);
-      
-      
-      //#||offset|(ssize_t `first`,\ssize_t `last`,\Value const& `delta`)
-      //#|void|O(logN)
-      //#|將區間 `[first,last]` 全部都加上 `delta`
-      void  offset  (ssize_t __first, ssize_t __last, Value const& __delta);
-      
-      
-      //#|=====================================================================
+namespace meow {
+/*!
+ * @brief 中文名 \c 線段樹
+ *
+ * 維護一個陣列, 並且讓user可以有區間查詢, 區間修改的小東東
+ *
+ * Template Class Operators Request
+ * --------------------------------
+ *
+ * |const?|Typename|Operator   | Parameters   |Return Type | Description       |
+ * |-----:|:------:|----------:|:-------------|:----------:|:------------------|
+ * |const |Vector  |operator[] |(size_t \c n) |Scalar      | 取得第 `n` 維度量 |
+ * |const |Vector  |operator<  |(Vector \c v) |bool        | 權重比較          |
+ * |const |Scalar  |operator*  |(Scalar \c s) |Scalar      | 相乘              |
+ * |const |Scalar  |operator+  |(Scalar \c s) |Scalar      | 相加              |
+ * |const |Scalar  |operator-  |(Scalar \c s) |Scalar      | 相差              |
+ * |const |Scalar  |operator<  |(Scalar \c s) |bool        | 大小比較          |
+ * |const |Value   |operator+  |(Value  \c v) |Value       | 相加(位移)        |
+ * |const |Value   |operator*  |(size_t \c n) |Value       | 每個Value都一樣,
+ *                                                          長為 `n` 的區間的值|
+ * |const |Value   |operator{b}|(Value  \c v) |Value       | 區間合併後的值    |
+ *
+ * - 若要維護區間最小值, 即每次都是詢問範圍 `[a, b]` 的最小值, 則可以定義
+ *      - \c operator+ 為 '回傳相加值'
+ *      - \c operator* 為 '回傳*this'
+ *      - \c operator| 為 '回傳std::min(*this, v)'
+ * - 若要維護區間最總和, 即每次都是詢問範圍 `[a, b]` 的總和, 則可以定義
+ *      - \c operator+ 為 '回傳相加值'
+ *      - \c operator* 為 '回傳(*this) * n'
+ *      - \c operator| 為 '回傳相加值' 
+ *
+ * @author cat_leopard
+ */
+template<class Value>
+class SegmentTree {
+private:
+  struct Node {
+    Value     value_;
+    Value    offset_;
+    bool  sameFlage_;
   };
-  //#
-  //# '''
-  //#
-}
+  //
+  size_t             size_;
+  std::vector<Node> nodes_;
+  //
+  void update(size_t index, size_t size, Value const& value, bool override) {
+    if (override) {
+      nodes_[index].value_    = value * size;
+      nodes_[index].offset_   = value;
+      nodes_[index].sameFlage_ = true;
+    }
+    else {
+      nodes_[index].value_  = nodes_[index].value_  + value * size;
+      nodes_[index].offset_ = nodes_[index].offset_ + value;
+    }
+  }
+  void update(size_t l, size_t r, size_t L, size_t R,
+              size_t index, Value const& value,
+              bool override) {
+    if (l == L && r == R) {
+      update(index, R - L + 1, value, override);
+      return ;
+    }
+    size_t mid = (L + R) / 2;
+    if (L < R) {
+      update(index * 2 + 1, mid - L + 1,
+             nodes_[index].offset_, nodes_[index].sameFlage_);
+      update(index * 2 + 2, R - mid,
+             nodes_[index].offset_, nodes_[index].sameFlage_);
+      nodes_[index].offset_ = Value(0);
+      nodes_[index].sameFlage_ = false;
+    }
+    if (r <= mid) {
+      update(l, r, L ,mid, index * 2 + 1, value, override);
+    }
+    else if (mid + 1 <= l) {
+      update(l, r, mid + 1,R, index*2 + 2, value, override);
+    }
+    else {
+      update(l, mid       , L, mid       , index * 2 + 1, value, override);
+      update(   mid + 1, r,    mid + 1, R, index * 2 + 2, value, override);
+    }
+    nodes_[index].value_ = (
+      (nodes_[index * 2 + 1].value_ | nodes_[index * 2 + 2].value_)
+      + nodes_[index].offset_
+    );
+  }
+  Value query(size_t l, size_t r, size_t L, size_t R, size_t index) {
+    if (l == L && r == R) return nodes_[index].value_;
+    Value off = nodes_[index].offset_ * (r - l + 1);
+    if (nodes_[index].sameFlage_) return off;
+    size_t mid = (L + R) / 2;
+    if     (r       <= mid) return query(l, r, L   ,  mid, index * 2 + 1) + off;
+    else if(mid + 1 <=   l) return query(l, r, mid + 1, R, index * 2 + 2) + off;
+    else{
+      return (  query(l, mid       , L,  mid       , index * 2 + 1)
+              | query(   mid + 1, r,     mid + 1, R, index * 2 + 2)
+      ) + off;
+    }
+  }
+  //
+  bool rangeCorrect(ssize_t* first, ssize_t* last) const {
+    if (*last < *first || *last < 0 || (ssize_t)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;
+  }
+public:
+  //! @brief constructor
+  SegmentTree() {
+    reset(1);
+  }
+
+  //! @brief constructor, with \c size gived
+  SegmentTree(size_t size) {
+    reset(size);
+  }
+
+  //! @brief constructor, 並且複製資料
+  SegmentTree(SegmentTree const& tree2):
+  size_(tree2.size_), nodes_(tree2.nodes_) {
+  }
 
-#include "SegmentTree.hpp"
+  /*!
+   * @brief 複製
+   */
+  SegmentTree copyFrom(SegmentTree const& b) {
+    size_  = b.size_;
+    nodes_ = b.nodes_;
+    return *this;
+  }
+  
+  /*!
+   * @brief 回傳size
+   */
+  size_t size() const {
+    return size_;
+  }
+
+  /*!
+   * @brief 將資料清空且設定維護範圍是 \c 0~size-1
+   */
+  void reset(size_t size){
+    size_ = std::max(size, (size_t)1);
+    nodes_.resize(size * 4);
+    nodes_[0].sameFlage_ = true;
+    nodes_[0].value_  = Value(0);
+    nodes_[0].offset_ = Value(0);
+  }
+
+  /*!
+   * @brief 回傳區間 \c [first,last] (邊界都含) 的區間值
+   */
+  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, 0);
+  }
+
+  /*!
+   * @brief 將區間 \c [first,last] 全部都設定成 \c value
+   */
+  void override(ssize_t first, ssize_t last, Value const& value) {
+    if (rangeCorrect(&first, &last) == false) return ;
+    update(first, last, 0, size_ - 1, 0, value, true);
+  }
+
+  /*!
+   * @brief 將區間 \c [first,last] 全部都加上 \c delta
+   */
+  void offset(ssize_t first, ssize_t last, Value const& delta) {
+    if (rangeCorrect(&first, &last) == false) return ;
+    update(first, last, 0, size_ - 1, 0, delta, false);
+  }
+  
+  //! @brief same as copyFrom(b)
+  SegmentTree& operator=(SegmentTree const& b) {
+    return copyFrom(b);
+  }
+};
+
+}
 
 #endif // dsa_SegmentTree_H__