1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
|
#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;
}
};
} // meow
#endif // dsa_BinaryIndexTree_H__
|
