blob: 3a772fd7e533ea8a9a924078dda7e84871fcb9a0 (
plain) (
tree)
|
|
\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}
Definition at line 21 of file Binary\-Index\-Tree.\-h.
\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
Definition at line 28 of file Binary\-Index\-Tree.\-h.
\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}
Definition at line 37 of file Binary\-Index\-Tree.\-h.
\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}
Definition at line 47 of file Binary\-Index\-Tree.\-h.
\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}
Definition at line 90 of file Binary\-Index\-Tree.\-h.
\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}
Definition at line 60 of file Binary\-Index\-Tree.\-h.
\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}
Definition at line 74 of file Binary\-Index\-Tree.\-h.
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}
|
