差分陣列 (Difference Array)

2021-03-15 15:55:02 +0800 CST Tags:

https://blogarithms.github.io/articles/2018-11/difference-arrays

可以想成 +1 代表繩子開始的位置，-1 代表繩子結束的位置，所以最後加總的意義就是到底有幾條繩子 lie 在我這個位置上。

之所以要這樣具象化是因為 Codeforces 740D 會在 tree 上做 difference array，如果不這樣想的話兩個 branch 交會的時候會有點卡， 假設兩個 children 分別有 5 條繩子和 7 條繩子，那麼交會的時候自然會先做加總，再來看自己這個節點有沒有多鋪一條繩子或 drop 掉一條繩子，再做調整，所以加總是 OK 的。