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

1 files changed, 59 insertions, 120 deletions

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