P6329 【模板】点分树 | 震波

这是一道模板题，需要支持两个操作，操作一就是单点修改点权，操作二就是查询距离x不超过k的点权值和。

我们考虑建出点分树，然后对于每个点维护两个数据结构，一个处理当前分治范围到当前点的贡献，一个处理当前分治范围到点分树上父亲节点的贡献，然后我们就可以通过容斥来得到当前范围内的贡献了。

另外我们还需要预处理lca，需要st表处理一下。

代码细节：

对于预处理lca的部分，代码实现比较巧妙，尤其是定义getmn函数节省了很多的代码

另外树状数组需要动态开，所以我们就用vector处理，然后resize为子树大小，另外需要处理一种特殊情况，就是我查询的范围已经超过了我定义的大小

一定要小心有些预处理函数没有加入到主函数中，这些预处理函数应该是有固定的位置的。

还有一个非常非常重要的点，就是BIT处理的时候一定要引用，否则就不是O(1)的传址，而是O(n)的传值了。

总结

以上是生活随笔为你收集整理的P6329 【模板】点分树 | 震波的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。