diff options
Diffstat (limited to 'meowpp/dsa/SegmentTree.h')
| -rw-r--r-- | meowpp/dsa/SegmentTree.h | 194 |
1 files changed, 0 insertions, 194 deletions
diff --git a/meowpp/dsa/SegmentTree.h b/meowpp/dsa/SegmentTree.h deleted file mode 100644 index 305c4c3..0000000 --- a/meowpp/dsa/SegmentTree.h +++ /dev/null @@ -1,194 +0,0 @@ -#ifndef dsa_SegmentTree_H__ -#define dsa_SegmentTree_H__ - -#include "../math/utility.h" - -#include <vector> -#include <algorithm> - -#include <cstdlib> - -namespace meow { -/*! - * @brief 中文名 \c 線段樹 - * - * 維護一個陣列, 並且讓user可以有區間查詢, 區間修改的小東東 - * - * Template Class Operators Request - * -------------------------------- - * - * |const?|Typename|Operator | Parameters |Return Type | Description | - * |-----:|:------:|----------:|:-------------|:----------:|:------------------| - * |const |Vector |operator[] |(size_t \c n) |Scalar | 取得第 `n` 維度量 | - * |const |Vector |operator< |(Vector \c v) |bool | 權重比較 | - * |const |Scalar |operator* |(Scalar \c s) |Scalar | 相乘 | - * |const |Scalar |operator+ |(Scalar \c s) |Scalar | 相加 | - * |const |Scalar |operator- |(Scalar \c s) |Scalar | 相差 | - * |const |Scalar |operator< |(Scalar \c s) |bool | 大小比較 | - * |const |Value |operator+ |(Value \c v) |Value | 相加(位移) | - * |const |Value |operator* |(size_t \c n) |Value | 每個Value都一樣, - * 長為 `n` 的區間的值| - * |const |Value |operator{b}|(Value \c v) |Value | 區間合併後的值 | - * - * - 若要維護區間最小值, 即每次都是詢問範圍 `[a, b]` 的最小值, 則可以定義 - * - \c operator+ 為 '回傳相加值' - * - \c operator* 為 '回傳*this' - * - \c operator| 為 '回傳std::min(*this, v)' - * - 若要維護區間最總和, 即每次都是詢問範圍 `[a, b]` 的總和, 則可以定義 - * - \c operator+ 為 '回傳相加值' - * - \c operator* 為 '回傳(*this) * n' - * - \c operator| 為 '回傳相加值' - * - * @author cat_leopard - */ -template<class Value> -class SegmentTree { -private: - struct Node { - Value value_; - Value offset_; - bool sameFlage_; - }; - // - size_t size_; - std::vector<Node> nodes_; - // - void update(size_t index, size_t size, Value const& value, bool override) { - if (override) { - nodes_[index].value_ = value * size; - nodes_[index].offset_ = value; - nodes_[index].sameFlage_ = true; - } - else { - nodes_[index].value_ = nodes_[index].value_ + value * size; - nodes_[index].offset_ = nodes_[index].offset_ + value; - } - } - void update(size_t l, size_t r, size_t L, size_t R, - size_t index, Value const& value, - bool override) { - if (l == L && r == R) { - update(index, R - L + 1, value, override); - return ; - } - size_t mid = (L + R) / 2; - if (L < R) { - update(index * 2 + 1, mid - L + 1, - nodes_[index].offset_, nodes_[index].sameFlage_); - update(index * 2 + 2, R - mid, - nodes_[index].offset_, nodes_[index].sameFlage_); - nodes_[index].offset_ = Value(0); - nodes_[index].sameFlage_ = false; - } - if (r <= mid) { - update(l, r, L ,mid, index * 2 + 1, value, override); - } - else if (mid + 1 <= l) { - update(l, r, mid + 1,R, index*2 + 2, value, override); - } - else { - update(l, mid , L, mid , index * 2 + 1, value, override); - update( mid + 1, r, mid + 1, R, index * 2 + 2, value, override); - } - nodes_[index].value_ = ( - (nodes_[index * 2 + 1].value_ | nodes_[index * 2 + 2].value_) - + nodes_[index].offset_ - ); - } - Value query(size_t l, size_t r, size_t L, size_t R, size_t index) { - if (l == L && r == R) return nodes_[index].value_; - Value off = nodes_[index].offset_ * (r - l + 1); - if (nodes_[index].sameFlage_) return off; - size_t mid = (L + R) / 2; - if (r <= mid) return query(l, r, L , mid, index * 2 + 1) + off; - else if(mid + 1 <= l) return query(l, r, mid + 1, R, index * 2 + 2) + off; - else{ - return ( query(l, mid , L, mid , index * 2 + 1) - | query( mid + 1, r, mid + 1, R, index * 2 + 2) - ) + off; - } - } - // - bool rangeCorrect(ssize_t* first, ssize_t* last) const { - if (*last < *first || *last < 0 || (ssize_t)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; - } -public: - //! @brief constructor - SegmentTree() { - reset(1); - } - - //! @brief constructor, with \c size gived - SegmentTree(size_t size) { - reset(size); - } - - //! @brief constructor, 並且複製資料 - SegmentTree(SegmentTree const& tree2): - size_(tree2.size_), nodes_(tree2.nodes_) { - } - - /*! - * @brief 複製 - */ - SegmentTree copyFrom(SegmentTree const& b) { - size_ = b.size_; - nodes_ = b.nodes_; - return *this; - } - - /*! - * @brief 回傳size - */ - size_t size() const { - return size_; - } - - /*! - * @brief 將資料清空且設定維護範圍是 \c 0~size-1 - */ - void reset(size_t size){ - size_ = std::max(size, (size_t)1); - nodes_.resize(size * 4); - nodes_[0].sameFlage_ = true; - nodes_[0].value_ = Value(0); - nodes_[0].offset_ = Value(0); - } - - /*! - * @brief 回傳區間 \c [first,last] (邊界都含) 的區間值 - */ - 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); - } - - /*! - * @brief 將區間 \c [first,last] 全部都設定成 \c value - */ - void 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); - } - - /*! - * @brief 將區間 \c [first,last] 全部都加上 \c delta - */ - void 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); - } - - //! @brief same as copyFrom(b) - SegmentTree& operator=(SegmentTree const& b) { - return copyFrom(b); - } -}; - -} // meow - -#endif // dsa_SegmentTree_H__ |