\( \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年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算法

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