树上差分

树结构上的差分算法及应用
差分概念的理解
差分是一种用于高效处理区间更新和查询的技术。对于一维数组而言，通过构建差分数组可以快速完成区间的增量操作并求得前缀和来恢复原始数值变化情况[^3]。
当这一理念被推广到树形结构之上时，则形成了所谓的“树上差分”。其核心思想是在不改变原有逻辑关系的前提下，利用额外的数据记录路径之间的差异信息以便于后续计算。
实现方法
为了在树中执行有效的差分运算，通常采用如下策略：

边权差分：针对每条连接两个节点u,v的无向边赋予初始权重w(u,v)，之后如果要对某棵子树内的所有结点施加相同的增加值k，只需调整进入该子树根部唯一入口处那条边的权重即可。
增量表达式为Δw(parent,child)=k，其中parent指向即将受到影响区域之外最近的一个祖先位置而child即为对应子树内部任选代表性的成员之一。

点权差分：此方式侧重于标记特定顶点而非它们之间连线部分的变化趋势。具体做法是对选定范围两端端点分别打±k标签（起点+终点−），再经由深度优先搜索(DFS)遍历整棵树累加经过各定点所携带标志值得总合从而得出最终结果。

from collections import defaultdict

def dfs(node, parent, diff_values, tree_structure):
result = diff_values[node]

for neighbor in tree_structure[node]:
if neighbor != parent:
result += dfs(neighbor, node, diff_values, tree_structure)

return result

# 构建图结构 (假设输入已经给出)
tree_structure = defaultdict(list)
edges_with_weights = [(0, 1), (1, 2), ... ] # 这里省略实际边列表...
for u, v in edges_with_weights:
tree_structure[u].append(v)
tree_structure[v].append(u)

# 对某些节点或边上做差分标记
diff_values = [0]*len(tree_structure)

# 更新指定节点/边的差分值...

# 计算每个节点的实际影响值
actual_impact_per_node = []
for i in range(len(diff_values)):
actual_impact_per_node.append(dfs(i,-1,diff_values.copy(),tree_structure))
登录后复制
上述代码片段展示了如何基于给定的一组边建立邻接表表示法下的未加权无向连通图，并实现了简单的深搜过程用以传播从源至汇沿途累积起来的影响因子。
应用场景
树状差分技术广泛应用于解决涉及频繁修改局部属性同时又需即时反馈整体状态的问题当中，比如社交网络中的好友推荐系统、文件系统的权限管理机制以及地理信息系统(GIS)里的最短路径规划等领域都可见其身影。