blob: e7e146a74b888d79506bd60ad5319bdd9f37fda2 (
plain) (
blame)
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
|
namespace meow{
template<class Value>
inline
BinaryIndexTree<Value>::BinaryIndexTree():
_array(0){
}
template<class Value>
inline
BinaryIndexTree<Value>::BinaryIndexTree(size_t __size, Value const& __value):
_array(__size, __value){
}
template<class Value>
inline
BinaryIndexTree<Value>::BinaryIndexTree(BinaryIndexTree const& __tree2):
_array(__tree2._array){
}
//
template<class Value>
inline void
BinaryIndexTree<Value>::reset(size_t __size, Value const& __init){
_array.clear();
_array.resize(__size, __init);
}
//
template<class Value>
inline void
BinaryIndexTree<Value>::update(size_t __index, Value const& __value){
__index++;
for( ; __index <= _array.size(); __index += (__index & -__index)){
_array[__index - 1] = _array[__index - 1] + __value;
}
}
template<class Value>
inline Value
BinaryIndexTree<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;
}
}
|