Description

一個不需要, 也不應該先compile成obj files的templates.

Links

File Tree

meowpp/ C++ templates

  • utility.h some useful functions, stringPringf() , stringReplace() , cstringEndWith() , debugPrintf() , messagePrintf() , constant PI , noEPS() , normalize() , denormalize() , ratioMapping() , inRange() , squ() , average()

  • Usage.h class Usage

  • colors/ Color splces and transformer

    • RGB.h class RGBi , class RGBf

    • YUV.h class YUVi , class YUVf , RGB_to_YUV() , YUV_to_RGB()

    • HSL.h class HSLf , RGB_to_HSL() , HSL_to_RGB() , YUV_to_HSL() , HSL_to_YUV()

    • HSV.h class HSVf , RGB_to_HSV() , HSV_to_RGB() , YUV_to_HSV() , HSV_to_YUV() , HSL_to_HSV() , HSV_to_HSL()

  • dsa/ Data Structures and Algorithms

    • DisjointSet.h class DisjointSet

    • Heaps.h class MergeableHeap<Element>

    • KD_Tree.h class KD_Tree<Vector, Scalar>

    • SegemenTree.h class SegmentTree<Value>

    • SplayTree.h class SplayTree<Key, Value>

    • VP_Tree.h class VP_Tree<Vector, Scalar>

  • oo/

    • Register_Implement.h class RegisterInterface , class ImplementInterface

Structures/Classes/Functions

meow:: Functios in utility.h

Name Parameters Return_Type Description

stringPrintf

(char const * fmt, …)

std::string

Format print to C++ string and return it

stringReplace

(std::string str,

std::string const& from,

std::string const& to)

std::string

Return a string like str, but all from be replaced by to

cstringEndWith

(char const* str,
int n, …)

bool

Return whether str is end with one of the c-string you specify in the parameters or not

debugPrintf

(char const* fmt, …)

void

Print debug message (file name, line number, …etc) when DEBUG is defined

messagePrintf

(int level_change,
char const* fmt, …)

void

階層式的訊息輸出

noEPS

(double value, double eps = 1e-9)

double

如果abs(輸入的數值) < eps, 則回傳0, 否則回傳輸入的數值

normalize

(double lower, double upper,
double value)

double

(value - lower) / (upper - lower)

denormalize

(double lower, double upper,
double ratio)

double

lower + (upper - lower) * ratio

ratioMapping

(double l1, double u1,
double m1, double l2,
double u2)

double

denormalize(l2, u2, normalize(l1, u1, m1))

inRange<T>

(T const& mn, T const& mx,
T const& v)

T

std::max(mn, std::min(mx, v))

squ<T>

(T const& x)

T

x * x

average<T>

(T const& beg, T const& end,
double sigs)

T

只將 sigs 個標準差以內的數據拿來取平均

average<T>

(T const& beg, T const& end,
T const& p, double sigs)

T

同上, 不過這次用 p 來加權平均
Note

  • stringReplace() 不是用什麼好方法寫的因此執行效率很低請別虐待它.

  • 額外附贈一個 const double PI = 3.141592653589......

meow:: Usage (C++ Class)

Description

Usage 是用來分析argc, argv和輸出usage document的class. argc, argv的部份, 有以下規則

  • -c 其中 c 可以代換成正常的一個字元的字符, 這種選像要嘛就是 有設置 , 不然就是 沒設置

  • -c <value> 附加一個value, 這種選項可以是選擇性 ,即要設定與否都可以, 反之則一定要設定. 另外可以給定value的預設值以及哪些value是可接受的

  • <value> 其他, 一律視為process arguments

