复杂度更优的单点加区间和算法!

· · 休闲·娱乐

考虑一条数轴。让序列的 [1,n] 分别对应上数轴的每个点。

考虑初始时,如果 a_i = x,那么在数轴上 i 的位置添加一个权值为 x 的点。

对于单点加,如果要给 a_i 加上 x,那么在数轴上 i 的位置添加一个权值为 x 的点。

如果要查询区间 [l,r] 的和,那么本质是查询 [l,r] 这个一维矩阵里面所有点的权值之和。

在一个一维空间里面加入点,或查询一维矩形内点的权值和,可以使用 kd-Tree,其中 k=1。也就是 1d-Tree。

因为 kd-Tree 不支持二进制分组,所以理论上要拍一个二进制分组上去,这样就比一般的线段树还要劣了!

考虑把这个二进制分组优化掉。

注意到能够插入新点的位置最多只有 n 个。能不能最开始在这 n 个位置插入权值为 a_i 的新点,然后在额外加点的时候改点权呢?

是可以的,考虑在每个 kd-Tree 节点上维护它对应的矩形范围的点权之和,那么在加点的时候,找到它对应的那个节点,直接给它到根节点的链上全部加上要加的点权就可以了。

树高最多 O(\log n),所以单点加复杂度是 O(\log n) 的。而矩形查询,根据 kd-Tree 的复杂度分析,是 O(n^{1-k}) 的,由于 k=1,所以就是 O(1),因此这个思路优于已知的所有解决该问题的算法!

看来下一届诺贝尔信息学奖一定会颁给你了!