一個不套路的東西，沒啥好說的。

感覺不能叫學習筆記吧，只能叫「學會了祭」（

UPD 2020.8.27：算了還是寫點字吧（

標記永久化是跟懶標記相對的一種樹形數據結構區間修改維護方式。

不難發現，用懶標記維護的話，任意時刻訪問任意節點，它維護的信息一定是最新版（即算上了目前所有有關它的貢獻）。這樣懶癌患者會很舒服，直接調用節點信息就是真實值了，不用有其他顧慮。

標記永久化同樣是每個節點維護一個信息和標記。不同的是，這里的信息是在初始值的基礎上，只算上落在子樹內節點（即后代）的貢獻，而標記是專門記錄落在此節點上的貢獻和的。

區間修改的時候：對于每個經過的節點，顯然它一定是將來要將待修改區間分成的節點（即被待修改區間完全包含）的祖先，也就是分成的節點在它子樹內，于是直接更新它的信息（上傳或直接修改，具體看復雜度和可實現性）；對于每個要將待修改區間分成的節點，它也是經過的節點所以信息也按上面改，而且它的標記也要把本次的貢獻算上。

顯然，對一個節點有貢獻的節點只可能是它的祖先或后代。后代的貢獻已經算在它自身維護的信息中了，若想獲得此節點的真實信息，要需要算上它的祖先貢獻和。而當前節點祖先和恰好是可以一路一邊走下來一邊計算的。仔細想想這個就是樹上差分的思想。

不難發現，標記永久化對樹的形態的穩定性有較強的依賴性。線段樹和 Trie 顯然都是可以標記永久化的；而大部分平衡樹的形態都極其不穩定，一些祖先改啊改，標記永久化就失效了，這時候只能用懶標記及時地把祖先的貢獻算到當前節點維護的信息里。

一些應用：

• 主席樹。由于一個節點可能有多個（屬于不同歷史版本的）爸爸，懶標記的話就會把這些爸爸的貢獻都算上，也就是實現了時代的融合，肯定是不行的。標記永久化恰好可以解決這個問題，對于每個歷史版本，從根一路走下來累計的祖先貢獻和都是不一樣的，恰好對應每個歷史版本。具體學了再說（我不會主席樹，我好菜啊，我是 114514 流選手）。
• 樹套樹。首先，每個節點內的信息都是一個樹，如果有上傳操作的話，恭喜你獲得了 \(\mathrm O\!\left(n^2\log^2\right)\) 的優秀數據結構。考慮一路改下來避免上傳。再來看區間修改的問題：如果懶標記，每個懶標記顯然也是樹，下傳也是可以獲得優秀復雜度的。考慮標記永久化，標記依然是樹，不過不用進行下傳操作了。上下傳操作都沒有了，查詢的時候算貢獻并不需要整棵樹都保留，只需要截取查詢區間的貢獻，也就保證了復雜度了。
• 其他不能用懶標記而能用標記永久化的情況。