Methods

  • Usage(String const& _name)
    建構子, 所有說明文字中 <name> 都會被代換成 _name

  • Usage()
    建構子, _name 自動取為 " nobody "

  • import(Usage const& usage)
    將另一個usage的設定匯入, 回傳成功與否 (bool)

  • update(Usage const& usage)
    將另一個usage分析argc,argv出來的資料拿來用, 回傳成功與否 (bool)

  • addOption(unsigned char option, String const& description)
    新增一個不接額外選項的參數, 並附上說明文字, 回傳成功與否 (bool)

  • addOption(unsigned char option, String const& description, String const& value_type, String const& value_default, bool must)
    新增一個有額外選項的參數, 並附上說明文字, 額外選項的型別跟預設值. 說明文字中所有的" <types> "將會被取代指定的型別, 其中 must 代表 " 是否一定要設定此參數 " , 回傳表成功與否 (bool)

  • addOptionValueAccept(unsigned char option, String const& value, String const& description)
    針對某個option, 新增一個可接受的額外選項 (如果某個option從頭到尾都 沒有新增可接受的選項, 則視為不限制), 回傳成功與否 (bool)

  • hasOptionSetup(unsigned char option)
    回傳是否有此選項 (bool)

  • getOptionValuesCount(unsigned char option)
    回傳此參數被設置了幾次 (size_t) , 只對有接額外參數的有效

  • getOptionValue(unsigned char option, size_t index)
    回傳第`index`個額外選項 (String)

  • getProcArgsCount()
    回傳有多少個Process Arguments (size_t)

  • getProcArg(size_t index)
    取得第`index`個Process Argument (String)

  • getProcArgs()
    回傳一個陣列, 包含所有Process Arguments (Strings)

  • addUsageBegin(String const& des)
    新增一段usage document於每個選項逐條說明之前

  • addUsageEnd (String const& des)
    新增一段usage document於每個選項逐條說明之後

  • String getUsage()
    回傳usage document (String)

  • setArguments(int argc, char** argv, String* errmsg)
    輸入argv, argc, 回傳是否沒有錯誤發生 (bool) , 其中如果有錯誤發生, 且 errmsg != NULL 則會將錯誤訊息寫入之

Note

  • String 是 std::string .

  • Strings 是 std::vector< std::string> >.

  • 如果沒有寫回傳什麼, 就是回傳 void

meow:: ImplementInterface/RegisterInterface (C++ Class)

Description

Assume there is a problem which can be solved by different algorithms. Then you can write multiple classes to approach this problem.
Now if you want to decide which algorithm to use in runtime, you can just approach this case by a simple way:

  • Let all the problem-solving classes inherit from class ImplementInterface<T> , and call the constructure with giving identify (type T ) .

  • Create an class inherit from RegisterInterface<T> , and register all your implement class to it by call regImplement(pointer to the class).

  • Select which implement class you want by call getImplement(identify) , which will return the pointer to the corresponding class.

meow:: DisjointSet (C++ class)

Description

DisjointSet 是個輕量級Data Dtructure, 用來維護一堆互斥集的資訊. 相關資料可參考 演算法筆記

Support Methods

Const? Name Parameters Return_Type Time_Complexity Description

const

root

(size_t number)

size_t

very fast

回傳 number 所在的 集合的編號 (0~N-1)

const

size

()

size_t

very fast

回傳 總集合大小

reset

(size_t N)

void

O(N)

清空, 並且設定總集合大小為 N

merge

(size_t number1,
size_t number2)

size_t

very fast

將 number1 所在的集合 跟 number2 所在的集合 合併, 並回傳合併後新的集合的編號
Note

  • very fast 表示它算的真的超級快, 可以視為常數時間.

  • 預設值所有 number 所在的集合的編號就是 number 本身, 即沒有任兩個數在同一個set裡面

meow:: MergeableHeap<Element> (C++ class)

Description

一個用 左偏樹 實作的 Maximum-Heap , 除了原本heap有的功能外, 還支援 merge, split 等功能

Template Class Operators Request

Const? Typename Operator Parameters Return_Type Description

const

Element

operator<

(Element v)

bool

大小比較

Support Methods

  • N ← this 中擁有的資料數

Const? Name Parameters Return_Type Time_Complexity Description

moveTo

(MergeableHeap* h)

void

O(M)

將 this 的資料複寫到 h 上面, 同時清空自己, 時間複雜度中的M是 h 所擁有的資料數

const

top

()

Element const&

O(1)

回傳最大的那個 Element

const

size

()

size_t

O(1)

回傳 this 中擁有的資料數

const

empty

()

bool

O(1)

回傳 this 是否為空

push

(Element const& e)

void

O(logN)

將 e 加入

pop

()

void

O(logN)

將最大的 Element 移除

clear

()

void

O(N)

將資料清空

merge

(MergeableHeap* heap2)

void

O(logN+logM)

將 heap2 的資料統統加到 this 中, 並且清空 heap2 時間複雜度中的M是 heap2 的資料數
Warning

  • 假設現在有兩個MergeableHeap A 和 B, 則:

    • 執行 A.merge(&B) 後 B 會變成空的

    • 執行 B.moveTo(&A) 後 B 會變成空的, A 原本擁有的資料也會覆蓋掉

