樹上差分

• 算法詳解
• • 作用
  • 做法
• 例題
• 推一篇部落格(寫得真的很好)

算法詳解

作用

區間修改u到v最短路徑上的點權或邊權

做法

前置知識:LCA(很重要)

顧名思義,就是樹上的差分,說了和沒說一樣

先把重要的擺在前面:

樹上差分是自底向上的!!!自底向上的!!!自底向上的!!!

為什麼呢?

先回憶一下差分:對于區間[l,r],每個數加上d,那麼我們定義查分數組為dat,則dat[l]+=d,dat[r+1]-=d

一棵樹,一個點有很多個子結點,但是隻有一個父節點,如果我們自頂向下做差分以及字首和,如果點u被修改了,以u為根的整顆子樹都會被影響,要抵消影響,就要通路u的每一個子結點,就意味着還是不能做到O(1)修改,還不如暴力(還不能了解的自己想想或者寫一寫就知道了,其實我表達也不是很到位).但是,如果我們采用自底向上,被影響的隻有u的祖先結點,很明顯,是一條鍊的結構,我們隻需通路u的某個祖先結點v就可以實作區間修改u到v最短路徑上的資料.

如果u和v不存在祖先關系呢?LCA就要派上用場了,修改u到v的最短路徑上dat值就是分别修改u到lca(u,v)和v到lca(u,v)的dat值(lca(u,v)必定在u到v的最短路徑上)

最後通過dfs周遊每一個點求出改點被修改後實際權值即可

例題

進去後直接跳到第二題"小王子",不要看完整的題目(題面很長且不好了解要求什麼)!!!

傳送門

推一篇部落格(寫得真的很好)

傳送門