【学习笔记】浅析平衡树套线段树 & 带插入区间K小值

时间：2023-03-08 18:02:30
【学习笔记】浅析平衡树套线段树 & 带插入区间K小值

常见的树套树

一般来说，在嵌套数据结构中，线段树多被作为外层结构使用。

但线段树毕竟是 静态 的结构，导致了一些不便。

下面是一个难以维护的例子：

带插入区间 \(k\) 小值问题

来源：Luogu P4278 & BZOJ 3065

给定一个初始长为 \(n\) 的正整数序列，执行 \(m\) 次操作：

  • Q x y k：查询区间 \([x, y]\) 中第 \(k\) 小的数的大小；
  • M x val：将位置 \(x\) 的数字修改为 \(val\)；
  • I x val：在位置 \(x\) 前插入数字 \(val\)。

插入次数、原序列长度 \(\le 3.5\times 10^4\)，查询次数、数值大小 \(\le 7\times 10^4\)。强制在线。

不常见的树套树

由于数列出现的结构上的变动，线段树作为静态数据结构已经难以维护。

于是我们考虑用动态结构的 平衡树 作为外层结构，即 平衡树套线段树。

但是毕竟为外层结构，我们选择的平衡树也不能太跳，这里暂且使用 替罪羊树。WBLT 之类的应该也行，不过这里暂且介绍一种 不会。

替罪羊树不同于 Splay，Treap——它不用旋转。为了维持平衡，我们会在不平衡的结点 排扁重构。是否足够不平衡是根据子树大小判断的。替罪羊树相对于旋转平衡树结构更稳定，更适合作为外层结构。

在这里，替罪羊树上的每一个结点都包含着一颗 动态开点权值线段树，表示以当前结点为根的子树中的数值构成的集合。

维护手法

建树

建树的整体框架与普通平衡树并无大异，只不过加上线段树部分即可。

大致来说就是当前线段树需要包含左右儿子以及自己的信息。

相对于一个个插入，使用 线段树合并 方法显然优秀一些。

我们知道线段树合并的总复杂度是一只 \(\log\) 的，所以总复杂度不会超过 \(O(n\log^2 n)\)。

操作

插入操作，我们只要进行常规的平衡树插入即可。平衡树上二分找到第 \(x\) 个位置前加入结点，同时在寻找的路径上的每一个平衡树结点上进行线段树的插入。这样的复杂度是 \(O(\log^2 n)\)，因为平衡树深度为 \(O(\log n)\)，所以一共更新了 \(O(\log n) \times O(\log n)\) 个线段树结点。在插入前需要判断重构。

单点修改也是同理，找到这个结点然后把这条路径进行线段树单点修改即可。复杂度仍然 \(O(\log^2 n)\)。

对于查询，我们回忆一下 Dynamic Rankings 的线段树（树状数组）套线段树做法，类似的我们也把这些平衡树子树“拎”出来，把零散的结点“抠”出来，然后一起二分即可。复杂度 \(O(\log^2 n)\)。

复杂度

时空复杂度均为 \(O(n\log^2 n)\)。

但是常数其实很大。用这个做法过掉上题的 Luogu 数据是非常困难的。

降低空间常数

如果一颗线段树的子树不代表任何元素，即 \(siz = 1\)。那么对于当前来说这个子树不要也罢，于是可以添加一个 垃圾回收机制。

代码实现

由于线段树不是实现重点，这里只展出替罪羊树的部分。

segt 前缀的是线段树；spat 前缀的是替罪羊树。

建树

int spatBuild(int l, int r) {

	if (l > r) return 0;

    int mid = (l + r) >> 1;

    int x = createSpatNode(0, 0, a[mid], r - l + 1);

	spat[x].lc = spatBuild(l, mid - 1);

	spat[x].rc = spatBuild(mid + 1, r);

    spat[x].seg_rt = segtMerge(

		spat[spat[x].lc].seg_rt,

		spat[spat[x].rc].seg_rt,

		0, U);

    segtInsert(spat[x].seg_rt, 0, U, a[mid], 1);

    return x;

}

