查看: 1347|回復: 1

[TOJ] [樹壓平][BIT]A 與大榕樹的邂逅

[複製鏈接]
  • TA的每日心情
    慵懶
    2015-4-10 14:18
  • 簽到天數: 78 天

    [LV.6]常住居民II

    176

    主題

    612

    帖子

    3959

    積分

    管理員

    Rank: 9Rank: 9Rank: 9

    積分
    3959

    台南一中資訊社新手達陣程式設計達人 - 2014

    發表於 2014-10-8 17:40:37 | 顯示全部樓層 |閱讀模式

    趕快加入我們來參與討論吧!

    您需要 登錄 才可以下載或查看,沒有帳號?加入我們

    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點時所花費的代價。 159.png

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

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


    遊客,本帖隱藏的內容需要積分高於 300 才可瀏覽,您當前積分為 0

    點評

    jd3
    太神奇啦! (0 AC的題解等到了感動~)  發表於 2014-10-8 22:35
    回復

    使用道具 檢舉

    您需要登錄後才可以回帖 登入 | 加入我們

    本版積分規則

    快速回覆 返回頂部 返回列表