meow:: VP_Tree<Vector, Scalar> (C++ class)

Description

VP_Tree 用來維護由 N個K維度向量所成的集合, 並可於該set中查找 前i個離給定向量最接近的向量.
不像 KD_Tree 二分樹每次都選擇一個維度去分, 分成小的跟大的, VP_Tree 每次選一個點, 將資料分成 離這個點近的, 跟離這個點遠的. 至於怎麼選呢…., 嘛還沒研究, 先random

參考資料連結:

Template Class Operators Request

Const? Typename Operator Parameters Return_Type Description

const

Vector

operator[]

(size_t n)

Scalar

取得第 n 維度量

const

Vector

operator=

(Vector v)

Vector&

copy operator

const

Vector

operator<

(Vector v)

bool

權重比較

const

Scalar

Scalar

(int n)

Scalar

建構子, 其中一定n=0 or 4

const

Scalar

operator*

(Scalar s)

Scalar

相乘

const

Scalar

operator+

(Scalar s)

Scalar

相加

const

Scalar

operator-

(Scalar s)

Scalar

相差

const

Scalar

operator-

( )

Scalar

取負號

const

Scalar

operator<

(Scalar s)

bool

大小比較

Custom Type Definitions

  • Vectors ← std::vector<Vector>

Support Methods

  • N ← this 中擁有的資料數

  • D ← this 資料維度

Const? Name Parameters Return_Type Time_Complexity Description

insert

(Vector const& v)

void

O(1)

將向量 v 加到set中

erase

(Vector const& v)

bool

O(N)

將向量 v 從set中移除, TODO:可以再優化

build

()

void

O(KN logN) or O(1)

檢查距上一次 build() 至今是否有 insert/erase 被呼叫, 若有, 重新建樹, 否則不做事

forceBuild

()

void

O(KN logN)

重新建樹

const

query

(Vector const& v,
size_t i,
bool cmp)

Vectors

O(logN) Expected

於set中找尋距離 v 前 i 近的向量, 並依照由近而遠的順序排序. 如果有兩個向量 v1,v2 距離一樣, 且 cmp 為 true , 則直接依照 v1 < v2 來決定誰在前面. 最後回傳一陣列包含所有解.

clear

()

void

O(1)

清空所有資料

reset

(size_t dimension)

size_t

O(1)

清空所有資料並且指定維度為 max(1, dimension) 並且回傳指定後的維度
Note

  • 實測結果發覺, 維度小的時候, 比起中規中矩的 KD_Tree, VP_Tree 有 randomp 於其中, 因此時間複雜度只是期望值 O(logN) 但是測資大到 一定程度, KD_Tree 效率會一整個大幅掉下, 但 VP_Tree 幾乎不受影響

  • TODO insert(), erase() 算是未完成功能

meow:: KD_Tree<Vector, Scalar> (C++ class)

Description

KD_Tree 全名k-dimension tree, 用來維護由 N個K維度向量所成的集合, 並可於該set中查找 前i個離給定向量最接近的向量

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

大小比較

Custom Type Definitions

  • Vectors ← std::vector<Vector>

Support Methods

  • N ← this 中擁有的資料數

  • K ← this 資料維度

Const? Name Parameters Return_Type Time_Complexity Description

insert

(Vector const& v)

void

O(1)

將向量 v 加到set中

erase

(Vector const& v)

bool

O(N)

將向量 v 從set中移除, TODO:可以再優化

build

()

void

O(KN logN) or O(1)

檢查距上一次 build() 至今是否有 insert/erase 被呼叫, 若有, 重新建樹, 否則不做事

forceBuild

()

void

O(KN logN)

重新建樹

const

query

(Vector const& v,
size_t i,
bool cmp)

Vectors

O(KN 1-1/K )

於set中找尋距離 v 前 i 近的向量, 並依照由近而遠的順序排序. 如果有兩個向量 v1,v2 距離一樣, 且 cmp 為 true , 則直接依照 v1 < v2 來決定誰在前面. 最後回傳一陣列包含所有解.

clear

()

void

O(1)

清空所有資料

reset

(size_t dimension)

void

O(1)

清空所有資料並且指定維度為 dimension
Note

  • 此資料結構只有在 N >> 2 K 時才比較有優勢, 當 K 逐漸變大時, 所花時間會跟暴搜沒兩樣

