树上前缀和原理与应用
1、树上前缀和是什么及其作用
树上前缀和是普通前缀和在树形结构上的扩展,主要用于高效处理树上路径的查询问题。
主要作用:
- 快速计算树上任意两点路径上的节点权值和
- 支持快速查询子树和
- 结合树上差分处理路径修改问题
- 降低路径查询的时间复杂度(从 O(n) 降到 O(1) 或 O(log n),配合 LCA)
2、树上前缀和原理
基本思想:
对于一棵树,我们可以定义两种前缀和:
- 节点到根的前缀和:
sum[u]表示从根节点到 u 路径上所有节点的权值之和 - 子树前缀和:
sum_sub[u]表示以 u 为根的子树中所有节点的权值之和
路径和计算公式:
对于任意两点 u 和 v,设它们的最近公共祖先为 lca,则 u 到 v 路径上的节点权值和可以通过以下公式计算:
PathSum(u, v) = sum[u] + sum[v] - 2 * sum[lca] + val[lca]
其中 val[lca] 为最近公共祖先节点的权值,避免被重复减去。该公式利用容斥原理,将路径拆分为两条从根出发的路径并去除重叠部分。


