竹園論壇

標題: [樹壓平][BIT]A 與大榕樹的邂逅 [打印本頁]

作者: Sylveon 時間: 2014-10-8 17:40
標題: [樹壓平][BIT]A 與大榕樹的邂逅
原題：http://toj.tfcis.org/oj/pro/159/

用DFS把樹壓到一維陣列上，並記錄進出DFS的編號[tex]In,Out[/tex]，其中可以發現對於某點P與其子孫節點C有下關係：[tex]InP%3CInC%3COutC%3COutP[/tex]我們稱這種走訪方法為尤拉走訪(Euler tour technique)。

這樣做有什麼好處呢？我們開一個數列A，若對於點P的點權重為W，我們令[tex]A%5BInP%5D%3DW%5C%20%2CA%5BOutP%5D%3D-W[/tex]，透過尤拉走訪，我們可以發現前綴和過了[tex]A%5BOutP%5D[/tex]後，P點及其子孫的權重就會被完全抵消，就是我們把原本直接走到終點，改成以尤拉走訪的方式行走，於是我們就可以利用前綴和[tex]A%5BInP%5D[/tex]來表示到P點時所花費的代價。

由於題目又有要求單點修改，我們可以使用對前綴和計算與修改有著十分優良效率的Binary Indexed Tree (BIT)來運算，這裡就不再對BIT多做解釋了。

時間複雜度：
DFS：[tex]O(N)[/tex]
BIT單次查詢與修改：[tex]O(log2N)=O(logN)[/tex]
總複雜度：[tex]O(MlogN)[/tex]

歡迎光臨竹園論壇 (http://forum.tfcis.org/)