\( \newcommand{\ord}[1]{\mathcal{O}\left(#1\right)} \newcommand{\abs}[1]{\lvert #1 \rvert} \newcommand{\floor}[1]{\lfloor #1 \rfloor} \newcommand{\ceil}[1]{\lceil #1 \rceil} \newcommand{\opord}{\operatorname{\mathcal{O}}} \newcommand{\argmax}{\operatorname{arg\,max}} \newcommand{\str}[1]{\texttt{"#1"}} \)

2015年12月30日 星期三

[ round-off error eps ] 浮點數誤差模板

有些計算幾何的過程中會產生捨位誤差,這時候就需要決定一個很小的數,去避開這個捨位誤差問題,我們稱那個很小的數為EPS
  • A < B ....... A - B < - EPS
  • A > B ....... A - B > EPS
  • A == B ....... abs(A - B) <= EPS
  • A <= B ....... A - B <= EPS
  • A >= B ....... A - B >= - EPS
因為我的計算幾何模板在實作時是用template實作的,所以如果需要處理浮點數誤差時,需要傳入一個新的資料結構,所以寫了這份模板

[ long long multiply long long mod long long ] long long 乘 long long 模 long long不溢位算法

這標題有點長,不過也很清楚的顯示了這篇的重點,所以就直接附模板吧
如果a,b<m的話a%=m,b%=m;可以拿掉沒關係

code(比較慢,但適用範圍更大,算法取自維基百科:同餘):

2015年12月27日 星期日

[ Maze generation-Randomized Kruskal's algorithm ] 迷宮生成-隨機Kruskal算法

說得通俗點,就是"隨機拆牆"。
一開始假設所有牆都在,也就是圖的每個點都不連通。如果當前不滿足“任意兩個格子間都有唯一路徑”,那麼就隨機選擇一堵牆,要求牆兩端的格子不連通,即它們對應的兩個頂點在兩個不同的連通分量。把這堵牆拆掉,即在後牆兩端的格子對應的頂點間建立一條邊。重複作下去,直到所有的點都在同一個連通分量裡面。
會發現這就是隨機合併點的Kruskal演算法,需要用到並查集

範例生成圖:
#########################
#   #       #   #       #
### # # # ### ####### ###
#     # #   #   # #     #
######### ### # # ##### #
#       # #   #   #     #
### ### # # # ### ### ###
#   #   #   #   #       #
### # ##### ### ##### ###
#   #       # #     # # #
####### # ### # ####### #
#   # # #   #       # # #
# ### ### ### # ##### # #
# #     # #   # # # # # #
# # ### # ### ### # # # #
# # #     #   #         #
# # ### ######### # #####
#   #   # # #     #   # #
####### # # # # ### ### #
#     #       #   #     #
# # ##### ######### # ###
# #               # #   #
### # # ### # ####### ###
#   # #   # #   #       #
#########################

code(n,m必須是奇數):

2015年12月21日 星期一

[ min-max heap ] 最小-最大堆

最小-最大堆(Min-Max Heaps)是一個完整二元樹。此二元樹是交替的階層方式呈現,分別為最小階層 ( min level ) 和最大階層 ( max level ) ,這裡實作樹根為最小鍵值。

最小-最大堆是一種堆積支援以下幾種操作:
  1. 求最大值 - max()
  2. 求最小值 - min()
  3. 刪除最大值 - pop_max()
  4. 刪除最小值 - pop_min()
  5. 元素入堆 - push()
詳細演算法可以參考原始論文
Min-Max Heaps and Generalized Priority Queues
如果不懂敘述就看code吧
以下提供模板:

2015年11月23日 星期一

[ link-cut tree ] 動態樹教學+模板

因為code太多容易顯示不出來,這裡有Gist連結
動態樹,一種支持斷邊、連邊的資料結構(要保證是樹或森林),可以維護路徑、但不能維護子樹。
類似於樹鏈剖分(建議先學完樹鏈剖分,再學LCT)。
只不過樹鏈剖分的輕重邊是根據子樹大小而決定的,這棵樹只能是靜態的。
而LCT中的“輕重邊”是根據最後一次操作決定的,最後一次處理了x這個點,那麼從x到根的路徑就是重鏈(每個父親只與一個兒子的連邊為重邊)。
用splay來維護每一條重鏈,以點的深度為關鍵字,即splay中的每個點左兒子深度都比他小,右兒子的深度都比他大(若只有一個點,那麼這個點單獨是一棵splay)。
如果還不知道splay tree的可以參考這裡

splay tree及其節點的一些函數:

定義:
  1. Preferred child:
    如果一個點是他父親結點的所有兒子中最後被訪問的,那麼他是他父親的Preferred child。
    每個點最多有一個Preferred child。如果x結點是最後被訪問的點,那麼他沒有Preferred child。
  2. Preferred edge:
    每個點到自己的Preferred child的邊叫Preferred edge(相當於樹鏈剖分中的重邊)
  3. Preferred path:
    由Preferred edge組成的鏈叫Preferred path(相當於樹鏈剖分的重鏈)
簡單來說就是一個節點在重鏈上的直接兒子定義為preferred child,連向該兒子的邊定義為preferred edge。
access(x):
我們用操作access(x)來表示訪問節點x為LCT的最基礎操作,使x到根結點的路徑成為重鏈。

如上圖,粗邊為重邊。

首先把x旋到他所在的splay的根部。
因為當前的x點是最後一個被訪問的點,所以他沒有Preferred child,因此要把右兒子與他斷開,右兒子成為新的一條鏈。
x的父親是y,把y旋到他所在splay的根結點,把此時y的右兒子與他斷開,把x連過來即可,相當於合併y和x所在的splay。
然後,再找y的父親,合併y與y的父親所在的splay,一直到根結束。
最終,x到根結點的路徑成為新的Preferred edge,而曾經的Preferred child都被拋棄。
有了access操作後,其他的操作就更容易實現了

make_root(x):
將x設為其所在的樹的根
首先access(x),這樣x與根結點處在同一棵splay中。
設a=access(x),而a是splay tree的根,因為要讓x成為整棵樹的根,所以x的深度要最小,我們只要在a上加一個區間反轉的標記rev就可以完成。
這裡提供兩種方式,最後都會把節點x轉到splay tree根的位置(這很重要)
1.
2.
link(x,y):
連接x與y所在的兩棵樹。
先判斷是否在同一棵splay tree裡,如果是的話就不做任何事
首先Makeroot(x),x就成為了他所在樹的根。
然後直接把x的父親賦值為y即可。
cut(x,y):
斷開x與y所相連的邊。
首先Makeroot(x),然後Access(y),此時x與y在同一棵splay中,再Splay(y),此時x是y的左兒子,然後將其左兒子及左兒子的父母設成空節點即可。
cut_parents(x):
跟cut類似,斷掉x和其父親節點之間的邊。首先access節點x。然後讓x旋轉到所在輔助樹的根節點上。斷掉左子樹。
find_root(x):
尋找點x在所在樹的根節點。這個操作很簡單,我們只要對x做一次access操作,這樣x和它的根就應該在一個splay中了。那麼此時的根就應該是這個splay最左邊的節點。
因為是splay tree,所以在搜尋完後仍要進行splay操作
對於很多問u到v的路徑問題,我們可以將u到v的路徑構造成一顆splay tree並求出其根節點維護的值即可。
如果要不改變根節點的話可以求出LCA再進行處理,以下用u,v路徑上的點權總和為例:
修改點權:
將一棵有邊權的樹構建成link cut tree:
查詢這棵樹的邊權,因為不能改變root,所以要對access函數作一點修改,以下以u,v路徑上的最大值為例:
查詢只需要這樣寫就好了:

2015年11月9日 星期一

[ Karatsuba Multiply ] 大數模板乘法Karatsuba法

複雜度大約是\(\ord{N^{log3}}\),約為\(\ord{N^{1.5}}\)比一般直式乘法還快,附上連結:
Karatsuba算法

附模板,配合大數模板使用:

2015年10月14日 星期三

[ Augmenting Path Algorithm ] 二分圖匹配增廣路徑演算法

就是一直找增廣路徑,找到不能再找就是最大匹配惹
複雜度\(\ord{n1*(m+n2+n1)}\),用dinic會比較快但是code比較長
模板:

[ Improved Shortest Augmenting Paths,ISAP ,Flow ] 網路流ISAP算法

使用gap優化(間隙優化)
使用當前弧優化

這裡提供遞迴與非遞迴兩種實現
基本上兩個版本效能差不多
遞迴版本:

非遞迴版本:

[ Dinic's algorithm ,Flow ] 網路流Dinic模板

使用當前弧優化

多路增廣模板:

單路增廣模板:

[ Edmonds–Karp algorithm ,Flow] 網路流Edmonds–Karp算法

這是最基本的多項式時間網路流演算法,因此在這裡我多了一些變化,首先是一般用鄰接矩陣,複雜度$\ord{\abs{V}^5}$的做法:
接著是使用鄰接串列,複雜度是$\ord{\abs{E}^2\abs{V}}$的作法:
最近幫學長寫作業的時候,又發現了一個不需要多紀錄反邊的做法,但是每個點要同時記錄入邊和出邊,這樣可以用較少的記憶體完成演算法:

[ Travelling Salesman Problem, TSP ] 旅行推銷員問題

假設圖是完全圖的情況下,從原點出發經過所有點一次並回到原點的最短路徑問題
以下為模板:

2015年10月6日 星期二

[ Rabin-Karp rolling hash ] Rabin-Karp 字串hash演算法

Michael O. Rabin和Richard M. Karp在1987年提出一個想法,即可以對模式串進行哈希運算並將其哈希值與文本中子串的哈希值進行比對。
設字串陣列為\(S[n]\),字元編號為\(0\)到\(n-1\)
首先建立陣列\(Hash[n+1]\),\(Hash[i]\)表示
\((S[0]*P^{i-1}+S[1]*P^{i-2}+...+S[i-1])\%PM,Hash[0]=0\),其中\(P\)跟\(PM\)是質數
假設要取編號\(L\)到編號\(R\)左閉右開區間的hash值,則其為\((Hash[R]-Hash[L]*P^{R-L})\%PM\)
如果要用double hash則用不同質數計算兩種不同的hash值,用pair拼起來即可
以下提供模板:

2015年9月23日 星期三

[ Fraction ] 分數模板

今天學弟的比賽剛結束,因為有考到相關內容所以到現在才釋出分數模板。
因為每種題目要求輸出的分數格式都不一樣,所以不提供輸出的程式,必定約到最簡分數。
以下提供模板:

2015年9月17日 星期四

[ Ternary Search ] 三分搜尋法模板

對於一個U型或倒U型函數,我們可以利用三分搜尋法找出其最低/最高點,時間複雜度為\(\ord{log \; n}\),這裡n是\(10^{(整數位數+浮點位數)}\)

關於原理就不多說了,以下提供對於U型函數的模板:

用法:

2015年8月31日 星期一

[ Lowest Common Ancestor , LCA Euler Tour Technique ] 最近共同祖先樹壓平轉RMQ算法

想法就是把樹壓平,然後紀錄當前節點u的深度在dep[u],紀錄時間戳記,進入的時候要紀錄一次,出來的時候也要記錄,把當前點u進入的時間戳紀錄在in[u]中,時間戳的大小為2*n,所以必須用兩倍的記憶體來維護。之後就轉成RMQ問題
查詢a,b兩點的LCA=dep[in[a]]到dep[in[b]]中,最小深度的時間戳經過的那個點
查詢:
RMQ的部分就要自己維護了,使用線段樹效能會非常差,在n,q<=100000的情況下使用稀疏表的效能與使用樹鏈剖分的效能差不多

[ Lowest Common Ancestor , LCA Doubling Search ] 最近共同祖先倍增演算法

首先建立一張倍增表,pa[i][x]表示x的第\(2^i\)的祖先,若不存在則為\(-1\),可以在DFS或BFS的過程中求得,複雜度為\(\ord{N*MAX\_LOG}\)

對於每筆詢問,我們可以利用剛剛求得的倍增表,在\(\ord{MAX\_LOG}\)的時間在線查詢
先將要查詢的a,b兩點較深的點移至較淺的點的深度,之後二分搜LCA的位置
附上模板:

[ Lowest Common Ancestor , LCA Tarjan's Algorithm ] 最近共同祖先tarjan演算法

tarjan算法的步驟是(當dfs到節點u時):

在並查集中建立僅有u的集合,設置該集合的祖先為u
對u的每個孩子v:
  1. 遞迴處理v
  2. 合併v的集合到父節點u的集合,確保集合的祖先是u
設置u為已遍歷
處理關於u的查詢,若查詢(u,x)中的x已遍歷過,則LCA(u,x) = x所在的集合的祖先

因為只進行過一次DFS,所以複雜度為\(\ord{(N+Q)*\alpha(N)}\),為了優化並查集,這裡採用啟發式合併,因此為了記錄集合的祖先而外增加了一個數組head
其雖為線性,但是效率並不怎麼好,跟倍增法的效能差不多
使用方法也很簡單,只需要將每個詢問的兩點記錄起來即可

2015年8月5日 星期三

[ Mo's algorithm ]莫隊算法

對於一些詢問區間答案的資料結構題,我們已經知道了區間[l,r]的答案,且能在極少的時間( \(\ord 1 \) or \(\ord{logN}\) )內得到區間[l+1,r]、[l-1,r]、[l,r+1]、[l,r-1]的答案,題目也准許離線,只要滿足這些性質就可以使用莫隊。

首先我們須將所有詢問記錄下來,將序列分成sqrt(n)塊,找出每筆詢問l所在的塊,每塊內r由小排到大

這裡n是序列的長度

之後就按造順序一個一個將序列元素在一些維護費用很小的資料結構進行插入刪除,直到等於當前區間為止,此時就可以把這個資料結構的答案存到ans陣列裡,然後結束後一次輸出

這裡進行一下簡單的證明:
  • 假設序列長度為N,我們將序列每K個分成一塊,在排完序後,左界屬於同一塊的詢問,每次都不會移動操過K次;而左界屬於不同塊的操作,從第i塊移動到第i+1塊最多要移動2*K次,總共分成N/K塊,故移動次數加起來不操過2*K*(N/K)=2*N次,因此左界移動的複雜度為\(\ord{Q*K}+\ord N\),Q為詢問次數
  • 對於右界,在同一塊內因為是遞增的關係所以移動次數不會操過N次,而最多只有N/K塊,因此複雜度為\(\ord{N*N/K}\)
  • 這個時候我們可以取K=sqrt(N)得到一個複雜度為\(\ord{Q*K+N+N*N/K}=\ord{(Q+N)*sqrt(N)}\)的方法
這是區間眾數的模板(對於每個詢問l,r輸出區間[l,r]眾數的個數):

2015年7月28日 星期二

[ sparse table ] RMQ問題的稀疏表算法

RMQ問題(Range Minimum/Maximum Query,區間最值問題),通常是給定一條串列s,有若干次的詢問查詢區間L至區間R的最大(小)值。
相信關於RMQ問題使用線段樹的做法很多人都有一定的了解,這邊提供另外一種在線不可修改的做法,稱為稀疏表算法,其預處理時間為\(\ord{NlogN}\),N為串列長度,
查詢時間為\(\ord 1\),是一種高效的演算法。

關於此算法的說明請看http://noalgo.info/489.html
由連結提供的程式碼效能是十分差的,因此這邊提供我的模板(以區間最小值為例):

2015年7月25日 星期六

[ Palindromic Tree ] 回文樹(回文自動機)

回文樹是去年新出的資料結構,由一個俄羅斯codeforces的紅人Mikhail Rubinchik在2014年發明的(http://codeforces.com/blog/entry/13959),雖然名子直接翻譯叫回文樹,但他長的比較像一個自動機,所以也有很多人翻回文自動機。
在構造它之前,我們必須先證明一個長度n的字串其不同的回文子字串個數<=n,什麼是不同的回文子字串?就是長的不同的回文子字串,及把出現位置不同但形狀一樣的回文子字串當做是同樣的子字串。

證明:
  1. 由左往右一個一個增加字符,則新產生的回文子字串其結尾一定是當前增加的字符x
  2. 考慮以當前位置為結尾的最長回文x......x,顯而易見的,若產生除了x......x之外其它的回文子串,則必定被x......x所包含
  3. 若增加字符x後,產生了除了x......x之外其它的回文子串,則根據回文的性質,其一定早已在x......的部分理出現(例:假設S是對稱點x...S.xax,因為回文的性質所以S的另一邊也會出現相同的字串xax.S.xax)
  4. 因此每增加一個字符最多只會產生一個新的回文子字串,而長度為n的字符串最多只會產生n種不同的回文子字串
接下來進行回文自動機元素的詳細解說:

回文自動機包含以下元素:
  1. 狀態St,所有節點的集合,一開始兩個節點,0表示偶數長度串的根和1表示奇數長度串的根
  2. last 新增加一個字符後所形成的最長回文串的節點編號
  3. s 當前的字符串(一開始設s[0]=-1(可以是任意一個在串S中不會出現的字符))
  4. n 表示添加的字符個數

每個節點代表一個不同的回文子字串,我們在每個節點會儲存一些數值:
  1. len 表示所代表的回文子字串長度
  2. next[c] 表示所代表的回文子字串在頭尾各增加一個字符c後的回文字串其節點編號
  3. fail 表示所代表的回文子字串不包括本身的最長後綴回文子串的節點編號
  4. cnt(非必要) 表示所代表的回文子字串在整體字串出現的次數(在建構完成後呼叫count()才能計算)
  5. num(非必要) 表示所代表的回文子字串其後綴為回文字串的個數
注意一開始必須先將狀態初始化St[0].len=0,St[1].len=-1,last=0,s[0]=-1,n=0

關於構造方法及圖片說明請參考:http://blog.csdn.net/u013368721/article/details/42100363
概念請參考:http://blog.csdn.net/MaticsL/article/details/43651169
證明請參考:http://yqcmmd.com/index.php/2015/03/30/746/

最後提供模板(使用STL vector),因為St的元素在解題的過程中常會被用到所以就不封裝了:

2015年7月22日 星期三

[ Heavy-Light Decomposition ] 樹鏈剖分模板+LCA

在某些狀況下,我們希望對樹上a點到b點的路徑進行修改或查詢的動作,而且這些動作用一般的樹壓平RMQ或是離線處理無法完成的,這個時候我們可以利用特殊的方法將樹拆成長鏈。
長鏈可以搭配良好的資料結構。只要找出樹上所有長鏈,每條長鏈套用線段樹、BIT、Sparse Table、BST、Heap,就能降低時間複雜度。

可以利用簡單的做法將dfs序切成許多長鏈:
  1. 首先先設定其中一點為根,算出每個子樹有多少節點
  2. 樹上每個節點各自連向最大的子樹,相連的部分會自然形成鏈
通常步驟二會進行一次dfs,每次朝著最大的子樹走,每個節點記錄其時間戳記及所在的鏈(通常是記鏈首),這樣就可以將樹壓平的結果切成許多鏈,使得樹鏈剖分同時可以做到樹壓平的操作。

我們可以進行一個簡單的證明:
  • 假設節點數為V,由根往任意葉節點走,一旦遇到新鏈,新鏈的子樹必小於等於原鏈子樹,剩下的節點數量不到一半,所以沿途最多遇到 logV 條鏈。
因為一條路徑藉由 LCA 拆成兩段,沿途最多遇到 2*logV 條鏈,所以在任意兩點a,b間最多只需要進行2*logV次的區間操作,若是套線段樹之類的結構可以做到\(\ord{log^2V}\)
這些操作都可以在求LCA的過程中完成:

若樹鏈剖分的目的只是為了求LCA,build_link()及find_lca()有更好的做法:
這就只需進行一次DFS

2015年6月30日 星期二

[ Suffix Array SA-IS Algorithm ] 後綴數組線性SA-IS算法

SA-IS是我目前看過最快的線性後綴數組演算法,但是做為競賽用途而進行簡化後他的效率在某些硬體上會比DC3慢,不過記憶體使用量是DC3的1/3~1/2倍,而最短的實現code也比DC3短很多,因此我認為這是十分優秀的算法

因為某些SA-IS的實作方式會利用傳入的陣列s的空間進行計算,因此傳入的陣列s必須是int範圍,而傳入的字串的尾端字元必須是最小的而且在之前完全沒有出現過,因此必須給字串先做以下處理:

假設要傳入字串 mississippi
先在尾端加入字元'#': mississippi#
算法結束後陣列sa為:11 10 7 4 1 0 9 8 6 3 5 2
將第一個數字11去除後剩下的數字即為字串mississippi的後綴數組:
10 7 4 1 0 9 8 6 3 5 2
關於SA-IS算法的論文請看這裡:
Two Efficient Algorithms for Linear Time Suffix Array Construction

關於SA-IS算法的教學(專利申請文)請看這裡:
后缀数组构造方法  CN 102081673 A

SA-IS的教學投影片:
https://www.cs.helsinki.fi/u/tpkarkka/opetus/11s/spa/lecture11.pdf

SA-IS中文教學:
https://riteme.github.io/blog/2016-6-19/sais.html

如果想對Suffix Array算法進行測試請使用這個Online Judge:
http://www.spoj.com/problems/SARRAY/

以下將會提供一些SA-IS的實做模板

1.台大黑暗code界的黑暗codebook:
其實這段code本來是被壓縮得更短,而且用到非常多的記憶體,不過經過卦長的改良後成功減少記憶體的使用並將他排版成正常人能看得懂的樣子
而這裡的MXN則是字串的最長長度(假設字元數<字串長度)

2.卦長自行實作的模板(記憶體用量少):
為了簡化實作方法及減少記憶體的使用,因此將計算後剩下的空間進行重複利用,壓縮後只需要這些記憶空間,而傳入的陣列s可以直接傳入char陣列,因此對使用者來說是非常方便的一份code
這裡的MXN則是字串的最長長度(假設字元數<字串長度)

3.論文提供的實作code:
這是其中一個比DC3快的code,而且記憶體使用量是最少的,但是長度很長就是了,不適合在比賽時使用

4.超快記憶體使用超少的模板庫code:
https://gist.github.com/jacky860226/1d33adad858eef71bfe18120d8d69e6d#file-sa-is-very-fast-cpp
因為長度太長所以就直接貼上網址了,沒有人會在比賽時寫這種東西

2015年6月24日 星期三

[ Suffix Array DC3 algoruthm ] 後綴數組線性DC3演算法

這邊提供後綴數組DC3算法的模板,他是一個能在線性時間\(\ord N\)內求得後綴數組的演算法,注意這邊傳入的陣列s及sa長度必須是字串長的3倍以上,因為DC3會用到大量的記憶體,而且會利用傳入的陣列s的空間進行計算,因此傳入的陣列s必須是int範圍,而傳入的字串的尾端字元必須是最小的而且在之前完全沒有出現過,因此必須給字串先做以下處理:

假設要傳入字串 mississippi
先在尾端加入字元'#': mississippi#
算法結束後陣列sa為:11 10 7 4 1 0 9 8 6 3 5 2
將第一個數字11去除後剩下的數字即為字串mississippi的後綴數組:
10 7 4 1 0 9 8 6 3 5 2

因為是遞迴的關係,所以常數很大,但在大數據的時候比倍增法快
關於DC3演算法的介紹請看這兩篇文章:
http://ching.im/post/algorithm/difference-cover-modulo-algorithm
《后缀数组——处理字符串的有力工具》

如果想對Suffix Array算法進行測試請使用這個Online Judge:
http://www.spoj.com/problems/SARRAY/

在傳入的參數中最後一個A為最大的字元+1通常設為'z'+1

以下提供模板(其實code挺短的):

2015年6月21日 星期日

[ Suffix Array Prefix doubling algorithms ] 後綴數組倍增算法

後綴數組(又稱尾碼陣列)是一個十分強大的字串處理武器,大部分的問題都可以用它來解決,它可以幾乎做到所有後綴樹(Suffix Tree)能做到的事,所以這邊就不介紹後綴樹了

因為後綴數組可以由後綴樹進行遍歷轉換而來,而構造後綴樹僅需花費線性的時間,所以構造後綴數組的時間可為線性\(\ord N\),但是後綴數組本身就是為了減少構造後綴樹的空間與代碼量而被發明出來的,直接由後綴樹轉換是沒意義的
但是仍然有其他線性構造後綴數組的方法,像是DC3、SA-IS等會在下一篇介紹,這次要講的是比較簡單常用的方法-----倍增法
關於後綴數組的使用說明可以參考《后缀数组——处理字符串的有力工具》
關於倍增法的說明可以參考 演算法筆記-SuffixArray 的部分
這邊提供\(\ord{N*logN*logN}\)及\(\ord{NlogN}\)的模板

\(\ord{N*logN*logN}\):
\(\ord{NlogN}\):
注意此方法必須要在字元集大小為常數的情況下有效,否則必須離散化

所需的陣列長度只需要與字串陣列相同即可
當然\(N*logN*logN\)的做法會比較值觀,\(NlogN\)的方法則是利用radix_sort進行的,radix_sort本來在倍增的時候要先排序第一關鍵字跟第二關鍵字,但是第二關鍵字排序的結果可以用已經求好的SA直接求出來
對radix_sort還不了解的人請看這個網頁:https://www.cs.usfca.edu/~galles/visualization/RadixSort.html
如果想對Suffix Array算法進行測試請使用這個Online Judge:
http://www.spoj.com/problems/SARRAY/

2015年6月3日 星期三

英文字母大小寫轉換特殊做法

假設有一個題目是這樣的:
        給定一串英文字母,請將大寫的部分轉成小寫,小寫的部分轉成大寫並輸出

一般我們會用if或是三元運算子做判斷,但是這太麻煩了
經過觀察發現,摁合一個小寫字母ascii與其對應的大寫字母ascii相差皆為32,
而其二進位編碼剛好允許透過 xor 32的方式進行轉換,但是32這個數字不好記,又可以發現ascii 32='空白',而以下的code就可以將大小寫互換:
1
2
3
4
5
6
7
8
#include<stdio.h>
char s[1000005];
int main(){
    scanf("%s",s);
    for(int i=0;s[i];++i)putchar(s[i]^' ');puts("");
    for(int i=0;s[i];++i)putchar(s[i]^32);puts("");
    return 0;
}
兩種寫法會有相同的效果

2015年5月28日 星期四

[ Persistent Binary Index Tree ] 持久化BIT

(二分索引樹)BIT是一種容易實現的資料結構,但在持久化的應用上是非常困難的,但我們可以犧牲些許的複雜度來簡化其實現方式

一般區間和的BIT長這樣:

這是持久化的版本(也可以用pair來實作):
可以知道其更新的複雜度為\(\ord{logN}\),查詢複雜度為\(\ord{logN*logQ}\),Q是查詢次數

2015年5月14日 星期四

[ Suffix Automaton ] 後綴自動機

定義字串S的後綴自動機是一種自動機可以接受S的所有後綴,其狀態最多為2*strlen(s)-1個,雖然理論複雜,但其構造方式十分簡單,且它可以用來處理一些後綴數組或事後綴樹的問題,因此是一個十分強大的資料結構。
後綴自動機大致的構造方式是將字串擔一字元按順序進行插入,插入的均攤時間為\(\ord 1\),關於詳細的情形可以在 http://blog.sina.com.cn/s/blog_70811e1a01014dkz.html 這個網站中得到
而關於複雜度及詳細的證明請參考陈立杰的簡報
關於狀態數為線性的證明在19~21頁,有詳細的圖文解說
這個網站包含其一些延伸資料結構http://maskray.me/blog/2013-05-10-suffix-automaton
為了減少記憶體的使用,以vector代替指標維護狀態
以下提供模板:

2015年5月9日 星期六

[ Aho-Corasick Automaton ] AC自動機

Aho-Corasick Automaton,該算法在1975年產生於貝爾實驗室,是著名的多模匹配算法之一
在了解AC自動機之前,必須先學會字典樹Trie的使用,簡單的來說,他是將KMP的fail函數應用在Trie做為失敗邊。
有\(n\)個字串\(B_0,B_1,...,B_{n-1}\) 要匹配字串\(A\),則一般用KMP的算法會得到\(\ord{\sum_{i=0}^{n-1}(|A|+|B_i|)}\),使用AC自動機的演算法其複雜度為\(\ord{|A|+\sum_{i=0}^{n-1}|B_i|}\),必須用DP

關於AC自動機的介紹請看這裡

以下為AC自動機的模板

2015年5月8日 星期五

[ Knuth-Morris-Pratt Algorithm ] 克努斯-莫里斯-普拉特(KMP)算法

這是一個大家很常聽到的字串匹配演算法,較Z Algorithm複雜,但更為通用,C++的string就有內建(string::find)。假設要以B匹配A,則會先建立B的部分匹配表(又叫做失配函數),其定義如下:
     fail(i)=max(滿足B[0,k]=B[i-k,i]的所有k)
同樣的也可以在線性時間來完成
對於KMP演算法的詳細情況請參考這裡
以下提供fail function陣列及匹配的實作

2015年5月7日 星期四

[ Manacher's algorithm ] Linear time Longest palindromic substring 線性最長回文子串

Manacher演算法是Z algorithm的變種,可以說是雙向的Z algorithm,複雜度也是\(\ord N\)
其Z function定義如下:
     Z(i)=以位置i為中心的最長回文半徑
但是這樣只能處理回文長度是奇數的子串,因此必須幫字串做一些修改

假設原來的字串是: "asdsasdsa"
修改後變成: "@#a#s#d#s#a#s#d#s#a#"
其中'@'及'#'為不同字元且皆未在原字串中出現過
其Z function陣列為: 0 1 2 1 2 1 6 1 2 1 10 1 2 1 6 1 2 1 2 1
則 最大的數字-1 (10-1=9)就是我們要的答案

這裡提供Manacher algorithm產生Z function陣列的實作:

[ Z algorithm ] Linear-time pattern matching 線性字串匹配 Z演算法

定義一個字串S的Z function:
    Z(i)=0 如果i=0 or S[i]!=S[0]     否則
    Z(i)=max(所有的k滿足 S[0,k-1]=S[i,i+k-1])
從Z function的定義,假設要在字串A裡面匹配字串B
可以先建構字串S=B+(A和B都沒有的字元)+A的Z function陣列
若Z[i]=lenB則表示在A[i-lenB]有一個完全匹配
這裡提供兩個可以\(\ord{N}\)時間求出Z function陣列的方法:

對一個特殊構建的數據strlen(s)=10000000其效率平均為
z_alg1:   0.106s
z_alg2:   0.089s
這兩種方法的想法是相同的
我們可以知道第一個方法是較為直觀好寫的,但是運算量較大且調用min函數的效率並不高
但仍在可接受的範圍

2015年5月3日 星期日

[ skew heap ] implementation 斜堆 實作

斜堆(Skew heap)也叫自適應堆(self-adjusting heap),它是(重量)左偏樹的一個變種。
相較於(重量)左偏樹,斜堆不需記錄其高度或是節點個數(size)等附加域,其合併(merge)的方式也較為簡潔,效率也較高。和(重量)左偏樹一樣,斜堆的push、pop的時間複雜度為\(\ord{log \; n}\)、查詢最值為\(\ord 1\)。
關於複雜度分析
以下提供斜堆的實作,使用方法與STL priority_queue相似

2015年3月27日 星期五

[ basic operation of naive order statistic tree ] 樸素二元搜尋樹 名次樹的基本操作

一般的名次樹支援以下幾種操作:

1.插入
2.刪除
3.查找
4.求節點大小
5.求元素名次
6.求第k大
7.求前驅
8.求後繼

之前寫的模板已經有了前六種操作,因此我會在本模板中附上求前驅跟後繼的操作
前驅與後繼並不是名次樹才有的操作,在不記錄節點大小的情形下也能求得
關於求前驅跟後繼操作的說明可以參考 随机平衡二叉查找树Treap的分析与应用 這篇文章

以下提供模板:

2015年3月14日 星期六

[ AA tree ] AA樹

AA樹是紅黑樹的一種變種,是Arne Andersson教授在1993年年在他的論文"Balanced search trees made simple"中介紹,設計的目的是減少紅黑樹考慮的不同情況。區別於紅黑樹的是,AA樹的紅結點只能作為右葉子。另外AA樹為實現方便,不再使用紅黑兩種顏色,而是用level標記結點,結點中的level相當於紅黑樹中結點的黑高度。

其主要透過skew和split兩種旋轉來進行平衡的,插入時只能為紅節點,故會出現不符合其規定則進行平衡操作

若想進一步了解其平衡操作請參考維基百科
在實作中,skew為右璇,split為左旋。本模板以rotate(o,0)、rotate(o,1)代表

以下提供模板:

2015年3月13日 星期五

[ symmetric binary B-tree ( red black tree ) ] 對稱二叉B樹 ( 紅黑樹 )

紅黑樹是一種有最壞情況擔保的平衡樹,其插入最多會用到2個旋轉,刪除最多用到3個旋轉,其犧牲些許的平衡來加快插入刪除的速度,並有高度上h<=2*log(n+1)的保證。
故其插入刪除之常數會比較小,而查詢之常數會較大(相對於一般高度平衡樹),而一般的函式庫裡的"關聯數組"通常適用紅黑樹實做的
其平衡原因及方法請參考維基百科
因其操作複雜故不常在競賽中被使用,且刪除速度較size balanced tree慢約2倍

以下提供模板:

2015年2月19日 星期四

[ scapegoat tree ] 替罪羊樹

替罪羊樹論文其中一個作者,Ronald Linn Rivest,同時也是RSA加密算法的R
替罪羊樹是一種不需要旋轉的平衡樹,它會要求使用者給定一個\(\alpha\)值,其值介於0.5到1之間,\(\alpha\)越大,插入就越快,查詢就越慢,實驗發現\(\alpha\)介於0.55~0.75是最佳的,但是具體的值要看使用者的要求
其平衡滿足:
1.
    \(\alpha*size(o) \le size(o \to left)\)
    \(\alpha*size(o) \le size(o \to right)\)
2.
    \(deep(o) \le log_{1/\alpha} (size(tree))\)
當插入節點導致條件2.不滿足時,會往上回溯到第一個不滿足的節點,然後重建這顆節點的子樹成為完美平衡的二元樹
刪除可以用一般的BST刪除法,當不滿足條件時往上回溯到最先不滿足的節點,重建子樹,也可以懶惰刪除,先設立一個標記, 要刪除這個節點就把它做記號,當\(\alpha\)*全部的節點數量>實際上存在的節點數量,就重建這顆子樹
本文提供一般刪除的方法

其實替罪羊樹的節點是不需要記錄其size的,因為若需要重建,求得size的時間複雜度與重建的時間複雜度相等,這裡為了支援其它有如rank等操作才將size域附加在節點中

插入刪除的均攤時間複雜度為\(\ord{logN}\),相較之下朝鮮樹只是他的劣質仿冒品,其複雜度證明請參考此論文

以下為模板:

這裡也提供不需要記錄節點大小(size)的平衡方式,相對的一些需要用到附加size域的函數將不能被使用,但插入刪除的效率不變


如果編譯發現沒有__lg()這個函數的話,請在程式碼開頭附上這份code:

2015年2月18日 星期三

[ korea tree ] 朝鮮樹

某天albus YY出來了一個沒有旋轉操作的平衡樹,由於albus的真名(华中科技大学附属中学 金正中)聽起來很像朝鮮主席,所以就叫朝鮮樹了!

朝鮮樹是一種不需旋轉的 自平衡二元搜尋樹,利用當深度大於max_deep(通常取sqrt(N))時暴力重建的方式讓平均時間為\(\ord{N*sqrt(N)}\),是一種很糟糕的平衡樹,但是我們還是要理解他,因為這樣暴力重建的概念會在其他樹上用到。
若題目的要求數據量<=500000時可以使用

所有操作都與本篇其他樹差不多只多了個rebuild函數,它會暴力將整顆樹重建成深度logN的平衡樹

對於重建的部分則使用了拍扁重建法,將樹先拍扁成鍊表後重建,只需要花費\(\ord 1\)的空間複雜度

以下提供模板:

2015年2月17日 星期二

[ Splay Tree ] 伸展樹模板

最近研究了伸展樹,它可以在均攤\(\ord{logN}\)的時間完成伸展操作,所謂的伸展操作就是將某個節點旋轉(rotate)到根(root)的過程,因為我們大部分在搜尋資料時,常常都只會用到特定的資料,其他大多數的資料是較少被搜尋的,因此將常被搜尋的資料靠近根是很好的策略,伸展樹由此被發明。
因為伸展樹可以分裂合併,所以可以取代分裂合併式treap或是分裂合併式randomize binary tree的功能,可以在競賽中被使用,而普通的伸展樹效率不高,故本文只介紹作區間處理的伸展樹
之後的link-cut tree會用到他,所以必須要能理解
例題: UVA 11922

定義伸展樹節點:(T為資料型態)

初始化時nil的l,r要指向自己

旋轉(跟其他樹差不多)
d=0左旋,1右旋

接下來是最重要的伸展操作
這是按劉汝佳在橘色那本書的寫法實現的
主要是將第k個節點伸展到root的過程
注意!! k必須大於0

有了splay操作,接下來是分裂&合併

當我們要維護一個區間1~n時,可以建立0~n的splay tree,0是廢棄節點,較為方便使用

最後提供新增節點的方法:

這樣所有的操作就齊全了
剩下的一些懶惰標記跟treap一樣,可以做區間翻轉和線段樹的功能
但是請小心指標的使用
(nil為衛兵指標,方便用來編輯,若不想用可以將程式碼略為修改)

2015年1月23日 星期五

[ Big Interger ] 大數模板

今天在家裡寫了一整天的大數,好不容易加減乘除都有了,但是乘法的部分FFT還不會寫所以先用做基本的n^2乘法(聽說有一個奇怪的方法叫做Karatsuba演算法也能做大數乘法,還蠻快的)

定義一個大數:
bigN a;//定義大數

以下是大數模板:

2015年1月21日 星期三

[ AVL Tree ] 優化AVL樹

AVL樹是以子樹的高度做為平衡的條件
其平衡條件為:
     左子樹的高度與右子樹的高度差不能超過1

因為每次的插入及刪除都有可能壞平衡,所以必須要進行旋轉來修正其平衡性。
共有4種旋轉方法,一序為 : 左左、左右、右右、右左,若想知道關於如何進行平衡的介紹請點擊這裡,其插入刪除常數較大,故其平均效率比Size Balanced Tree要差。

因為在網路上看到很多的AVL樹,其寫法都過於冗長,所以我這邊發一個AVL樹的模板,其code複雜度跟Size Balanced Tree差不多。
主要是將相同的平衡操作合併成一個balanced()函數,插入和刪除完後呼叫即可。

以下為模板:

Treap 模板

這是 旋轉式Treap 的模板,是目前所有平衡樹中code最為簡便的一種。
插入和刪除的時間複雜度跟Randomized binary search tree一樣,是在演算法競賽中最適合使用的平衡樹。
因為 分裂/合併式 Treap 可以完全被 分裂/合併式 Randomized binary search tree取代,故不提供

做法1,完全依靠旋轉進行平衡(刪除速度較慢):

作法2,刪除時合併左右子樹(刪除速度較快):

2015年1月17日 星期六

[ 線性同餘方法 ] 亂數產生器 實做

今天來講幾個簡單的亂數產生方法
主要是利用線性同餘方法來處理的

它的首要條件便是必須符合平均分配率Uniform distribution,也就是在$0 \sim m-1$之間的每個數字, 出現的機率必須相等。
Linear Congruential Method雖是常用法,但也有它的條件:
$X(n+1) = (a \times X(n) + c) \%m$,其中$\%$是取餘數的意思
$X(n+1)$為新的亂數,$X(n)$為前一次產生的亂數。則各參數必須符合下列條件:

  1. $c$與$m$必須互質。
  2. 對於任何$m$的質因數$p$,也必須為$a-1$的質因數。
  3. 若$m$為$4$的倍數,則$a-1$也必須為4的倍數。


如此才能確保產生出來的亂數符合平均分配率,同時也具有最長的重複週期。

以下是在網路上找到的一些不錯的亂數產生方法:
其中random1是Brain大神在處理randomize binary tree的亂數(0xdefaced是質數,defaced是英文單字比較好記)
random2聽說是stdlib裡面的rand()原型,而16807是7的5次方,random2可以產生較rand()大的亂數
random4不是線性同於方法,個人覺得他比較像Subtract with carry的方法
在做[分裂/合併式]randomize binary tree時,其實可以利用seed++的方式當作亂數用(連結中有教學)

c++ rope 基本應用

rope(粗繩)是一個很強大的字串處理物件,聽說是為了與string(細繩)做對比才叫做rope的,其底層是一棵持久化平衡樹,因此在做合併或在中間插入的期望時間是logn

再使用rope前必須在前置作以下的處理

#include<ext/rope>
using namespace __gnu_cxx;

定義一個元素為char的rope:
rope<char> r;

其實rope本身為了方便已經將rope<char>重新定義為crope
因此也可以這樣寫:
crope r;


當然rope也可以存取非char的元素
只是有些操作會不支援(例如輸出操作)

對於rope的一些常用操作請參考由SGI網站翻譯的rope成員詳細說明
裡面整理了rope的各種函式及元素
且已經將其翻譯成中文方便閱讀

Randomized Binary Search Tree 平均深度證明

一棵Randomized Binary Search Tree ,平均深度為2logn
其每個節點成為該顆子樹的根的機率有1/(該顆子樹的大小+1)
對於[分裂/合併式][Split / Merge] Randomized Binary Search Tree 亦同
而其等價於在BST中進行隨機插入
這裡提供嚴謹的證明 連結
以下簡略的證明原自於陳柏叡大大(數奧國手)親筆所寫:

現在總共有n個數,要證說對他隨機排序之後一個一個插入BST得到的平均最大深度=2logn。
那看任意一個數x,他的祖先個數就是它的深度,所以只要算x的祖先個數的期望直。
這只要算,對x以外的每個數y,y當x的祖先的機率是多少,再把他們加起來即可。

但注意到,假設在這n個數(由小到大)排序好的序列裡面,x 排在第 i 個, y 排在第 j 個(  y 可以 <x,所以 j 可以 < i  ),那麼落在 [ i , j ] ( 或 [ j , i ] )這個區間裡的所有數, y 是第一個被插入BST的(否則會和 y 是 x 的祖先矛盾),而這件事情發生的機率為 1/(  | i - j | +1 ) 。
也就是,如果一個數 y 和 x 在排序好的序列裡面的坐標差 = d 的話,那麼 y 當 x 的祖先的機率就是 1/(d+1)。

所以如果 x 是排序好的序列裡的第 i 個,那所求是
1 / i + 1 / ( i - 1 ) + ... + 1/2 + 1/2 + 1/3 + ... + 1/( n - i + 1 )
<= 2 ( 1/2 + 1/3 + ... + 1/n )
約 = 2logn

2015年1月16日 星期五

[smart pointer] [reference counter] 智能指標 引用計數

鑒於有些題目需要記憶體的限制,因此必須要考慮到記憶體的管理。
智能指標可以幫助我們解決這個問題

在C++11,STL已經有內件shared_ptr,但是速度很慢,而大部分在比賽時會用到的只有引用計數的概念(可以參考Brain大神的blog),因此我將引用計數(參考自 C++ Template 侯捷譯)部分特別獨立出來,做了一份模板

以下為模板:
用法:

reference_pointer<int> a;//建立一個int的引用指標a
a = new_reference(5);//a指向新增int動態變數,其值為5
a = new_reference<int>(5);//同上,只是定義較為嚴謹
a = new_reference((int)5);//同上,只是定義較為嚴謹
reference_pointer<int> b = a;//將b指向a所指向之物

struct P{
     int a,b;
     P(int _a,int _b):a(_a),b(_b){}
}p(2,3);
reference_pointer<P> a;//建立一個P的引用指標a
c = new_reference(P(1,2));//指向新增P動態變數,其值為1,2
c = new_reference<P>(P(1,2));//同上,只是定義較為嚴謹
c = new_reference(p);//指向新增P動態變數,其值為p

其他的用法可以由下面的代碼看出來(HOJ Problem : 226 - K. CP AC代碼):
其使用了[持久化][分裂/合併式]隨機二分搜尋樹
持久化的部分會在之後介紹

2015年1月15日 星期四

[分裂/合併式] 隨機二分查找樹 [Split / Merge] Randomized Binary Search Tree

今天來講解可以做區間處理的Randomized Binary Search Tree
好比treap,可以利用拆分跟合併的方式來做區間處理
感謝伯恩大神的指導,請參考其網站

寫起來並不會比需要旋轉的難
先定義他的節點:
可以在裡面增加一些懶惰標記的更新(min,max,rev...等等)

計算節點大小

主要利用[分裂/合併]來進行區間處理
接下來講解分裂(參見 treap分裂):
這是將o按中序將前k個節點分到a,剩下的分到b

合併(參見 treap合併):
這就是隨機的精華所在
每次merge時,a有size(a)/(size(a)+size(b))的機率將a作為root
b反之亦然
而本來random是這樣寫的:
但是看了丁安立魔法師的blog,發現只要x++就好了,也不知道為甚麼

如果只是要做普通的二分搜尋樹,可以利用排名來求出其在整顆樹中的名次,然後再相對應處做插入
插入data可以寫成:
bst.insert(data,bst.rank(data));
刪除也可以用類似的方法處理

旋轉式的randomize bst就可以做這些處理了(其實分裂合併式bst速度有點慢),那為何還需要 分裂/合併 呢?
我們可以把整顆樹的中序走訪看成是一條陣列
-->因此可以利用它來作區間的維護

像是區間的最大最小值,區間反轉啦,區間移動、刪除等等都可以利用它在logn的時間完成
只須修改其up跟down函數就可以達成目的
凡是線段樹能做到的事情,他都能做到,可以用它來解決很複雜的區間處理問題

注意的是,在有懶惰標記的情況下,如果要詢問一個區間必須在切出那塊區間後先進行down的操作再進行詢問,否則懶惰標記可能沒有被推下去,範例如下:

這個範例up()跟down()也要重寫:

因為應用時分靈活,故不提供樣板,只做介紹

2015年1月13日 星期二

[ Randomized Binary Search Tree ] 隨機二分查找樹

今天來介紹隨機二分查找樹,因為看了很多外國的文章看了半天都看不懂,現在好不容易看懂英文了,就把它用中文的方式來介紹吧!
隨機二分查找樹,是利用隨機數或機率分布來達到平衡的條件,其證明以附在連結中。
利用隨機數的方法包括Treap,但是這太常見了,所以掠過。

這邊要介紹不需額外再節點紀錄隨機值的方式,透過其節點大小來計算其是否為根或是根據節點大小的比例隨機插入。

維持平衡用左旋根右旋(參見:樹旋轉):
接下來來講解一下它的插入
這裡會用到兩個函數:
insert():插入節點
insert_as_root(node *&p,T k):將k插入子樹p並做為p的根節點
為甚麼要這樣做呢?
當在對節點p進行插入時,新插入點根據隨機分布會有1/(size(p)+1)的機率成為這顆子樹的根
因此可以以遞迴處理
若此節點的值>插入值,則插入其左節點,然後右旋,反之亦然
其常數很小,所以常常插入時間比size balanced tree快,但是深度太大,刪除時間較慢
其平均深度等價於在一棵普通的BST進行隨機插入最終的平均深度,因此為2nlogn

而對於刪除節點,和Treap一樣,有兩種不同的做法:

第一種是透過與左偏樹類似的方法刪除,不需要旋轉,通常效率交高
合併左右子樹,然後刪除其根節點
合併的方式利用了隨機分布的概念
假設需將a,b合併
則有size(a)/(size(a)+size(b))的機率將b合併到a子樹
反之有size(b)/(size(a)+size(b))的機率將a合併到b子樹

第二種作法完全依賴於旋轉
在刪除時如果要被刪除的節點不是一條鏈的話,就按造隨機的概念進行旋轉
有size(左子樹)/(size(左子樹)+size(右子樹))的機率進行右旋
反之有size(右子樹)/(size(左子樹)+size(右子樹))的機率進行左旋

以下為第一種作法(效率較高):

以下為第二種作法:

2015年1月10日 星期六

字典樹 Trie

今天完成了字典樹 Trie的模板,可以在O(N) (N=字串長度)的時間搜尋一個字串
插入的時間亦是O(N),在字串匹配上有很大的幫助(AC字動機),但是因為每個節點都要記錄所有字元,是非常耗空間的
通常將根節點設為"沒有字元",若是想進一步了解Trie請自行google吧!
以下為模板:
跟stl map的用法類似
trie<int >t;  //定義一個存int的Trie
trie<int ,'a','z'>t  //定義一個字元範圍是'a'到'z'的Trie(預設是'A'~'z')
trie<int >::point_iterator it;  //定義一個節點迭代器
t.insert("asd",1);  //插入1到"asd"的位置(若原來已有值則覆蓋),傳回插入節點的point_iterator
t.find("asd");  //傳回"asd"位置的point_iterator,若無資料point_iterator為NULL,請注意
t["asf"];  //若"asd"存在資料,傳回其引用位置,若不存在則插入並傳回其引用位置
t.erase("asd");  //刪除"asd"節點,若成功刪除則傳回true,失敗(無結點)則傳回false
t.size(); //傳回字串的總數
t.clear();  //清空trie

2015年1月8日 星期四

重量左偏樹 weight-biased leftist tree

之前提到的左偏樹是深度左偏樹,雖然複雜度也是logn,但是重量左偏樹的速度在實作上是明顯較深度左偏樹快的
若是想了解深度左偏樹 height-biased leftist tree 或是左偏樹的理論請參考這篇文章
以下提供模板(使用方法與深度左偏樹相同):

2015年1月7日 星期三

在函式中傳入使用者自定函式的方法(C++ Functor 仿函式)

一般來說在函式中傳入使用者自定函式通常會用函數指標
但是C++ template提供了一個較為便利的函數參數,以物件的方式傳入
可支援一般函數或利用重載()運算子所定義的物件
詳情請看代碼:

2015年1月5日 星期一

歐拉函數 乘法模逆元

今天來講一下歐拉函數及乘法模逆元
首先是歐拉函數
定義: 歐拉函數$φ(N)$是小于或等于$N$的正整數中與$N$互質的數的個數$(N>0)$
其值為
$φ(N)=N \times (1-1/P_1) \times (1-1/P_2) \times (1-1/P_3) \times ... \times (1-1/P_k)$
其中$P_i$為$N$的質因數,總共有$k個$

因此可以利用質數篩法在線性或趨近線性的時間內完成某一區間的歐拉函數:
計算單一數的歐拉函數值可利用平方根質數法求:
接下來介紹乘法模逆元
一整數$A$對同餘$B$之乘法模逆元是指滿足以下公式的整數$R$$$A^{-1}≡R \; (mod \; B)$$
也可以寫成$$AR≡1 \; (mod \; B)$$
根據歐拉定理: 當$gcd(A,B)=1$,$A^{φ(B)} ≡ 1 \; mod \;B$
(若$B$是質數,則$φ(B)=B-1$,競賽題目$B$大多為質數,不需求歐拉函數)
為了方便,我們定義 $X\%Y$ 表示$X$除以$Y$的餘數
顯然 $R=A^{φ(B)-1} \;\% \; B$ 是$A$的模$B$乘法模逆元,可以由次方快速冪再$\ord{logn}$的時間得到:

另一種模逆元的解法:
計算$A$的模$B$乘法模逆元,可由擴展歐幾里得演算法得到
設$exgcd$擴展歐幾里得演算法的函數,它接受兩個整數$A,B$,輸出三個整數$g,x,y$。
$g,x,y$滿足等式$A \times x+B \times y=g$,且$g=gcd(A,B)$。
當$B=0$時,有$x=1,\; y=0$使等式成立
當$B>0$,在歐基里德算法的基礎上,已知$$gcd(A,B)=gcd(B,A\%B)$$
先遞迴求出$x^{'},y^{'}$滿足$$Bx^{'}+(A\%B)y^{'}=gcd(B,A\%B)=gcd(A,B)$$
然後可以將上面的式子化簡得$$Bx^{'}+(A-(A/B) \times B)y^{'}=gcd(A,B)$$$$Ay^{'}+Bx^{'}-(A/B) \times By^{'}=gcd(A,B)$$
這裡的除法是整除法,會自動無條件捨去。把含$B$的因式提取一個$B$,可得$$Ay^{'}+B(x^{'}-(A/B) \times y^{'})=gcd(A,B)$$
故$x=y^{'},\; y=x^{'}-(A/B) \times y^{'}$

若$g=1$,則$A$的模$B$乘法模逆元為$B+x$
$(A \times x+B \times y)\%B=1 \longrightarrow B \times y是B的倍數 \longrightarrow A(x+B)\%B=1 \; (因為x可能小於0)$
總複雜度和歐基里德算法相同,皆為$\ord{logn}$

擴展歐幾里得演算法函數實做:

2015年1月1日 星期四

[ size balanced tree ] 節點大小平衡樹 ( 傻B樹 )

它是由中国广东中山纪念中学的陈启峰發明的[已新增其中文論文連結]
跟一般的平衡樹一樣,靠左旋和右旋維持其平衡
他的精華來自於maintain函數
聽說是均攤\(\ord 1\)的,傳說中速度僅次於紅黑樹
coding複雜度跟Treap差不多,比AVL Tree好寫
平衡調件為: 每顆子樹的大小不小於其兄弟子樹的大小
我只提供模板,這裡有詳細的介紹


因為自己寫的速度有點慢,可以參考這邊一些大神寫的code