From 04e55aa4560f597373ca58c29f57fe6c98d11a50 Mon Sep 17 00:00:00 2001 From: cathook Date: Fri, 25 Apr 2014 01:53:47 +0800 Subject: add BIT --- README.html | 538 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 529 insertions(+), 9 deletions(-) (limited to 'README.html') diff --git a/README.html b/README.html index 664dc3d..e0b000a 100644 --- a/README.html +++ b/README.html @@ -2122,14 +2122,6 @@ width:100%;

-

keyOffset

-

(Key const& delta)

-

void

-

O(1)

-

將所有Element的Key同加上 delta

- - -

insert

(Key const& key,
Value const& value)

@@ -2150,6 +2142,14 @@ Value const& value)

+

keyOffset

+

(Key const& delta)

+

void

+

O(1)

+

將所有Element的Key同加上 delta

+ + +

operator[]

(Key const& key)

Value&

@@ -2397,6 +2397,508 @@ Value const& 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(...) +

    +
    • +
+
+
+
+
+
@@ -2443,6 +2945,24 @@ width:70%;

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

+
@@ -2464,7 +2984,7 @@ E-Mail: cat.hook31894 ~在~ gmail.com
-- cgit v1.2.3