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
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
|
\hypertarget{classmeow_1_1SegmentTree}{\section{meow\-:\-:Segment\-Tree$<$ Value $>$ Class Template Reference}
\label{classmeow_1_1SegmentTree}\index{meow\-::\-Segment\-Tree$<$ Value $>$@{meow\-::\-Segment\-Tree$<$ Value $>$}}
}
中文名 {\ttfamily 線段樹}
{\ttfamily \#include \char`\"{}Segment\-Tree.\-h\char`\"{}}
\subsection*{Public Member Functions}
\begin{DoxyCompactItemize}
\item
\hyperlink{classmeow_1_1SegmentTree_a8e8365f0440c68f3c0853b94a7de3ccb}{Segment\-Tree} ()
\begin{DoxyCompactList}\small\item\em constructor \end{DoxyCompactList}\item
\hyperlink{classmeow_1_1SegmentTree_a1fe904372d3cdd01f07a1c88f86b14a1}{Segment\-Tree} (size\-\_\-t \hyperlink{classmeow_1_1SegmentTree_a8985a196cfb954bc469e7dae146ad4ed}{size})
\begin{DoxyCompactList}\small\item\em constructor, with {\ttfamily size} gived \end{DoxyCompactList}\item
\hyperlink{classmeow_1_1SegmentTree_a12a47cdf24eacb80d0bad4010f6a2953}{Segment\-Tree} (\hyperlink{classmeow_1_1SegmentTree}{Segment\-Tree} const \&tree2)
\begin{DoxyCompactList}\small\item\em constructor, 並且複製資料 \end{DoxyCompactList}\item
\hyperlink{classmeow_1_1SegmentTree}{Segment\-Tree} \hyperlink{classmeow_1_1SegmentTree_a889f38048ffe08ce3c80911878faac44}{copy\-From} (\hyperlink{classmeow_1_1SegmentTree}{Segment\-Tree} const \&b)
\begin{DoxyCompactList}\small\item\em 複製 \end{DoxyCompactList}\item
size\-\_\-t \hyperlink{classmeow_1_1SegmentTree_a8985a196cfb954bc469e7dae146ad4ed}{size} () const
\begin{DoxyCompactList}\small\item\em 回傳size \end{DoxyCompactList}\item
void \hyperlink{classmeow_1_1SegmentTree_a80c550b0a3b997bc541ae0947ae2f55d}{reset} (size\-\_\-t \hyperlink{classmeow_1_1SegmentTree_a8985a196cfb954bc469e7dae146ad4ed}{size})
\begin{DoxyCompactList}\small\item\em 將資料清空且設定維護範圍是 {\ttfamily 0$\sim$size-\/1} \end{DoxyCompactList}\item
Value \hyperlink{classmeow_1_1SegmentTree_a18bb3667abd9810ce3534af3d70b14d5}{query} (ssize\-\_\-t first, ssize\-\_\-t last) const
\begin{DoxyCompactList}\small\item\em 回傳區間 {\ttfamily }\mbox{[}first,last\mbox{]} (邊界都含) 的區間值 \end{DoxyCompactList}\item
void \hyperlink{classmeow_1_1SegmentTree_a2f300a5fd5ffdd19e4b3efc6899a7439}{override} (ssize\-\_\-t first, ssize\-\_\-t last, Value const \&value)
\begin{DoxyCompactList}\small\item\em 將區間 {\ttfamily }\mbox{[}first,last\mbox{]} 全部都設定成 {\ttfamily value} \end{DoxyCompactList}\item
void \hyperlink{classmeow_1_1SegmentTree_aaeca3de355dc367e2664e83800ee6aa5}{offset} (ssize\-\_\-t first, ssize\-\_\-t last, Value const \&delta)
\begin{DoxyCompactList}\small\item\em 將區間 {\ttfamily }\mbox{[}first,last\mbox{]} 全部都加上 {\ttfamily delta} \end{DoxyCompactList}\item
\hyperlink{classmeow_1_1SegmentTree}{Segment\-Tree} \& \hyperlink{classmeow_1_1SegmentTree_a765e794af604ab7c20a4245dfafcf14c}{operator=} (\hyperlink{classmeow_1_1SegmentTree}{Segment\-Tree} const \&b)
\begin{DoxyCompactList}\small\item\em same as copy\-From(b) \end{DoxyCompactList}\end{DoxyCompactItemize}
\subsection{Detailed Description}
\subsubsection*{template$<$class Value$>$class meow\-::\-Segment\-Tree$<$ Value $>$}
中文名 {\ttfamily 線段樹}
維護一個陣列, 並且讓user可以有區間查詢, 區間修改的小東東
\subsubsection*{Template Class Operators Request}
\begin{TabularC}{6}
\hline
\rowcolor{lightgray}\PBS\raggedleft {\bf const?}&\PBS\centering {\bf Typename}&\PBS\raggedleft {\bf Operator }&{\bf Parameters }&\PBS\centering {\bf Return Type }&{\bf Description }\\\cline{1-6}
\PBS\raggedleft const &\PBS\centering \hyperlink{classmeow_1_1Vector}{Vector} &\PBS\raggedleft operator\mbox{[}\mbox{]} &(size\-\_\-t {\ttfamily n}) &\PBS\centering Scalar &取得第 {\ttfamily n} 維度量 \\\cline{1-6}
\PBS\raggedleft const &\PBS\centering \hyperlink{classmeow_1_1Vector}{Vector} &\PBS\raggedleft operator$<$ &(\hyperlink{classmeow_1_1Vector}{Vector} {\ttfamily v}) &\PBS\centering bool &權重比較 \\\cline{1-6}
\PBS\raggedleft const &\PBS\centering Scalar &\PBS\raggedleft operator$\ast$ &(Scalar {\ttfamily s}) &\PBS\centering Scalar &相乘 \\\cline{1-6}
\PBS\raggedleft const &\PBS\centering Scalar &\PBS\raggedleft operator+ &(Scalar {\ttfamily s}) &\PBS\centering Scalar &相加 \\\cline{1-6}
\PBS\raggedleft const &\PBS\centering Scalar &\PBS\raggedleft operator-\/ &(Scalar {\ttfamily s}) &\PBS\centering Scalar &相差 \\\cline{1-6}
\PBS\raggedleft const &\PBS\centering Scalar &\PBS\raggedleft operator$<$ &(Scalar {\ttfamily s}) &\PBS\centering bool &大小比較 \\\cline{1-6}
\PBS\raggedleft const &\PBS\centering Value &\PBS\raggedleft operator+ &(Value {\ttfamily v}) &\PBS\centering Value &相加(位移) \\\cline{1-6}
\PBS\raggedleft const &\PBS\centering Value &\PBS\raggedleft operator$\ast$ &(size\-\_\-t {\ttfamily n}) &\PBS\centering Value &每個\-Value都一樣, \\\cline{1-6}
\end{TabularC}
長為 {\ttfamily n} 的區間的值$|$ $|$const $|$\-Value $|$operator\{b\}$|$(Value {\ttfamily v}) $|$\-Value $|$ 區間合併後的值 $|$
\begin{DoxyItemize}
\item 若要維護區間最小值, 即每次都是詢問範圍 {\ttfamily \mbox{[}a, b\mbox{]}} 的最小值, 則可以定義
\begin{DoxyItemize}
\item {\ttfamily operator+} 為 '回傳相加值'
\item {\ttfamily operator$\ast$} 為 '回傳$\ast$this'
\item {\ttfamily operator$|$} 為 '回傳std\-::min($\ast$this, v)'
\end{DoxyItemize}
\item 若要維護區間最總和, 即每次都是詢問範圍 {\ttfamily \mbox{[}a, b\mbox{]}} 的總和, 則可以定義
\begin{DoxyItemize}
\item {\ttfamily operator+} 為 '回傳相加值'
\item {\ttfamily operator$\ast$} 為 '回傳($\ast$this) $\ast$ n'
\item {\ttfamily operator$|$} 為 '回傳相加值'
\end{DoxyItemize}
\end{DoxyItemize}
\begin{DoxyAuthor}{Author}
cat\-\_\-leopard
\end{DoxyAuthor}
\subsection{Constructor \& Destructor Documentation}
\hypertarget{classmeow_1_1SegmentTree_a8e8365f0440c68f3c0853b94a7de3ccb}{\index{meow\-::\-Segment\-Tree@{meow\-::\-Segment\-Tree}!Segment\-Tree@{Segment\-Tree}}
\index{Segment\-Tree@{Segment\-Tree}!meow::SegmentTree@{meow\-::\-Segment\-Tree}}
\subsubsection[{Segment\-Tree}]{\setlength{\rightskip}{0pt plus 5cm}template$<$class Value $>$ {\bf meow\-::\-Segment\-Tree}$<$ Value $>$\-::{\bf Segment\-Tree} (
\begin{DoxyParamCaption}
{}
\end{DoxyParamCaption}
)\hspace{0.3cm}{\ttfamily [inline]}}}\label{classmeow_1_1SegmentTree_a8e8365f0440c68f3c0853b94a7de3ccb}
constructor
\hypertarget{classmeow_1_1SegmentTree_a1fe904372d3cdd01f07a1c88f86b14a1}{\index{meow\-::\-Segment\-Tree@{meow\-::\-Segment\-Tree}!Segment\-Tree@{Segment\-Tree}}
\index{Segment\-Tree@{Segment\-Tree}!meow::SegmentTree@{meow\-::\-Segment\-Tree}}
\subsubsection[{Segment\-Tree}]{\setlength{\rightskip}{0pt plus 5cm}template$<$class Value $>$ {\bf meow\-::\-Segment\-Tree}$<$ Value $>$\-::{\bf Segment\-Tree} (
\begin{DoxyParamCaption}
\item[{size\-\_\-t}]{size}
\end{DoxyParamCaption}
)\hspace{0.3cm}{\ttfamily [inline]}}}\label{classmeow_1_1SegmentTree_a1fe904372d3cdd01f07a1c88f86b14a1}
constructor, with {\ttfamily size} gived
\hypertarget{classmeow_1_1SegmentTree_a12a47cdf24eacb80d0bad4010f6a2953}{\index{meow\-::\-Segment\-Tree@{meow\-::\-Segment\-Tree}!Segment\-Tree@{Segment\-Tree}}
\index{Segment\-Tree@{Segment\-Tree}!meow::SegmentTree@{meow\-::\-Segment\-Tree}}
\subsubsection[{Segment\-Tree}]{\setlength{\rightskip}{0pt plus 5cm}template$<$class Value $>$ {\bf meow\-::\-Segment\-Tree}$<$ Value $>$\-::{\bf Segment\-Tree} (
\begin{DoxyParamCaption}
\item[{{\bf Segment\-Tree}$<$ Value $>$ const \&}]{tree2}
\end{DoxyParamCaption}
)\hspace{0.3cm}{\ttfamily [inline]}}}\label{classmeow_1_1SegmentTree_a12a47cdf24eacb80d0bad4010f6a2953}
constructor, 並且複製資料
\subsection{Member Function Documentation}
\hypertarget{classmeow_1_1SegmentTree_a889f38048ffe08ce3c80911878faac44}{\index{meow\-::\-Segment\-Tree@{meow\-::\-Segment\-Tree}!copy\-From@{copy\-From}}
\index{copy\-From@{copy\-From}!meow::SegmentTree@{meow\-::\-Segment\-Tree}}
\subsubsection[{copy\-From}]{\setlength{\rightskip}{0pt plus 5cm}template$<$class Value $>$ {\bf Segment\-Tree} {\bf meow\-::\-Segment\-Tree}$<$ Value $>$\-::copy\-From (
\begin{DoxyParamCaption}
\item[{{\bf Segment\-Tree}$<$ Value $>$ const \&}]{b}
\end{DoxyParamCaption}
)\hspace{0.3cm}{\ttfamily [inline]}}}\label{classmeow_1_1SegmentTree_a889f38048ffe08ce3c80911878faac44}
複製
\hypertarget{classmeow_1_1SegmentTree_aaeca3de355dc367e2664e83800ee6aa5}{\index{meow\-::\-Segment\-Tree@{meow\-::\-Segment\-Tree}!offset@{offset}}
\index{offset@{offset}!meow::SegmentTree@{meow\-::\-Segment\-Tree}}
\subsubsection[{offset}]{\setlength{\rightskip}{0pt plus 5cm}template$<$class Value $>$ void {\bf meow\-::\-Segment\-Tree}$<$ Value $>$\-::offset (
\begin{DoxyParamCaption}
\item[{ssize\-\_\-t}]{first, }
\item[{ssize\-\_\-t}]{last, }
\item[{Value const \&}]{delta}
\end{DoxyParamCaption}
)\hspace{0.3cm}{\ttfamily [inline]}}}\label{classmeow_1_1SegmentTree_aaeca3de355dc367e2664e83800ee6aa5}
將區間 {\ttfamily }\mbox{[}first,last\mbox{]} 全部都加上 {\ttfamily delta}
\hypertarget{classmeow_1_1SegmentTree_a765e794af604ab7c20a4245dfafcf14c}{\index{meow\-::\-Segment\-Tree@{meow\-::\-Segment\-Tree}!operator=@{operator=}}
\index{operator=@{operator=}!meow::SegmentTree@{meow\-::\-Segment\-Tree}}
\subsubsection[{operator=}]{\setlength{\rightskip}{0pt plus 5cm}template$<$class Value $>$ {\bf Segment\-Tree}\& {\bf meow\-::\-Segment\-Tree}$<$ Value $>$\-::operator= (
\begin{DoxyParamCaption}
\item[{{\bf Segment\-Tree}$<$ Value $>$ const \&}]{b}
\end{DoxyParamCaption}
)\hspace{0.3cm}{\ttfamily [inline]}}}\label{classmeow_1_1SegmentTree_a765e794af604ab7c20a4245dfafcf14c}
same as copy\-From(b)
\hypertarget{classmeow_1_1SegmentTree_a2f300a5fd5ffdd19e4b3efc6899a7439}{\index{meow\-::\-Segment\-Tree@{meow\-::\-Segment\-Tree}!override@{override}}
\index{override@{override}!meow::SegmentTree@{meow\-::\-Segment\-Tree}}
\subsubsection[{override}]{\setlength{\rightskip}{0pt plus 5cm}template$<$class Value $>$ void {\bf meow\-::\-Segment\-Tree}$<$ Value $>$\-::override (
\begin{DoxyParamCaption}
\item[{ssize\-\_\-t}]{first, }
\item[{ssize\-\_\-t}]{last, }
\item[{Value const \&}]{value}
\end{DoxyParamCaption}
)\hspace{0.3cm}{\ttfamily [inline]}}}\label{classmeow_1_1SegmentTree_a2f300a5fd5ffdd19e4b3efc6899a7439}
將區間 {\ttfamily }\mbox{[}first,last\mbox{]} 全部都設定成 {\ttfamily value}
\hypertarget{classmeow_1_1SegmentTree_a18bb3667abd9810ce3534af3d70b14d5}{\index{meow\-::\-Segment\-Tree@{meow\-::\-Segment\-Tree}!query@{query}}
\index{query@{query}!meow::SegmentTree@{meow\-::\-Segment\-Tree}}
\subsubsection[{query}]{\setlength{\rightskip}{0pt plus 5cm}template$<$class Value $>$ Value {\bf meow\-::\-Segment\-Tree}$<$ Value $>$\-::query (
\begin{DoxyParamCaption}
\item[{ssize\-\_\-t}]{first, }
\item[{ssize\-\_\-t}]{last}
\end{DoxyParamCaption}
) const\hspace{0.3cm}{\ttfamily [inline]}}}\label{classmeow_1_1SegmentTree_a18bb3667abd9810ce3534af3d70b14d5}
回傳區間 {\ttfamily }\mbox{[}first,last\mbox{]} (邊界都含) 的區間值
\hypertarget{classmeow_1_1SegmentTree_a80c550b0a3b997bc541ae0947ae2f55d}{\index{meow\-::\-Segment\-Tree@{meow\-::\-Segment\-Tree}!reset@{reset}}
\index{reset@{reset}!meow::SegmentTree@{meow\-::\-Segment\-Tree}}
\subsubsection[{reset}]{\setlength{\rightskip}{0pt plus 5cm}template$<$class Value $>$ void {\bf meow\-::\-Segment\-Tree}$<$ Value $>$\-::reset (
\begin{DoxyParamCaption}
\item[{size\-\_\-t}]{size}
\end{DoxyParamCaption}
)\hspace{0.3cm}{\ttfamily [inline]}}}\label{classmeow_1_1SegmentTree_a80c550b0a3b997bc541ae0947ae2f55d}
將資料清空且設定維護範圍是 {\ttfamily 0$\sim$size-\/1}
\hypertarget{classmeow_1_1SegmentTree_a8985a196cfb954bc469e7dae146ad4ed}{\index{meow\-::\-Segment\-Tree@{meow\-::\-Segment\-Tree}!size@{size}}
\index{size@{size}!meow::SegmentTree@{meow\-::\-Segment\-Tree}}
\subsubsection[{size}]{\setlength{\rightskip}{0pt plus 5cm}template$<$class Value $>$ size\-\_\-t {\bf meow\-::\-Segment\-Tree}$<$ Value $>$\-::size (
\begin{DoxyParamCaption}
{}
\end{DoxyParamCaption}
) const\hspace{0.3cm}{\ttfamily [inline]}}}\label{classmeow_1_1SegmentTree_a8985a196cfb954bc469e7dae146ad4ed}
回傳size
The documentation for this class was generated from the following file\-:\begin{DoxyCompactItemize}
\item
meowpp/dsa/\hyperlink{SegmentTree_8h}{Segment\-Tree.\-h}\end{DoxyCompactItemize}
|
