K-D TREE
南天門日月卦長
什麼是K-D TREE
k-d樹(k-維樹的縮寫)
是在k維歐幾里德空間組織點的資料結構
比賽中常用來做範圍搜尋及最鄰近搜尋
K-D TREE的基本操作
這裡以計算曼哈頓距離的k-d tree作為範例結構定義
構造
就是把整個空間劃分為特定幾個部分
然後在特定空間進行相關操作
按造一定規則劃分成多個空間
(2,3), (5,4), (9,6), (4,7), (8,1), (7,2)
複雜度
因為樹是平衡的，所以深度為\(\ord{log \; n}\)
每一層找中位數要花\(\ord n\)
根據主定理可知構造一顆k-d tree的複雜度為
$$\ord{n \; log \; n}$$
每一層找中位數要花\(\ord n\)
根據主定理可知構造一顆k-d tree的複雜度為
$$\ord{n \; log \; n}$$
插入
複雜度
複雜度很明顯就是\(\ord{樹的高度}\)
所以最壞情況下可以是\(\ord n\) 不過我們可以用替罪羊樹去平衡他
可以達到\(\ord{log \; n*log \; n}\)的時間 關於平衡的方法請參考:
日月卦長的模板庫-動態kd樹模板
不知道替罪羊樹的請參考:
日月卦長的模板庫-替罪羊樹模板
所以最壞情況下可以是\(\ord n\) 不過我們可以用替罪羊樹去平衡他
可以達到\(\ord{log \; n*log \; n}\)的時間 關於平衡的方法請參考:
日月卦長的模板庫-動態kd樹模板
不知道替罪羊樹的請參考:
日月卦長的模板庫-替罪羊樹模板
刪除
找到要刪除的點後
找他右子樹中同一個分割維度最小的去取代他
如果沒有右子樹就交換左右子樹再進行同樣的操作
最後在遞迴刪除右子樹中被取代的點
複雜度
設樹的深度為\(\ord{log_{\alpha}n}\)
則findmin的最差複雜度為\(\ord{\alpha^{(kd-1)*(log_{\alpha}n)/kd}}=\ord{n^{1-1/kd}}\)
因此刪除的最差複雜度為:
$$\ord{n^{1-1/kd}+樹的高度}$$ 而且效能非常差
則findmin的最差複雜度為\(\ord{\alpha^{(kd-1)*(log_{\alpha}n)/kd}}=\ord{n^{1-1/kd}}\)
因此刪除的最差複雜度為:
$$\ord{n^{1-1/kd}+樹的高度}$$ 而且效能非常差
懶惰刪除
並且把他的祖先中跟他相關的資訊抹除掉
這樣就可以在\(\ord{log \; n}\)的時間內完成刪除操作
注意
懶惰刪除會讓 K近鄰算法 的時間複雜度變成\(\ord n\)
其他操作的複雜度不變
K近鄰算法 會在下一節提到
其他操作的複雜度不變
K近鄰算法 會在下一節提到
K近鄰算法
啟發式搜索(感謝Morris提供的方法)
類似於A*算法，我們可以提供一個heuristic值表示這顆子樹最少能查詢到的距離，若heuristic >= mndist則不進行走訪
我們只要想辦法維護這個heuristic值就好了
根據Morris的說法，在曼哈頓距離的情況下複雜度為\(\ord{log \; n}\)
我們只要想辦法維護這個heuristic值就好了
根據Morris的說法，在曼哈頓距離的情況下複雜度為\(\ord{log \; n}\)
另一種作法
從root節點開始，DFS搜索直到葉子節點，同時在stack中順序存儲已經訪問的節點。
如果搜索到葉子節點，當前的葉子節點被設為最近鄰節點。
然後通過stack回溯:
如果當前點的距離比最近鄰點距離近，更新最近鄰節點.
然後檢查以最近距離為半徑的圓是否和父節點的超平面相交.
如果相交，則必須到父節點的另外一側，用同樣的DFS搜索法，開始檢查最近鄰節點。
如果不相交，則繼續往上回溯，而父節點的另一側子節點都被淘汰，不再考慮的範圍中.
當搜索回到root節點時，搜索完成，得到最近鄰節點。
如果搜索到葉子節點，當前的葉子節點被設為最近鄰節點。
然後通過stack回溯:
如果當前點的距離比最近鄰點距離近，更新最近鄰節點.
然後檢查以最近距離為半徑的圓是否和父節點的超平面相交.
如果相交，則必須到父節點的另外一側，用同樣的DFS搜索法，開始檢查最近鄰節點。
如果不相交，則繼續往上回溯，而父節點的另一側子節點都被淘汰，不再考慮的範圍中.
當搜索回到root節點時，搜索完成，得到最近鄰節點。
複雜度
不管用甚麼方法最差情況還是會搜索到\(\ord{n^{1-1/kd}}\)個點所以最差複雜度是\(\ord{n^{1-1/kd}}\)
注意
如果需要使用 K近鄰算法
千萬別用懶惰刪除
K近鄰算法的複雜度會變\(\ord n\)
區間查找
複雜度
最差情況還是會搜索到\(\ord{n^{1-1/kd}}\)個區間故最差複雜度是\(\ord{n^{1-1/kd}+P}\)，\(P\)是查找的點的個數
k-d tree代替高維線段樹
單點修改區間查詢以二維區間最大值為例
k-d tree代替高維線段樹
區間修改(加值)單點、區間查詢
以二維區間最大值為例
複雜度
單點修改、單點查詢 的複雜度為\(\ord{log \; n}\)
區間修改、區間查詢 的複雜度為\(\ord{n^{1-1/kd}}\)
但是實際上區間操作的時間不會太慢
區間修改、區間查詢 的複雜度為\(\ord{n^{1-1/kd}}\)
但是實際上區間操作的時間不會太慢
例題
UVa 1683
題目
UVa 1683 - In case of failure
對平面上，每一個點找到最鄰近點的距離，輸出歐幾里得距離的平方即可。
UVa 11297
題目
UVa 11297 - Census
給一個二維平面，單點修改區間求min、max
UVa 11992
題目
UVa 11992 - Fast Matrix Operations
給一個二維平面，區間修改區間求sum、min、max
[IOI 2013]game
題目
[IOI 2013]game
給一個\(10^9*10^9\)的二維平面，單點修改求區間gcd
接下來一些大陸神題
BZOJ - 4154 Generating Synergy
題目
BZOJ - 4154 Generating Synergy
给定一棵以1为根的有根树,初始所有节点颜色为1,每次将距离节点a不超过l的a的子节点染成c,或询问点a的颜色
題解
把深度、dfs序當成兩個維度，設deep[a]表示a的深度，in[a]表示進入a時a的dfs序，out[a]表示離開a時的dfs序
把所有的點變成(deep[a],in[a])的形式 則對[(deep[a],out[a]),(deep[a]+l,in[a])]這個矩形染色即可
把所有的點變成(deep[a],in[a])的形式 則對[(deep[a],out[a]),(deep[a]+l,in[a])]這個矩形染色即可
BZOJ - 3489 A simple rmq problem
題目
BZOJ - 3489 A simple rmq problem
给出一个长度为n的序列，给出M个询问：在[l,r]之间找到一个在这个区间里只出现过一次的数，并且要求找的这个数尽可能大。如果找不到这样的数，则直接输出0。我会采取一些措施强制在线。
題解
三維k-d tree區間查詢
每個數a都把它當成三維點座標
(a的位置,a前一次出現的位置,a下一次出現的位置)
這樣做法就很明顯了
每個數a都把它當成三維點座標
(a的位置,a前一次出現的位置,a下一次出現的位置)
這樣做法就很明顯了