震波

单点修改，树上查询邻域点权和。

如果不带修的话是经典题目树上邻域数点的弱化版，因为查询时合并簇的次数限制从一次放宽到了 $O(\log n)$ 次。

具体做法是建出全局平衡二叉树，对于每个簇的某个界点 $u$，设 $d$ 为簇内到 $u$ 距离最远的点的距离，对于每个 $k\in[1,d]$ 维护簇内于 $u$ 相距为 $k$ 的点的点权和。全局平衡二叉树处理簇内点相关信息时一般不包含界点，否则不方便统计答案，这里同理。

于是树上单点修改 $u$ 的点权时，从包含 $u$ 的最小簇（$u$ 不能是该簇界点）开始向父亲跳。对途径的每个簇维护的距离两个界点相应距离的点的权值和进行单点修改。

查询以 $u$ 为中心的邻域时，将邻域分解为几个整簇和几个簇内邻域进行合并。具体做法是从以 $u$ 为界点的任一簇开始往父亲跳，对途径的每个点，考察邻域是否覆盖到了它的兄弟，它兄弟的界点是否在父亲的簇内。一通合并后记得考察根簇的界点是否在邻域内。

簇内查询邻域需要对所维护的到两个节点距离为定值的点的权值和求前缀和，还需要单点修改，所以使用树状数组查询。