UOJ Logo xiezheyuan的博客

博客

非递归权值线段树?线段树和树状数组的最终较量?

2023-11-06 16:57:13 By xiezheyuan

我承认我是标题党。不过还是请诸位大佬评价一下。是一个很平凡的 trick。

捂脸熊

前言

非递归线段树,也就是 zkw 线段树。优点是节省了递归的时间,缺点是容易写错,而且在某些时候实际上优化并不明显?

非递归权值线段树是 zkw 线段树在权值线段树的特化,相比于普通线段树有着更段的代码和更小的常数,相比于树状数组可以维护更加丰富的信息(如 Mex)。

值域补齐

类似 zkw,我们需要将值域补齐成 $2$ 的整数次幂来提升寻找节点的效率。

修改

先定位到叶子结点进行修改,然后向上更新所有祖先的信息。

大概类似于这样:

void Merge(int &element, int value);
void update(int p,int v){
    for(p=p+n-1;p;p>>=1) Merge(tree[p],v);
}

求前缀和

与 zkw 类似的,我们如果要求 $[1:i]$ 的和,令 $i=i+1$。然后从 $i$ 的叶子结点开始往上跳父亲。如果这是一个直系父亲的右节点那么左节点一定在前缀和里,加上。容易发现这样不重不漏。 不够优秀。 我们考虑直系父亲右节点是奇数,因此可以剪枝。将跳父亲改为跳到奇数位(直观点,就是跳到父亲后去掉二进制意义下的后导 $0$),可以使用 __builtin_ctz 内置函数来实现(这个函数内部实现尚不明确,似乎是 $O(\log \log n)$ 的,但在我们的实现中可以看成常数)。但是由于一些奇异原因,这个优化仅优化了 $2$ ms。

int rnk(int p){
    int v=1;p=p+n-1;
    for(p>>=__builtin_ctz(p);p;p>>=1,p>>=__builtin_ctz(p)) Merge(v, tree[p-1]);
    return v;
}

线段树上二分

模拟即可。你可以用一个循环来实现。

下面是 kth 的代码:

int kth(int k){
    int i=1;
    for(;i<n;tree[i<<1]>=k?i<<=1:(i=(i<<1|1),k-=tree[i-1]));
    return i-n+1;
}

总评

优势在于:

  • 短!真的很短!

  • 常数小!真的很小!(和树状数组差别不大)

  • 在你写这个东西的时候,你可以嘲讽一下我这个菜鸡。

然后你可以把这些题给写了,感受说的话诚非虚言:

  • P4137 Rmq Problem / mex(离线处理)

  • P3369 【模板】普通平衡树

  • CF69E Subsegments

xiezheyuan Avatar