meow::BinaryIndexTree< Value > Class Template Reference

極度簡化的 SegmentTree 已無區間更新的操作 More...

#include "BinaryIndexTree.h"

Public Member Functions
	BinaryIndexTree ()
	constructor More...
	BinaryIndexTree (size_t size, Value const &value)
	constructor More...
	BinaryIndexTree (BinaryIndexTree const &tree2)
	constructor More...
void	reset (size_t size, Value const &init)
	將資料洗掉, 重設 More...
void	update (size_t index, Value const &value)
	將array中第 index (從零算起)個element多加上指定的值 More...
Value	query (ssize_t index) const
	詢問 0~index 的區間值 More...

Detailed Description

template<class Value>
class meow::BinaryIndexTree< Value >

極度簡化的 SegmentTree 已無區間更新的操作

一般來說只能用在維護區間總和, 維護區間最大值只有在特殊情況才可以, 即 針對每個元素, 每次update() 的值一定會大於等於原本的值 . 若要用區間最大值 , 則 Value 的 operator+ 要寫成 std::max(...)

Author

cat_leopard

Definition at line 21 of file BinaryIndexTree.h.

Constructor & Destructor Documentation

template<class Value >

meow::BinaryIndexTree< Value >::BinaryIndexTree ( )

inline

constructor

Definition at line 28 of file BinaryIndexTree.h.

template<class Value >

meow::BinaryIndexTree< Value >::BinaryIndexTree ( size_t  size, Value const &  value  )

inline

constructor

Parameters

[in]	size	要維護的區間大小 [0,size)
[in]	value	預設值

Definition at line 37 of file BinaryIndexTree.h.

template<class Value >

meow::BinaryIndexTree< Value >::BinaryIndexTree ( BinaryIndexTree< Value > const &  tree2 )

inline

constructor

將另一個 BinaryIndexTree 原封不動的複製過來

Parameters

[in]

tree2

另外一個 BinaryIndexTree

Definition at line 47 of file BinaryIndexTree.h.

Member Function Documentation

template<class Value >

Value meow::BinaryIndexTree< Value >::query ( ssize_t  index ) const

inline

詢問 0~index 的區間值

時間複雜度O(logN)

Parameters

[in]

index

指定的index

Returns

區間值

Definition at line 90 of file BinaryIndexTree.h.

template<class Value >

void meow::BinaryIndexTree< Value >::reset ( size_t  size, Value const &  init  )

inline

將資料洗掉, 重設

時間複雜度O(N)

Parameters

[in]	size	要維護的區間大小 [0,size)
[in]	init	預設值

Returns

無

Definition at line 60 of file BinaryIndexTree.h.

template<class Value >

void meow::BinaryIndexTree< Value >::update ( size_t  index, Value const &  value  )

inline

將array中第 index (從零算起)個element多加上指定的值

時間複雜度O(logN)

Parameters

[in]	index	指定的index
[in]	value	指定的值

Returns

無

Definition at line 74 of file BinaryIndexTree.h.

---

The documentation for this class was generated from the following file:

• meowpp/dsa/BinaryIndexTree.h