\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}