meow:: SplayTree<Key, Value> (C++ class)

Description

SplayTree 是一種神乎其技的資料結構, 維護一堆 Key→Value . 並且支援 一些 std::map 難以快速實踐的操作, 如 split , merge , keyOffset

Template Class Operators Request

Const? Typename Operator Parameters Return_Type Description

const

Key

operator+

(Key k)

Key

相加

const

Key

operator<

(Key k)

bool

大小比較

Key

Key

(int n)

建構子, n 永遠是0

Value

Value

( )

建構子

Custom Type Definitions

  • Element → 用來當作回傳資料的媒介

    • 重定義 operator->() 到 std::pair<Key const&, Value&>*

    • 重定義 operator*() 到 std::pair<Key const&, Value&>&

    • 有 operator== , operator!=, operator= 可用

    • 可以直接用 (*e).second = some_value 來改變SplayTree中的資料

Support Methods

  • N ← this 中擁有的資料數

  • M ← tree2 中擁有的資料數

Const? Name Parameters Return_Type Time_Complexity Description

moveTo

(SplayTree* tree2)

void

O(M)

將 this 的資料複寫到 tree2 上面, 同時清空自己, 時間複雜度中的M是 tree2 所擁有的資料數

const

lowerBound

(Key const& k)

Element

O(logN)

找出第一個(最小的) Element且 k ⇐ 它的 Key, 並且回傳之. 找不到的話回傳 this->end()

const

lowerBound

(Key const& k)

Element

O(logN)

找出第一個(最小的) Element且 k < 它的 Key, 並且回傳之. 找不到的話回傳 this->end()

const

lowerBound

(Key const& k)

Element

O(logN)

找出第一個(最小的) Element且 k >= 它的 Key, 並且回傳之. 找不到的話回傳 this->end()

const

lowerBound

(Key const& k)

Element

O(logN)

找出第一個(最小的) Element且 k > 它的 Key, 並且回傳之. 找不到的話回傳 this->end()

const

find

(Key const& k)

Element

O(logN)

找出 Key= k 的Elemenet 並回傳. 找不到的話回傳 this->end()

const

order

(size_t ord)

Element

O(logN)

將Elements依照Key由小到大排序, 回傳第 ord 個Element (由0算起). 其中如果 ord > N - 1, 則會回傳 this->last()

const

first

(size_t ord)

Element

O(logN)

回傳Key最小的Element, 如果SplayTree為空, 則回傳 this->end()

const

last

(size_t ord)

Element

O(logN)

回傳Key最大的Element, 如果SplayTree為空, 則回傳 this->end()

const

end

()

Element

O(1)

回傳一個指向NULL的Element, 以供 find , order , first , last 等判斷是否有找到相對應的Element

const

size

()

size_t

O(1)

回傳資料數

const

size

()

bool

O(1)

回傳是否為空

clear

()

void

O(N)

清空資料

insert

(Key const& key,
Value const& value)

bool

O(logN)

檢查是否已有Element的Key 為 key, 若有則回傳 false , 否則將 一個 (Key → Value) = (key → value)的Element加入, 並回傳 true 將所有Element的Key同加上 delta

erase

(Key const& key)

bool

O(logN)

檢查是否已有Element的Key 為 key, 若有則刪除之, 並回傳 true, 否則則回傳 false

keyOffset

(Key const& delta)

void

O(1)

將所有Element的Key同加上 delta

operator[]

(Key const& key)

Value&

O(logN)

檢查是否已有Element的Key 為 key, 若有則回傳相對應的Value的Reference 否則先執行 insert(key, Value()) 再回傳相對應的Reference

splitOut

(Key const& upper_bound,
SplayTree* tree2)

void

O(logN) + O(M)

將 tree2 清空, 再將所有Key > upper_bound 的Element都丟到 tree2

mergeAfter

(SplayTree* tree2)

void

O(logN) + O(logM)

檢查是否 this 中的 Key 都小於 tree2 中的Key, 是的話把 tree2 中的 Element 都搬到 this , 同時清空 tree2 , 回傳 true. 否則 回傳 false

merge

(SplayTree* tree2)

void

O(logN) + O(logM)

