对于一般的重链剖分,我们支持路径修改和路径查询的时间复杂度是 O(log2n) 的,原因是我们需要跳 O(logn) 个重链,另外 O(logn) 需要在一种高级数据结构中查询(这里假如是线段树)。
然而我们考虑到,在重链剖分中,只有常数次询问 / 修改的是重链中的一段,其他都是询问 / 修改整个重链的信息,而按照线段树的思想,则个情况是可以直接返回答案 / 打上标记的。
所以我们可以建若干个动态开点线段树,保存一下每个点对应的重链编号,在编号处保存一下根节点的编号,就可以 O(logn) 单次链查询 / 修改?
然而这样子似乎不好支持子树修改查询。我们发现我们依赖的只是快速找到对应点这一个性质,所以不一定需要多个线段树。我们可以在每个根上方,完善出一个完整的线段树结构(完全二叉树)出来,这样子这棵伪线段树有着几乎与线段树一样的性质和时间复杂度,因此自然可以支持区间查询 / 修改。时间复杂度 O(logn)。
请问这个优化策略是正确的吗?