diff options
Diffstat (limited to 'meowpp/dsa/BinaryIndexTree.h')
| -rw-r--r-- | meowpp/dsa/BinaryIndexTree.h | 155 |
1 files changed, 92 insertions, 63 deletions
diff --git a/meowpp/dsa/BinaryIndexTree.h b/meowpp/dsa/BinaryIndexTree.h index 36f24d7..5525c62 100644 --- a/meowpp/dsa/BinaryIndexTree.h +++ b/meowpp/dsa/BinaryIndexTree.h @@ -4,70 +4,99 @@ #include <cstdlib> #include <vector> +#include <algorithm> -namespace meow{ - //# - //#=== meow:: *BinaryIndexTree<Value>* (C++ class) - //#==== Description - //# 極度簡化版的 `SegmentTree` 已無法區間操作, 區間詢問的區間開頭也一定要 - //# 在 `index=0` 的地方 - //# - //#==== 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 `n`) | Value | 合併用(類似 - //# `SegmentTree` 的 - //# operator{b} ) - //#|===================================================================== - //# - template<class Value> - class BinaryIndexTree{ - private: - std::vector<Value> _array; - public: - BinaryIndexTree(); - BinaryIndexTree(size_t __size, Value const& __value); - BinaryIndexTree(BinaryIndexTree const& __tree2); - - //#==== Support Methods - //# - //# * N <- `this` 中擁有的資料數 - //# - //#[options="header",width="100%",cols="1>m,3>s,7<,3<,3^,20<",grid="rows"] - //#|===================================================================== - //#|Const?|Name | Parameters | Return_Type| Time_Complexity| Description - - - //#||reset|(size_t `size`, Value const& `value`)|void|O(`size`) - //#|將資料長度刷成 `N = size` 且每一個元素都是 `value` - void reset(size_t __size, Value const& __value); - - - //#||update|(size_t `index`, Value const& `value`)|void|O(logN) - //#|將第 `index` (從零開始算) 多加上 `value` - void update( size_t __index, Value const& __value); - - - //#|const|query|(size_t `index`)|void|O(logN) - //#|詢問 `0~index` 的區間值 - Value query (ssize_t __index) const; - - - //#|===================================================================== - }; - //# - //#[NOTE] - //#======================================== - //# * 一般來說只能用在維護區間總和, 維護區間最大值只有在特殊情況才可以, 即 - //# '針對每個元素, 每次 update() 的值一定會大於等於原本的值' - //# * 若要用區間最大值 , 則 `Value` 的 `operator+` 要寫成 `std::max(...)` - //#======================================== - //# - //# ''' -} +namespace meow { -#include "BinaryIndexTree.hpp" +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() { + } -#endif // dsa_BinaryIndexTree_H__ + /*! + * @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__ |