meow::SegmentTree< Value > Class Template Reference

中文名 線段樹 More...

#include "SegmentTree.h"

Public Member Functions
	SegmentTree ()
	constructor More...
	SegmentTree (size_t size)
	constructor, with size gived More...
	SegmentTree (SegmentTree const &tree2)
	constructor, 並且複製資料 More...
SegmentTree	copyFrom (SegmentTree const &b)
	複製 More...
size_t	size () const
	回傳size More...
void	reset (size_t size)
	將資料清空且設定維護範圍是 0~size-1 More...
Value	query (ssize_t first, ssize_t last) const
	回傳區間 [first,last] (邊界都含) 的區間值 More...
void	override (ssize_t first, ssize_t last, Value const &value)
	將區間 [first,last] 全部都設定成 value More...
void	offset (ssize_t first, ssize_t last, Value const &delta)
	將區間 [first,last] 全部都加上 delta More...
SegmentTree &	operator= (SegmentTree const &b)
	same as copyFrom(b) More...

Detailed Description

template<class Value>
class meow::SegmentTree< Value >

中文名 線段樹

維護一個陣列, 並且讓user可以有區間查詢, 區間修改的小東東

Template Class Operators Request

const?	Typename	Operator	Parameters	Return Type	Description
const	Vector	operator[]	(size_t n)	Scalar	取得第 n 維度量
const	Vector	operator<	(Vector v)	bool	權重比較
const	Scalar	operator*	(Scalar s)	Scalar	相乘
const	Scalar	operator+	(Scalar s)	Scalar	相加
const	Scalar	operator-	(Scalar s)	Scalar	相差
const	Scalar	operator<	(Scalar s)	bool	大小比較
const	Value	operator+	(Value v)	Value	相加(位移)
const	Value	operator*	(size_t n)	Value	每個Value都一樣,

長為 n 的區間的值| |const |Value |operator{b}|(Value v) |Value | 區間合併後的值 |

• 若要維護區間最小值, 即每次都是詢問範圍 [a, b] 的最小值, 則可以定義
  • operator+ 為 '回傳相加值'
  • operator* 為 '回傳*this'
  • operator| 為 '回傳std::min(*this, v)'
• 若要維護區間最總和, 即每次都是詢問範圍 [a, b] 的總和, 則可以定義
  • operator+ 為 '回傳相加值'
  • operator* 為 '回傳(*this) * n'
  • operator| 為 '回傳相加值'

Author

cat_leopard

Constructor & Destructor Documentation

template<class Value >

meow::SegmentTree< Value >::SegmentTree ( )

inline

constructor

template<class Value >

meow::SegmentTree< Value >::SegmentTree ( size_t  size )

inline

constructor, with size gived

template<class Value >

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

inline

constructor, 並且複製資料

Member Function Documentation

template<class Value >

SegmentTree meow::SegmentTree< Value >::copyFrom ( SegmentTree< Value > const &  b )

inline

複製

template<class Value >

void meow::SegmentTree< Value >::offset ( ssize_t  first, ssize_t  last, Value const &  delta  )

inline

將區間 [first,last] 全部都加上 delta

template<class Value >

SegmentTree& meow::SegmentTree< Value >::operator= ( SegmentTree< Value > const &  b )

inline

same as copyFrom(b)

template<class Value >

void meow::SegmentTree< Value >::override ( ssize_t  first, ssize_t  last, Value const &  value  )

inline

將區間 [first,last] 全部都設定成 value

template<class Value >

Value meow::SegmentTree< Value >::query ( ssize_t  first, ssize_t  last  ) const

inline

回傳區間 [first,last] (邊界都含) 的區間值

template<class Value >

void meow::SegmentTree< Value >::reset ( size_t  size )

inline

將資料清空且設定維護範圍是 0~size-1

template<class Value >

size_t meow::SegmentTree< Value >::size ( ) const

inline

回傳size

---

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

• meowpp/dsa/SegmentTree.h