path: root/meowpp/dsa/SegmentTree.hpp

#include "../utility.h"

#include <algorithm>

namespace meow{
  
  template<class Value>
  inline void
  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{
      _nodes[__i]._value  = _nodes[__i]._value  + __value * __size;
      _nodes[__i]._offset = _nodes[__i]._offset + __value;
    }
  }
  template<class Value>
  inline void
  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){
      update(__i, __R - __L + 1, __value, __over);
      return ;
    }
    size_t mid = (__L + __R) / 2;
    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[__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 __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;
    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 || *__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(){ reset(1); }
  template<class Value>
  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){ }
  //
  template<class Value>
  inline void
  SegmentTree<Value>::reset(size_t __size){
    _size = std::max(__size, (size_t)1);
    _nodes.resize(__size * 4);
    _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, 0);
  }
  template<class Value>
  inline void
  SegmentTree<Value>::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);
  }
  template<class Value>
  inline void
  SegmentTree<Value>::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);
  }
}