#ifndef   SegmentTree_H__
#define   SegmentTree_H__

namespace meow{
  //#
  //#=== meow:: *SegmentTree<Value>* (C++ class)
  //#==== Description
  //#  維護一個陣列, 並且讓user可以有區間查詢, 區間修改的小東東
  //#
  //#==== Template Class Operators Request
  //#[options="header",width="70%",cols="1>m,1<,3<s,5<,3<,15<",grid="rows"]
  //#|=====================================================================
  //#|Const?|Typename| Operator  | Parameters |Return_Type| Description
  //#|const |Value   |operator+  |(Value  `v`)|Value      | 相加(位移)
  //#|const |Value   |operator*  |(size_t `n`)|Value      | 每個Value都一樣,
  //#                                                       長為 `n` 的區間的值
  //#|const |Value   |operator{b}|(Value  `v`)|Value      | 區間合併後的值
  //#|=====================================================================
  //#
  //# * 若要維護區間最小值, 即每次都是詢問範圍 `[a, b]` 的最小值, 則可以定義
  //# ** `operator+` 為 '回傳相加值'
  //# ** `operator*` 為 '回傳*this'
  //# ** `operator|` 為 '回傳std::min(*this, v)'
  //# * 若要維護區間最總和, 即每次都是詢問範圍 `[a, b]` 的總和, 則可以定義
  //# ** `operator+` 為 '回傳相加值'
  //# ** `operator*` 為 '回傳(*this) * n'
  //# ** `operator|` 為 '回傳相加值'
  //#
  template<class Value>
  class SegmentTree{
    private:
      struct Node{
        Value _value;
        Value _offset;
        bool  _sameFlag;
      };
      //
      size_t            _size;
      std::vector<Node> _nodes;
      //
      void update(size_t __index, size_t __size, Value const& __value,
                  bool __override);
      void update(size_t __l, size_t __r, size_t __L, size_t __R,
                  size_t __index, Value const& __value,
                  bool   __override);
      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);
      //
      //#==== Support Methods
      //#
      //# * N <- `this` 所維護的陣列長度
      //#
      //#[options="header",width="100%",cols="1>m,2>s,7<,3<,3^,20<",grid="rows"]
      //#|=====================================================================
      //#|Const?|Name | Parameters   | Return_Type| Time_Complexity| Description
      
      
      //#||reset|(size_t `size`)|void|O(1)
      //#|將資料清空且設定維護範圍是 `0~size - 1` 其中時間複雜度確切多少未知
      //# 要看 `std::vector::resize()` 的效率
      void reset(size_t __size);
      
      
      //#|const|query|(ssize_t `first`,\ssize_t `last`)|Value|O(logN)
      //#|回傳區間 `[first,last]` (邊界都含) 的區間值
      Value query   (ssize_t __first, ssize_t __last) const;
      
      
      //#||override|(ssize_t `first`,\ssize_t `last`,\Value const& `value`)
      //#|void|O(logN)
      //#|將區間 `[first,last]` 全部都設定成 `value`
      void  override(ssize_t __first, ssize_t __last, Value const& __value);
      
      
      //#||offset|(ssize_t `first`,\ssize_t `last`,\Value const& `delta`)
      //#|void|O(logN)
      //#|將區間 `[first,last]` 全部都加上 `delta`
      void  offset  (ssize_t __first, ssize_t __last, Value const& __delta);
      
      //
      void print(){
        for(int i = 0; i < _size; i++){
          query(i, i);
        }
        printf("\n");
        for(int depth = 0, count = 1, size = _size, id = 0;
            size > 0;
            depth++, count *= 2, size /= 2){
          for(int j = 0; j < count; j++, id++){
            printf("[%3d%c%3d%*s]",
                   _nodes[id]._value.value,
                   _nodes[id]._sameFlag ? 's' : ' ',
                   _nodes[id]._offset.value,
                   size * 9 - 9,
                   "");
          }
          printf("\n");
        }
      }
      
    //#|=====================================================================
  };
  //#
  //# '''
  //#
}

#include "SegmentTree.hpp"

#endif