#ifndef   dsa_BinaryIndexTree_H__
#define   dsa_BinaryIndexTree_H__

#include <cstdlib>

#include <vector>
#include <algorithm>

namespace meow {

template<class Value>
/*!
 * @brief 極度簡化的 \c SegmentTree 已無區間更新的操作
 *
 * 一般來說只能用在維護區間總和, 維護區間最大值只有在特殊情況才可以, 即
 * \b 針對每個元素, \b 每次update() \b 的值一定會大於等於原本的值 .
 * 若要用區間最大值 , 則 \a Value 的 \c operator+  要寫成 \c std::max(...)
 *
 * @author cat_leopard
 */
class BinaryIndexTree {
private:
  std::vector<Value> array_;
public:
  /*!
   * @brief constructor
   */
  BinaryIndexTree() {
  }

  /*!
   * @brief constructor
   *
   * @param [in] size 要維護的區間大小 \b [0,size)
   * @param [in] value 預設值
   */
  BinaryIndexTree(size_t size, Value const& value):
  array_(size, value) {
  }

  /*!
   * @brief constructor
   *
   * 將另一個 \c BinaryIndexTree 原封不動的複製過來
   * @param [in] tree2 另外一個 \c BinaryIndexTree
   */
  BinaryIndexTree(BinaryIndexTree const& tree2):
  array_(tree2.array_) {
  }

  /*!
   * @brief 將資料洗掉, 重設
   *
   * 時間複雜度\b O(N)
   *
   * @param [in] size 要維護的區間大小 \b [0,size)
   * @param [in] init 預設值
   * @return 無
   */
  void reset(size_t size, Value const& init) {
    array_.clear();
    array_.resize(size, init);
  }

  /*!
   * @brief 將array中第 \a index (從零算起)個element多加上指定的值
   *
   * 時間複雜度\b O(logN)
   *
   * @param [in] index 指定的index
   * @param [in] value 指定的值
   * @return 無
   */
  void update(size_t index, Value const& value) {
    index++;
    for ( ; index <= array_.size(); index += (index & -index)) {
      array_[index - 1] = array_[index - 1] + value;
    }
  }


  /*!
   * @brief 詢問 \a 0~index 的區間值
   *
   * 時間複雜度\b O(logN)
   *
   * @param [in] index 指定的index
   * @return 區間值
   */
  Value query(ssize_t index) const {
    index = std::min(index + 1, (ssize_t)array_.size());
    Value ret(0);
    for ( ; 0 < index; index -= (index & -index)) {
      ret = ret + array_[index - 1];
    }
    return ret;
  }
};

}

#endif // dsa_BinaryIndexTree_H__