趕快加入我們來參與討論吧!
您需要 登錄 才可以下載或查看,沒有帳號?加入我們
x
原題: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]
遊客,本帖隱藏的內容需要積分高於 300 才可瀏覽,您當前積分為 0
|