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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
|
\hypertarget{classmeow_1_1BinaryIndexTree}{\section{meow\-:\-:Binary\-Index\-Tree$<$ Value $>$ Class Template Reference}
\label{classmeow_1_1BinaryIndexTree}\index{meow\-::\-Binary\-Index\-Tree$<$ Value $>$@{meow\-::\-Binary\-Index\-Tree$<$ Value $>$}}
}
極度簡化的 {\ttfamily \hyperlink{classmeow_1_1SegmentTree}{Segment\-Tree}} 已無區間更新的操作
{\ttfamily \#include \char`\"{}Binary\-Index\-Tree.\-h\char`\"{}}
\subsection*{Public Member Functions}
\begin{DoxyCompactItemize}
\item
\hyperlink{classmeow_1_1BinaryIndexTree_afe34f33091c5c8267f1d219ff40824c4}{Binary\-Index\-Tree} ()
\begin{DoxyCompactList}\small\item\em constructor \end{DoxyCompactList}\item
\hyperlink{classmeow_1_1BinaryIndexTree_a355a4eacbfbe2112720d529efdbad021}{Binary\-Index\-Tree} (size\-\_\-t size, Value const \&value)
\begin{DoxyCompactList}\small\item\em constructor \end{DoxyCompactList}\item
\hyperlink{classmeow_1_1BinaryIndexTree_a8323caade12e478be1e47b7612a60b8f}{Binary\-Index\-Tree} (\hyperlink{classmeow_1_1BinaryIndexTree}{Binary\-Index\-Tree} const \&tree2)
\begin{DoxyCompactList}\small\item\em constructor \end{DoxyCompactList}\item
void \hyperlink{classmeow_1_1BinaryIndexTree_a5634a9420ee864860bbf8605b9e17c32}{reset} (size\-\_\-t size, Value const \&init)
\begin{DoxyCompactList}\small\item\em 將資料洗掉, 重設 \end{DoxyCompactList}\item
void \hyperlink{classmeow_1_1BinaryIndexTree_a3a4f1799b20d5dab24d8cc584db5d32d}{update} (size\-\_\-t index, Value const \&value)
\begin{DoxyCompactList}\small\item\em 將array中第 {\itshape index} (從零算起)個element多加上指定的值 \end{DoxyCompactList}\item
Value \hyperlink{classmeow_1_1BinaryIndexTree_a99f7d954c32c0292a9dda4b74abe5833}{query} (ssize\-\_\-t index) const
\begin{DoxyCompactList}\small\item\em 詢問 {\itshape 0$\sim$index} 的區間值 \end{DoxyCompactList}\end{DoxyCompactItemize}
\subsection{Detailed Description}
\subsubsection*{template$<$class Value$>$class meow\-::\-Binary\-Index\-Tree$<$ Value $>$}
極度簡化的 {\ttfamily \hyperlink{classmeow_1_1SegmentTree}{Segment\-Tree}} 已無區間更新的操作
一般來說只能用在維護區間總和, 維護區間最大值只有在特殊情況才可以, 即 {\bfseries 針對每個元素}, {\bfseries 每次update()} {\bfseries 的值一定會大於等於原本的值} . 若要用區間最大值 , 則 {\itshape Value} 的 {\ttfamily operator+} 要寫成 {\ttfamily std\-::max}(...)
\begin{DoxyAuthor}{Author}
cat\-\_\-leopard
\end{DoxyAuthor}
\subsection{Constructor \& Destructor Documentation}
\hypertarget{classmeow_1_1BinaryIndexTree_afe34f33091c5c8267f1d219ff40824c4}{\index{meow\-::\-Binary\-Index\-Tree@{meow\-::\-Binary\-Index\-Tree}!Binary\-Index\-Tree@{Binary\-Index\-Tree}}
\index{Binary\-Index\-Tree@{Binary\-Index\-Tree}!meow::BinaryIndexTree@{meow\-::\-Binary\-Index\-Tree}}
\subsubsection[{Binary\-Index\-Tree}]{\setlength{\rightskip}{0pt plus 5cm}template$<$class Value $>$ {\bf meow\-::\-Binary\-Index\-Tree}$<$ Value $>$\-::{\bf Binary\-Index\-Tree} (
\begin{DoxyParamCaption}
{}
\end{DoxyParamCaption}
)\hspace{0.3cm}{\ttfamily [inline]}}}\label{classmeow_1_1BinaryIndexTree_afe34f33091c5c8267f1d219ff40824c4}
constructor
\hypertarget{classmeow_1_1BinaryIndexTree_a355a4eacbfbe2112720d529efdbad021}{\index{meow\-::\-Binary\-Index\-Tree@{meow\-::\-Binary\-Index\-Tree}!Binary\-Index\-Tree@{Binary\-Index\-Tree}}
\index{Binary\-Index\-Tree@{Binary\-Index\-Tree}!meow::BinaryIndexTree@{meow\-::\-Binary\-Index\-Tree}}
\subsubsection[{Binary\-Index\-Tree}]{\setlength{\rightskip}{0pt plus 5cm}template$<$class Value $>$ {\bf meow\-::\-Binary\-Index\-Tree}$<$ Value $>$\-::{\bf Binary\-Index\-Tree} (
\begin{DoxyParamCaption}
\item[{size\-\_\-t}]{size, }
\item[{Value const \&}]{value}
\end{DoxyParamCaption}
)\hspace{0.3cm}{\ttfamily [inline]}}}\label{classmeow_1_1BinaryIndexTree_a355a4eacbfbe2112720d529efdbad021}
constructor
\begin{DoxyParams}[1]{Parameters}
\mbox{\tt in} & {\em size} & 要維護的區間大小 {\bfseries }\mbox{[}0,size) \\
\hline
\mbox{\tt in} & {\em value} & 預設值 \\
\hline
\end{DoxyParams}
\hypertarget{classmeow_1_1BinaryIndexTree_a8323caade12e478be1e47b7612a60b8f}{\index{meow\-::\-Binary\-Index\-Tree@{meow\-::\-Binary\-Index\-Tree}!Binary\-Index\-Tree@{Binary\-Index\-Tree}}
\index{Binary\-Index\-Tree@{Binary\-Index\-Tree}!meow::BinaryIndexTree@{meow\-::\-Binary\-Index\-Tree}}
\subsubsection[{Binary\-Index\-Tree}]{\setlength{\rightskip}{0pt plus 5cm}template$<$class Value $>$ {\bf meow\-::\-Binary\-Index\-Tree}$<$ Value $>$\-::{\bf Binary\-Index\-Tree} (
\begin{DoxyParamCaption}
\item[{{\bf Binary\-Index\-Tree}$<$ Value $>$ const \&}]{tree2}
\end{DoxyParamCaption}
)\hspace{0.3cm}{\ttfamily [inline]}}}\label{classmeow_1_1BinaryIndexTree_a8323caade12e478be1e47b7612a60b8f}
constructor
將另一個 {\ttfamily \hyperlink{classmeow_1_1BinaryIndexTree}{Binary\-Index\-Tree}} 原封不動的複製過來
\begin{DoxyParams}[1]{Parameters}
\mbox{\tt in} & {\em tree2} & 另外一個 {\ttfamily \hyperlink{classmeow_1_1BinaryIndexTree}{Binary\-Index\-Tree}} \\
\hline
\end{DoxyParams}
\subsection{Member Function Documentation}
\hypertarget{classmeow_1_1BinaryIndexTree_a99f7d954c32c0292a9dda4b74abe5833}{\index{meow\-::\-Binary\-Index\-Tree@{meow\-::\-Binary\-Index\-Tree}!query@{query}}
\index{query@{query}!meow::BinaryIndexTree@{meow\-::\-Binary\-Index\-Tree}}
\subsubsection[{query}]{\setlength{\rightskip}{0pt plus 5cm}template$<$class Value $>$ Value {\bf meow\-::\-Binary\-Index\-Tree}$<$ Value $>$\-::query (
\begin{DoxyParamCaption}
\item[{ssize\-\_\-t}]{index}
\end{DoxyParamCaption}
) const\hspace{0.3cm}{\ttfamily [inline]}}}\label{classmeow_1_1BinaryIndexTree_a99f7d954c32c0292a9dda4b74abe5833}
詢問 {\itshape 0$\sim$index} 的區間值
時間複雜度{\bfseries O(log\-N)}
\begin{DoxyParams}[1]{Parameters}
\mbox{\tt in} & {\em index} & 指定的index \\
\hline
\end{DoxyParams}
\begin{DoxyReturn}{Returns}
區間值
\end{DoxyReturn}
\hypertarget{classmeow_1_1BinaryIndexTree_a5634a9420ee864860bbf8605b9e17c32}{\index{meow\-::\-Binary\-Index\-Tree@{meow\-::\-Binary\-Index\-Tree}!reset@{reset}}
\index{reset@{reset}!meow::BinaryIndexTree@{meow\-::\-Binary\-Index\-Tree}}
\subsubsection[{reset}]{\setlength{\rightskip}{0pt plus 5cm}template$<$class Value $>$ void {\bf meow\-::\-Binary\-Index\-Tree}$<$ Value $>$\-::reset (
\begin{DoxyParamCaption}
\item[{size\-\_\-t}]{size, }
\item[{Value const \&}]{init}
\end{DoxyParamCaption}
)\hspace{0.3cm}{\ttfamily [inline]}}}\label{classmeow_1_1BinaryIndexTree_a5634a9420ee864860bbf8605b9e17c32}
將資料洗掉, 重設
時間複雜度{\bfseries O(\-N)}
\begin{DoxyParams}[1]{Parameters}
\mbox{\tt in} & {\em size} & 要維護的區間大小 {\bfseries }\mbox{[}0,size) \\
\hline
\mbox{\tt in} & {\em init} & 預設值 \\
\hline
\end{DoxyParams}
\begin{DoxyReturn}{Returns}
無
\end{DoxyReturn}
\hypertarget{classmeow_1_1BinaryIndexTree_a3a4f1799b20d5dab24d8cc584db5d32d}{\index{meow\-::\-Binary\-Index\-Tree@{meow\-::\-Binary\-Index\-Tree}!update@{update}}
\index{update@{update}!meow::BinaryIndexTree@{meow\-::\-Binary\-Index\-Tree}}
\subsubsection[{update}]{\setlength{\rightskip}{0pt plus 5cm}template$<$class Value $>$ void {\bf meow\-::\-Binary\-Index\-Tree}$<$ Value $>$\-::update (
\begin{DoxyParamCaption}
\item[{size\-\_\-t}]{index, }
\item[{Value const \&}]{value}
\end{DoxyParamCaption}
)\hspace{0.3cm}{\ttfamily [inline]}}}\label{classmeow_1_1BinaryIndexTree_a3a4f1799b20d5dab24d8cc584db5d32d}
將array中第 {\itshape index} (從零算起)個element多加上指定的值
時間複雜度{\bfseries O(log\-N)}
\begin{DoxyParams}[1]{Parameters}
\mbox{\tt in} & {\em index} & 指定的index \\
\hline
\mbox{\tt in} & {\em value} & 指定的值 \\
\hline
\end{DoxyParams}
\begin{DoxyReturn}{Returns}
無
\end{DoxyReturn}
The documentation for this class was generated from the following file\-:\begin{DoxyCompactItemize}
\item
meowpp/dsa/\hyperlink{BinaryIndexTree_8h}{Binary\-Index\-Tree.\-h}\end{DoxyCompactItemize}
|
