天天爱跑步：桶（就是数组）/权值线段树（没打）
2020-12-13 06:22
标签：closed sed class 线段 线段树 gif 空间复杂度 图片 负数 提取：等式转换，桶，倍增lca 对于（x，y）的一次提问，我们规定lca为（x，y）的lca d为深度，w为点出现观察员的时间 那么对于（x，lca）这段路径上的点i，此次提问能作出贡献的等式是 d[x]-d[i]=w[i] ->d[x]=w[i]+d[i] 对于（lca，y）这段路径上的点i，此次提问能作出贡献的等式是 d[x]-d[lca]+d[i]-d[lca]=w[i] ->d[x]-2*d[lca]=w[i]-d[i] 那么我们可以将提答转化为区间修改了！ 在（x，lca）上将“d[x]"这种物品的个数+1 在（lca，y）上将"d[x]-2*d[lca]"这种物品的个数+1 但是好像lca处加重了？ 请听下文。 能否继续优化？ 当然可以！考虑将区间修改转化为单点修改... 树上差分！ 具体的，（对于（x，lca）过程，（lca，y）同理） 将x处"d[x]"物品的个数+1 将lca处”d[x]"物品的个数-1 对吗？ 我们考虑lca处，如果这样处理，就会使得lca处反而没修改！（请注意与上文差异） 所以基于lca有且只有一次添加，我们将第一次修改的范围变为（x，fa[lca]）， 而第二次修改范围（lca，y）不变，这就达到我们的目的了！ 而树上差分可以用权值线段树（常用，但空间复杂度较大），桶（数组？）来解决。 本题我的选择是数组。 第二次修改时d[x]-2*d[lca]可能会成负数记得平移Orz Code 天天爱跑步：桶（就是数组）/权值线段树（没打） 标签：closed sed class 线段 线段树 gif 空间复杂度 图片 负数 原文地址：https://www.cnblogs.com/hzoi2018-xuefeng/p/11175725.html
下一篇：js 数组去重
文章标题：天天爱跑步：桶（就是数组）/权值线段树（没打）
文章链接：http://soscw.com/index.php/essay/32893.html