#ifndef   SegmentTree_H__
#define   SegmentTree_H__

namespace meow{
  template<class Value>
  class SegmentTree{
    private:
      struct Node{
        Value _value;
        Value _offset;
        bool  _sameFlag;
        //
        Node();
      };
      //
      size_t            _size;
      std::vector<Node> _nodes;
      size_t const      _root;
      //
      size_t  leftChild(size_t __parent) const;
      size_t rightChild(size_t __parent) const;
      //
      void downUpdate(size_t __L, size_t __R, size_t __index);
      void override(size_t __l, size_t __r,
                    size_t __L, size_t __R,
                    size_t __index, Value const& __value);
      void offset(size_t __l, size_t __r,
                  size_t __L, size_t __R,
                  size_t __index, Value const& __delta);
      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);
      //
      void reset(size_t __size);
      //
      Value query  (ssize_t __first, ssize_t __last) const;
      void override(ssize_t __first, ssize_t __last, Value const& __value);
      void offset  (ssize_t __first, ssize_t __last, Value const& __delta);
  };
  /*********************************************************
    @asciidoc
    === meow:: *SegmentTree<Value>* (C++ class)
    .Description
    `SegmentTree` is a data structure that can maintain an array, and
    support *range update* , *range query*
    
   .Template Request
   * `Value` should has
   ** `operator+(Value)` offset
   ** `operator|(Value)` merge two nodes
   ** `operator*(size_t)` ??
   
   For example, if you want to maintain *range minimum*
   
   * `Value::operator+(Value v2)` will be `this->realValue + v2.realValue`
   * `Value::operator|(Value v2)` will be `std::min(this->realValue, v2.realValue)`
   * `Value::operator*(size_t n)` will be `this->realValue`
   
   If you want to maintain *range sum*
   
   * `Value::operator+(Value v2)` will be `this->realValue + v2.realValue`
   * `Value::operator|(Value v2)` will be `this->realValue + v2.realValue)`
   * `Value::operator*(size_t n)` will be `this->realValue * n`

    .Support methods
   * N <- array size
   [options="header",width="100%",cols="1>,1<s,3<,1<,1<,10<",grid="rows"]
   |=======================================================================
   |Const?|Name| Parameters| Return Type| Time Complexity| Description
   ||reset|(size_t N)|void|O(1)|
   Clear and reset the array size to N (from `0` to `N - 1`)
   |const|query|(ssize_t __first, ssize_t __last)|Value|O(logN)|
   Range query
   ||override|(ssize_t __first, ssize_t __last, Value const& __value)|void|
   O(logN)| Let the element in the array index from `__first` to `__last`
   be `__value`
   ||offset|(ssize_t __first, ssize_t __last, Value const& __value)|void|
   O(logN)| Let the element in the array index from `__first` to `__last`
   plus `__value`
   |=======================================================================

'''
@asciidoc-
   *********************************************************/
}

#endif