檢查是否 this 中的 Key 都小於 tree2 中的Key 或者 是否 this 中的 Key 都大於 tree2 中的Key, 是的話把 tree2 中的 Element 都搬到 this , 同時清空 tree2 , 回傳 true. 否則 回傳 false
Note

  • 假設現在有兩個SplayTree A 和 B, 則:

    • 執行 B.moveTo(&A) 後 B 會變成空的, A 原本擁有的資料也會覆蓋掉

    • 執行 A.merge(&B) 或 A.mergeAfter(&B) 後 如果檢查發現確實可以merge, 則之後 B 會變成空的

meow:: SegmentTree<Value> (C++ class)

Description

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

Template Class Operators Request

Const? Typename Operator Parameters Return_Type Description

const

Value

operator+

(Value v)

Value

相加(位移)

const

Value

operator*

(size_t n)

Value

每個Value都一樣, 長為 n 的區間的值

const

Value

operator|

(Value v)

Value

區間合併後的值

  • 若要維護區間最小值, 即每次都是詢問範圍 [a, b] 的最小值, 則可以定義

    • operator+ 為 回傳相加值

    • operator* 為 回傳*this

    • operator| 為 回傳std::min(*this, v)

  • 若要維護區間最總和, 即每次都是詢問範圍 [a, b] 的總和, 則可以定義

    • operator+ 為 回傳相加值

    • operator* 為 回傳(*this) * n

    • operator| 為 回傳相加值

Support Methods

  • N ← this 所維護的陣列長度

Const? Name Parameters Return_Type Time_Complexity Description

reset

(size_t size)

void

O(1)

將資料清空且設定維護範圍是 0~size - 1 其中時間複雜度確切多少未知 要看 std::vector::resize() 的效率

const

query

(ssize_t first,
ssize_t last)

Value

O(logN)

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

override

(ssize_t first,
ssize_t last,
Value const& value)

void

O(logN)

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

offset

(ssize_t first,
ssize_t last,
Value const& delta)

void

O(logN)

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

meow:: SplayTree_Range<Key, Value> (C++ class)

Description

SplayTree_Range 是一種神乎其技的資料結構, 維護一堆 Key→Value. 並且支援 一些 std::map 難以快速實踐的操作, 如 split , merge , keyOffset

Template Class Operators Request

Const? Typename Operator Parameters Return_Type Description

const

Key

operator+

(Key k)

Key

相加

const

Key

operator<

(Key k)

bool

大小比較

Key

Key

(int n)

建構子, n 永遠是0

Value

Value

( )

建構子

Custom Type Definitions

  • Element → 用來當作回傳資料的媒介

    • 重定義 operator->() 到 std::pair<Key const&, Value&>*

    • 重定義 operator*() 到 std::pair<Key const&, Value&>&

    • 有 operator== , operator!=, operator= 可用

    • 可以直接用 (*e).second = some_value 來改變SplayTree_Range中的資料

Support Methods

  • N ← this 中擁有的資料數

  • M ← tree2 中擁有的資料數

Const? Name Parameters Return_Type Time_Complexity Description

moveTo

(SplayTree_Range* tree2)

void

O(M)

將 this 的資料複寫到 tree2 上面, 同時清空自己, 時間複雜度中的M是 tree2 所擁有的資料數

const

lowerBound

(Key const& k)

Element

O(logN)

找出第一個(最小的) Element且 k ⇐ 它的 Key, 並且回傳之. 找不到的話回傳 this->end()

const

lowerBound

(Key const& k)

Element

O(logN)

找出第一個(最小的) Element且 k < 它的 Key, 並且回傳之. 找不到的話回傳 this->end()

const

lowerBound

(Key const& k)

Element

O(logN)

找出第一個(最小的) Element且 k >= 它的 Key, 並且回傳之. 找不到的話回傳 this->end()

const

lowerBound

(Key const& k)

Element

O(logN)

找出第一個(最小的) Element且 k > 它的 Key, 並且回傳之. 找不到的話回傳 this->end()

const

find

(Key const& k)

Element

O(logN)

找出 Key= k 的Elemenet 並回傳. 找不到的話回傳 this->end()

const

query

()

Value

O(1)

回傳整棵樹的區間Value

const

query

(Key const& first ,
Key const& last)

Value

O(logN)

找出key介於 first
~ last 的區間Value

const

order

(size_t ord)

Element

O(logN)

將Elements依照Key由小到大排序, 回傳第 ord 個Element (由0算起). 其中如果 ord > N - 1, 則會回傳 this->last()

const

first

