path: root/meowpp/dsa/SegmentTree.hpp

#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