我承认我是标题党。不过还是请诸位大佬评价一下。是一个很平凡的 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