(size_t ord)

Element

O(logN)

回傳Key最小的Element, 如果SplayTree_Range為空, 則回傳 this->end()

const

last

(size_t ord)

Element

O(logN)

回傳Key最大的Element, 如果SplayTree_Range為空, 則回傳 this->end()

const

end

()

Element

O(1)

回傳一個指向NULL的Element, 以供 find , order , first , last 等判斷是否有找到相對應的Element

const

size

()

size_t

O(1)

回傳資料數

const

size

()

bool

O(1)

回傳是否為空

clear

()

void

O(N)

清空資料

insert

(Key const& key,
Value const& value)

bool

O(logN)

檢查是否已有Element的Key 為 key, 若有則回傳 false , 否則將 一個 (Key → Value) = (key → value)的Element加入, 並回傳 true 將所有Element的Key同加上 delta

erase

(Key const& key)

bool

O(logN)

檢查是否已有Element的Key 為 key, 若有則刪除之, 並回傳 true, 否則則回傳 false

keyOffset

(Key const& delta)

void

O(1)

將所有Element的Key同加上 delta

valueOffset

(Value const& delta)

void

O(1)

將所有Element的value同加上 delta

valueOverride

(Value const& vaule)

void

O(1)

將所有Element的value同變成 value

operator[]

(Key const& key)

Value&

O(logN)

檢查是否已有Element的Key 為 key, 若有則回傳相對應的Value的Reference 否則先執行 insert(key, Value()) 再回傳相對應的Reference

splitOut

(Key const& upper_bound,
SplayTree_Range* tree2)

void

O(logN) + O(M)

將 tree2 清空, 再將所有Key > upper_bound 的Element都丟到 tree2

mergeAfter

(SplayTree_Range* tree2)

void

O(logN) + O(logM)

檢查是否 this 中的 Key 都小於 tree2 中的Key, 是的話把 tree2 中的 Element 都搬到 this , 同時清空 tree2 , 回傳 true. 否則 回傳 false

merge

(SplayTree_Range* tree2)

void

O(logN) + O(logM)

檢查是否 this 中的 Key 都小於 tree2 中的Key 或者 是否 this 中的 Key 都大於 tree2 中的Key, 是的話把 tree2 中的 Element 都搬到 this , 同時清空 tree2 , 回傳 true. 否則 回傳 false
Note

  • 假設現在有兩個SplayTree_Range A 和 B, 則:

    • 執行 B.moveTo(&A) 後 B 會變成空的, A 原本擁有的資料也會覆蓋掉

    • 執行 A.merge(&B) 或 A.mergeAfter(&B) 後 如果檢查發現確實可以merge, 則之後 B 會變成空的

meow:: BinaryIndexTree<Value> (C++ class)

Description

極度簡化版的 SegmentTree 已無法區間操作, 區間詢問的區間開頭也一定要 在 index=0 的地方

Template Class Operators Request

Const? Typename Operator Parameters Return_Type Description

const

Value

operator+

(Value n)

Value

合併用(類似 SegmentTree 的 operator| )

Support Methods

  • N ← this 中擁有的資料數

Const? Name Parameters Return_Type Time_Complexity Description

reset

(size_t size, Value const& value)

void

O(size)

將資料長度刷成 N = size 且每一個元素都是 value

update

(size_t index, Value const& value)

void

O(logN)

將第 index (從零開始算) 多加上 value

const

query

(size_t index)

void

O(logN)

詢問 0~index 的區間值
Note

  • 一般來說只能用在維護區間總和, 維護區間最大值只有在特殊情況才可以, 即 針對每個元素, 每次 update() 的值一定會大於等於原本的值

  • 若要用區間最大值 , 則 Value 的 operator+ 要寫成 std::max(...)

Test

ACM 相關題目

Name Problem Link Status Time source

KD_Tree

Retrenchment

NTU-OJ ACM-ICPC Live

Accept

0.083

codepad

VP_Tree

Retrenchment

NTU-OJ ACM-ICPC Live

Accept

0.516

codepad

SplayTree + SegmentTree

Shuffling_cards

NTU-OJ SPOJ

Accept/TLE

6.910/---

codepad

SplayTree + BinaryIndexTree

Shuffling_cards

NTU-OJ SPOJ

Accept/Accept

5.480/44.35

codepad

Bug Report / Contact

  • E-Mail: cat.hook31894 ~在~ gmail.com