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