知識總結 線段樹合併及其複雜度證明

2022-09-22 09:22:56 字數 629 閱讀 7607

應該算是比較基礎的知識了吧 …… 隨便寫寫,主要內容是證明。

例題(現編的):有一棵 \(m\) 個點的有根樹,每個點上有若干個數,\(m\) 個點上共有 \(n\) 個數,數的規模是 \(n\) 。每次詢問給定 \(u,l,r\) ,求 \(u\) 的子樹中有多少個數在 \([l,r]\) 中。

做法是每個點開一棵線段樹,插入這個結點上的數。如果能把一個結點的線段樹的資訊在合理的時間內全部插入(或者說「合併」)到它父親的線段樹中,就可以由下往上做一遍樹上遞推,這樣每個結點的線段樹都儲存的是整棵子樹的資訊了。

先放**吧:

int merge(const int x, const int y)

這個**還是相當好理解的,無需贅述。下面來證明一下複雜度。(我想了一中午終於想出一個超簡潔的證明 —— 本來以為會很複雜的)

從**中可以看出合併兩棵樹的複雜度約等於這兩棵樹重合的結點數。也就是說,每次合併的複雜度不會超過較小的那棵的點數。既然如此,總複雜度就不會超過總點數,也就是 \(o(n\log n)\) 。而訪問到一個結點才會新開一個結點,所以空間複雜度也是 \(o(n\log n)\) 。實際操作中可能空間有兩倍的常數。

哇怎麼這麼短就寫完了 ……