算法小站
首页
wiki
新鲜事
文章搜索
网站导航
回忆录
首页
wiki
新鲜事
文章搜索
网站导航
回忆录
登录
注册
算法基础
搜索
数据结构
字符串
数学
图论
动态规划
计算几何
杂项
wiki 主题
算法基础
二维偏序
高维前缀和
树上差分
搜索
数据结构
线段树
线段树单点修改
线段树区间修改
动态开点线段树
线段树的合并(一)
可持久化线段树
树链剖分
平衡树
FHQ-Treap
珂朵莉树
分块
位分块
字符串
数学
图论
图的连通性
有向图的强连通分量
无向图的割点割边和双连通分量
流和匹配
最大流
最大流的一些应用
图论杂项
最大团搜索算法
树上问题
kruskal重构树
kruskal重构树的一些问题
动态规划
计算几何
杂项
启发式合并
高精度
一些经典问题
约瑟夫环
曼哈顿距离
排列与置换
主题名称
是否为父主题
是否为其添加wiki文章
取 消
确 定
选择主题
修改主题名称
修改父主题
修改wiki文章
取 消
删 除
修 改
算法基础
搜索
数据结构
字符串
数学
图论
动态规划
计算几何
杂项
算法基础
二维偏序
高维前缀和
树上差分
[[ item.c ]]
0
0
树上差分
## 树上差分  树上差分常见的分为点差分和边差分 **点差分** 现在需要对路径$$(x, y)$$上所有点的权值都`+1`,那么我们不直接维护点权,而是让节点的权值等于**差分数组`d[...]`的值**,对应地 ```math \displaystyle d_x +1, d_y + 1, d_{lca} - 1, d_{fa(lca)} - 1 ``` 那修改完之后,求一个节点`u`**真正的权值**,只需要`dfs`**计算$$u$$及其子树的权值和**即可 **边差分** **把边权下移给节点,变成点权操作**,我们要消除`lca`以上的边的影响 ```math \displaystyle d_x + 1, d_y + 1, d_{lca} - 2 ``` 同样计算$$u$$及其**子树的权值和**,就是$$u$$实际的点权,也就是`(fa(u), u)`的实际边权
看完文章有啥想法
发布评论
目录
[[ item.c ]]
51 人参与,0 条评论