diff options
Diffstat (limited to 'meowpp/dsa/SegmentTree.hpp')
| -rw-r--r-- | meowpp/dsa/SegmentTree.hpp | 172 |
1 files changed, 172 insertions, 0 deletions
diff --git a/meowpp/dsa/SegmentTree.hpp b/meowpp/dsa/SegmentTree.hpp new file mode 100644 index 0000000..24efcdd --- /dev/null +++ b/meowpp/dsa/SegmentTree.hpp @@ -0,0 +1,172 @@ +#ifndef SegmentTree_H__ +#define SegmentTree_H__ + +namespace meow{ + template<class Value> + inline SegmentTree<Value>::Node::Node(){ } + + 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; + } + } + 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); + }else{ + override(__l , mid, __L , mid, leftChild(__index), __value); + override(mid + 1, __r, mid + 1, __R, rightChild(__index), __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){ + 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; + } + 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); + } + _nodes[__index]._value = ( _nodes[ leftChild(__index)]._value + | _nodes[rightChild(__index)]._value); + } + 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; + } + 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; + } + } + 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; + } + *__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) { + } + template<class Value> + inline + SegmentTree<Value>::SegmentTree(size_t __size): _size(0), _root(0){ + reset(__size); + } + template<class Value> + inline + SegmentTree<Value>::SegmentTree(SegmentTree const& __tree2): + _size(__tree2._size), _nodes(__tree2._nodes), _root(0){ } + // + template<class Value> + inline void + SegmentTree<Value>::reset(size_t __size){ + _size = __size; + _nodes.resize(__size * 4); + _nodes[_root]._sameFlag = true; + _nodes[_root]._value = 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); + } + 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); + } + 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); + } +} + +#endif |