查询

int qry[N], qcnt;

int val[N], vcnt;

void spatScanOut(int x, int ql, int qr, int l, int r) {

    if (ql > qr || l > r) return;

    if (ql <= l && r <= qr) return qry[++qcnt] = x, void();

    if (l > qr || r < ql) return;

    int mid = spat[spat[x].lc].siz + l;

    if (ql <= mid && mid <= qr) val[++vcnt] = spat[x].val;

    spatScanOut(spat[x].lc, ql, qr, l, mid - 1);

    spatScanOut(spat[x].rc, ql, qr, mid + 1, r);

}

int Query(int ql, int qr, int k) {

    qcnt = vcnt = 0;

    spatScanOut(spatRoot, ql, qr, 1, spat[spatRoot].siz);

    int l = 0, r = U;

    for (int i = 1; i <= qcnt; i++)

        qry[i] = spat[qry[i]].seg_rt;

    while (l < r) {

        int mid = (l + r) >> 1;

        int sum = 0;

        for (int i = 1; i <= qcnt; i++)

            sum += segt[segt[qry[i]].lc].siz;

        for (int i = 1; i <= vcnt; i++)

            sum += (val[i] <= mid);

        if (k <= sum) {

            r = mid;

            for (int i = 1; i <= qcnt; i++)

                qry[i] = segt[qry[i]].lc;

        } else {

            l = mid + 1, k -= sum;

            for (int i = 1; i <= qcnt; i++)

                qry[i] = segt[qry[i]].rc;

            for (int i = 1; i <= vcnt; i++)

                if (val[i] <= mid) val[i] = U + 5;

        }

    }

    return l;

}

单点修改

int spatAt(int x, int k) {

    while (x) {

        if (spat[spat[x].lc].siz + 1 == k) return spat[x].val;

        if (k <= spat[spat[x].lc].siz) x = spat[x].lc;

        else k -= spat[spat[x].lc].siz + 1, x = spat[x].rc;

    }

    throw;

}

void spatEdit(int x, int k, int lst, int cur) {

    segtInsert(spat[x].seg_rt, 0, U, lst, -1);

    segtInsert(spat[x].seg_rt, 0, U, cur, 1);

    if (spat[spat[x].lc].siz + 1 == k)

        return spat[x].val = cur, void();

    if (k <= spat[spat[x].lc].siz) spatEdit(spat[x].lc, k, lst, cur);

    else spatEdit(spat[x].rc, k - spat[spat[x].lc].siz - 1, lst, cur);

}

void Replace(int pos, int val) {

    int lst = spatAt(spatRoot, pos);

    if (lst != val) spatEdit(spatRoot, pos, lst, val);

}

插入

void spatFlatten(int& x) {

	if (!x) return;

    spatFlatten(spat[x].lc);

    a[++n] = spat[x].val;

    spatFlatten(spat[x].rc);

    destroySegtTree(spat[x].seg_rt);

    p_rec[++p_top] = x, x = 0;

}

void spatRebuild(int& x) {

    n = 0, spatFlatten(x);

    x = spatBuild(1, n);

}

void spatInsert(int& x, int k, int val) {

    if (!x) {

        x = createSpatNode(0, 0, val, 1);

        segtInsert(spat[x].seg_rt, 0, U, val, 1);

        return;

    }

    ++spat[x].siz, segtInsert(spat[x].seg_rt, 0, U, val, 1);

    if (k <= spat[spat[x].lc].siz) spatInsert(spat[x].lc, k, val);

    else spatInsert(spat[x].rc, k - spat[spat[x].lc].siz - 1, val);

    if (checkBad(x)) spatRebuild(x);

}

void Insert(int pos, int val) {

    spatInsert(spatRoot, pos - 1, val);

}

完整实现

Record：https://darkbzoj.tk/submission/83902

14695ms|117088kb|6.5kb

后记