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
|
#ifndef __BinaryIndexTree_H__
#define __BinaryIndexTree_H__
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(...)`
//#========================================
//#
//# '''
}
#include "BinaryIndexTree.hpp"
#endif // BinaryIndexTree_H__
|
