还是复习笔记，因为我发现我都不会
数组 \(a=[1,9,1,9,4,5,1,4].\)
前缀和
前缀和数组 \(s = [1,10,11,20,24,29,30,34]\).
如何计算？ \(s_i = s_{i - 1} + a_i\)。
有什么用？ 计算区间和，区间 \([l,r]\) 的和就是 \(s_r - s_{l - 1}\)。
差分
差分数组 \(s' = [1,8,-8,8,-5,1,-4,3]\).
差分前缀和数组 \(s'' = [1,9,1,9,4,5,1,4]\).
发现差分数组做个前缀和就变成原数组了。
如何计算？ \(s'_i = a_i - a_{i - 1}\)。
有什么用？ 在区间查询的基础上，可以进行区间修改。对区间 \([l,r]\) 进行区间加，\(s'_l+\Delta,s'_{r + 1} - \Delta\)。常常配合树状数组使用。
树上前缀和
- 信息在点上：\(s_x + s_y - s_{lca} - s_{fa_{lca}}\)
- 信息在边上：\(s_x + s_y - 2s_{lca}\)
树上差分
点差分
信息放在点上。对一段路径进行修改操作。
\[s'_x + \Delta,s'_y+\Delta,s'_{lca} - \Delta,s'_{fa_{lca}} - \Delta
\]
边差分
信息放在边上。对一段路径进行修改操作。
\[s'_x + \Delta,s'_y+\Delta,s'_{lca} - 2\Delta
\]