首页 > 其他分享 >树套树——维护区间内权值信息的“重武器”

树套树——维护区间内权值信息的“重武器”

时间：2023-04-18 18:23:10浏览次数：57  
标签：树套 重武器 res mid pos int 区间 内权值 id

Introduction

树套树，顾名思义，就是将各类“树”据结构的节点换成“树”，以此解决一些问题。

一般情况下，两层树分别维护区间信息和区间内权值的信息。

而因为树套树极劣的空间复杂度和巨大的常数，经常需要使用 动态开点 和 垃圾回收 的方法降低空间复杂度，以及一定的卡常技巧（将较为短小的不含循环的非递归函数套上 inline 等）。

Examples

外层位置，内层权值

最经典的树套树了，外层是描述区间信息的区间线段树（或树状数组），内层是维护区间内权值的平衡树（或权值线段树）。

模板题

下面就着上面给出的模板题来讲这类树套树。

  • 对于操作 1（查询 \(k\) 在区间中的排名），\(k\) 在区间内的排名等价于区间内小于 \(k\) 的数的个数 \(+ 1\)，在线段树上查询区间的时间复杂度是 \(O(\log n)\)，再乘上在每个区间的平衡树上查找小于 \(k\) 的树的个数所需的时间复杂度 \(O(\log n)\)，单次操作的时间复杂度为 \(O(\log^2 n)\)。
  • 对于操作 2（查询区间内排名为 \(k\) 的数），我们无法直接查询区间内排名为 \(k\) 的值，但可以通过操作 1 验证当前值在区间内的排名与 \(k\) 的大小关系，那么利用 二分答案 的思想来优化后，单次操作的时间复杂度可以做到 \(O(\log^3 n)\)。
  • 对于操作 3（单点修改），注意树套树的外层线段树上是没法存 tag 的，要在每段符合条件的区间上都更新，单次操作的时间复杂度为 \(O(\log^2 n)\)。
  • 对于操作 4（查询区间内 \(k\) 的前驱），在线段树递归的过程中对每个符合条件的区间中 \(k\) 的前驱取最大值即可，单次操作的时间复杂度为 \(O(\log^2 n)\)。
  • 对于操作 5（查询区间内 \(k\) 的后继），类似地，在线段树递归的过程中对每个符合条件的区间中 \(k\) 的后继取最小值即可，单次操作的时间复杂度为 \(O(\log^2 n)\)。

Tips

  • 一般动态开点时内层树的结点数开到 \([200, 400]\) 倍，如果能够套垃圾回收可酌情减少，但一定不要开太小，并要注意防止 MLE。

  • 注意到 Fhq-Treap 中分裂和合并操作的常数巨大，因此能采用朴素实现的就尽量不去过多地分裂和合并。

  • 区间线段树套平衡树的时间复杂度可看作 \(O(n \log^3 n)\)。

代码 
#include <bits/stdc++.h>

#define MAXN 50100
#define lson pos << 1
#define rson pos << 1 | 1

using namespace std;

int n, m, w[MAXN];

template<typename _T>
void read(_T &_x) {
    _x = 0;
    _T _f = 1;
    char _ch = getchar();
    while (_ch < '0' || '9' < _ch) {
        if (_ch == '-') _f = -1;
        _ch = getchar();
    }
    while ('0' <= _ch && _ch <= '9') {
        _x = (_x << 3) + (_x << 1) + (_ch & 15);
        _ch = getchar();
    }
    _x *= _f;
}

template<typename _T>
void write(_T _x) {
    if (_x < 0) {
        putchar('-');
        _x = -_x;
    }
    if (_x > 9) write(_x / 10);
    putchar('0' + _x % 10);
}

namespace Treap {
	int tot;

	struct Treap {
		int val, rnd, sz;
		int ls, rs;
	} t[MAXN * 400];

	inline int newt(int val) {
		tot++;
		t[tot].val = val;
		t[tot].rnd = rand();
		t[tot].sz = 1;
		return tot;
	}

	inline void upd(int id) {
		t[id].sz = t[t[id].ls].sz + t[t[id].rs].sz + 1;
	}

	int merge(int x, int y) {
		if (!x || !y) return x ^ y;
		if (t[x].rnd <= t[y].rnd) {
			t[x].rs = merge(t[x].rs, y);
			upd(x);
			return x;
		}
		t[y].ls = merge(x, t[y].ls);
		upd(y);
		return y;
	}

	void split(int id, int val, int &x, int &y) {
		if (!id) {
			x = y = 0;
			return;
		}
		if (t[id].val > val) {
			y = id;
			split(t[id].ls, val, x, t[y].ls);
		} else {
			x = id;
			split(t[id].rs, val, t[x].rs, y);
		}
		upd(id);
	}

	inline void insert(int &id, int val) {
		int x, y;
		split(id, val, x, y);
		id = merge(merge(x, newt(val)), y);
	}

	inline void erase(int &id, int val) {
		int x, y, z;
		split(id, val, x, z);
		split(x, val - 1, x, y);
		y = merge(t[y].ls, t[y].rs);
		id = merge(merge(x, y), z);
	}

	int getrk(int id, int val) {
		int res = 0;
		while (id) {
			if (t[id].val < val) res += t[t[id].ls].sz + 1, id = t[id].rs;
			else id = t[id].ls;
		}
		return res;
	}

	int getval(int id, int k) {
		if (k <= t[t[id].ls].sz) return getval(t[id].ls, k);
		if (k == t[t[id].ls].sz + 1) return t[id].val;
		return getval(t[id].rs, k - t[t[id].ls].sz - 1);
	}

	inline int getpre(int &id, int val) {
		int x, y;
		split(id, val - 1, x, y);
		int res = t[x].sz ? getval(x, t[x].sz) : -2147483647;
		id = merge(x, y);
		return res;
	}

	inline int getnxt(int &id, int val) {
		int x, y;
		split(id, val, x, y);
		int res = t[y].sz ? getval(y, 1) : 2147483647;
		id = merge(x, y);
		return res;
	}
}

namespace SGT {
	int rt[MAXN << 2];

	void upd(int pos, int l, int r, int x, int pre, int now) {
		if (pre != -1) Treap::erase(rt[pos], pre);
		Treap::insert(rt[pos], now);
		if (l == r) return;
		int mid = (l + r) >> 1;
		if (x <= mid) upd(lson, l, mid, x, pre, now);
		else upd(rson, mid + 1, r, x, pre, now);
	}

	int qrk(int pos, int l, int r, int x, int y, int c) {
		if (x <= l && r <= y) return Treap::getrk(rt[pos], c);
		int mid = (l + r) >> 1, res = 0;
		if (x <= mid) res += qrk(lson, l, mid, x, y, c);
		if (y > mid) res += qrk(rson, mid + 1, r, x, y, c);
		return res;
	}

	int qval(int x, int y, int k) {
		int l = 0, r = 1e8, mid, res = -1;
		while (l <= r) {
			mid = (l + r) >> 1;
			if (qrk(1, 1, n, x, y, mid) + 1 <= k) res = mid, l = mid + 1;
			else r = mid - 1;
		}
		return res;
	}

	int qpre(int pos, int l, int r, int x, int y, int c) {
		if (x <= l && r <= y) return Treap::getpre(rt[pos], c);
		int mid = (l + r) >> 1, res = -2147483647;
		if (x <= mid) res = qpre(lson, l, mid, x, y, c);
		if (y > mid) res = max(res, qpre(rson, mid + 1, r, x, y, c));
		return res;
	}

	int qnxt(int pos, int l, int r, int x, int y, int c) {
		if (x <= l && r <= y) return Treap::getnxt(rt[pos], c);
		int mid = (l + r) >> 1, res = 2147483647;
		if (x <= mid) res = qnxt(lson, l, mid, x, y, c);
		if (y > mid) res = min(res, qnxt(rson, mid + 1, r, x, y, c));
		return res;
	}
}

using namespace SGT;

int main() {
	read(n), read(m);
	for (int i = 1; i <= n; i++) {
		read(w[i]);
		upd(1, 1, n, i, -1, w[i]);
	}
	while (m--) {
		int op, a, b, c;
		read(op), read(a), read(b);
		if (op == 1) {
			read(c);
			write(qrk(1, 1, n, a, b, c) + 1), putchar('\n');
		} else if (op == 2) {
			read(c);
			write(qval(a, b, c)), putchar('\n');
		} else if (op == 3) {
			upd(1, 1, n, a, w[a], b);
			w[a] = b;
		} else if (op == 4) {
			read(c);
			write(qpre(1, 1, n, a, b, c)), putchar('\n');
		} else {
			read(c);
			write(qnxt(1, 1, n, a, b, c)), putchar('\n');
		}
	}
	return 0;
}

适当添加 inline 后吸氧可过。 人傻常数大……

外层权值，内层位置

还是就着例题（P3332 [ZJOI2013]K大数查询）来讲。

不难发现这题不能再用区间线段树套平衡树来做了，因为单次修改操作的时间复杂度高达 \(O(n \log^2 n)\)。因此考虑外层维护权值，内层维护区间信息，也就是权值线段树套区间线段树。

  • 对于区间修改，直接在权值线段树对应范围上的区间线段树中修改即可，单次操作的时间复杂度为 \(O(\log^2 n)\)。
  • 对于查询区间第 \(k\) 大，借鉴 主席树 的思想，通过查询当前值域在位置 \([l, r]\) 中的数的个数来判断答案是否在当前值域中，单次操作的时间复杂度为 \(O(\log^2 n)\)。
    这一部分用语言描述过于晦涩难懂，下面给出带注释的代码方便理解（采用了 标记永久化 以优化常数，实现方法参考 这篇博客）。

内层树：

ll query(int pos, int l, int r, int x, int y) { // 查询位置区间 [x, y]
    if (!pos) return 0;
    if (x <= l && r <= y) return t[pos].w;
    int mid = (l + r) >> 1;
    ll res = (min(r, y) - max(l, x) + 1) * t[pos].tag;
    if (x <= mid) res += query(t[pos].ls, l, mid, x, y);
    if (y > mid) res += query(t[pos].rs, mid + 1, r, x, y);
    return res;
}

外层树：

int query(int pos, int l, int r, int x, int y, ll k) {// 查询位置区间 [x, y] 中第 k 大的值
    if (l == r) return l;
    int mid = (l + r) >> 1;
    ll tmp = SGT_IN::query(rt[rson], 1, n, x, y);
    // 在区间线段树中查询区间中在权值区间 [mid + 1, r] 的数的个数
    if (tmp >= k) return query(rson, mid + 1, r, x, y, k);
    // 如果数的个数 >= k，则第 k 大值一定在权值区间 [mid + 1, r] 中
    return query(lson, l, mid, x, y, k - tmp);
    // 否则一定在权值区间 [l, mid] 中，注意此时要查询的排名会发生变化
}
代码 
#include <bits/stdc++.h>

#define MAXN 50100
#define lson pos << 1
#define rson pos << 1 | 1

using namespace std;

typedef long long ll;

int n, m;

template<typename _T>
void read(_T &_x) {
    _x = 0;
    _T _f = 1;
    char _ch = getchar();
    while (_ch < '0' || '9' < _ch) {
        if (_ch == '-') _f = -1;
        _ch = getchar();
    }
    while ('0' <= _ch && _ch <= '9') {
        _x = (_x << 3) + (_x << 1) + (_ch & 15);
        _ch = getchar();
    }
    _x  *= _f;
}

template<typename _T>
void write(_T _x) {
    if (_x < 0) {
        putchar('-');
        _x = -_x;
    }
    if (_x >= 10) write(_x / 10);
    putchar('0' + _x % 10);
}

namespace SGT_IN {
    int tot = 0;

    struct Seg {
        ll w, tag;
        int ls, rs;
    } t[MAXN * 400];

    void upd(int &pos, int l, int r, int x, int y) {
        if (!pos) pos = ++tot;
        t[pos].w += min(r, y) - max(l, x) + 1;
        if (x <= l && r <= y) {
            t[pos].tag++;
            return;
        }
        int mid = (l + r) >> 1;
        if (x <= mid) upd(t[pos].ls, l, mid, x, y);
        if (y > mid) upd(t[pos].rs, mid + 1, r, x, y);
    }

    ll query(int pos, int l, int r, int x, int y) {
        if (!pos) return 0;
        if (x <= l && r <= y) return t[pos].w;
        int mid = (l + r) >> 1;
        ll res = (min(r, y) - max(l, x) + 1) * t[pos].tag;
        if (x <= mid) res += query(t[pos].ls, l, mid, x, y);
        if (y > mid) res += query(t[pos].rs, mid + 1, r, x, y);
        return res;
    }
}

namespace SGT_OUT {
    int rt[MAXN << 2];

    void upd(int pos, int l, int r, int x, int y, int w) {
        SGT_IN::upd(rt[pos], 1, n, x, y);
        if (l == r) return;
        int mid = (l + r) >> 1;
        if (w <= mid) upd(lson, l, mid, x, y, w);
        else upd(rson, mid + 1, r, x, y, w);
    }

    int query(int pos, int l, int r, int x, int y, ll k) {
        if (l == r) return l;
        int mid = (l + r) >> 1;
        ll tmp = SGT_IN::query(rt[rson], 1, n, x, y);
        if (tmp >= k) return query(rson, mid + 1, r, x, y, k);
        return query(lson, l, mid, x, y, k - tmp);
    }
}

using namespace SGT_OUT;

int main() {
    read(n), read(m);
    while (m--) {
        int op, l, r;
        ll c;
        read(op), read(l), read(r), read(c);
        if (op == 1) upd(1, 1, n, l, r, c);
        else write(query(1, 1, n, l, r, c)), putchar('\n');
    }
    return 0;
}

Bonus

上文中提到的外层位置，内层权值一类的树套树，还可以处理动态逆序对问题，常用树状数组套权值线段树、区间线段树套权值线段树。

Conclusion

树套树本质上就是数据结构间的互相嵌套，一般情况下就是将维护区间信息和维护权值信息的两种不同数据结构结合在一起，以解决一些特殊的问题。

在实际应用中，树套树码量、常数、空间复杂度都十分巨大，需要一定的卡常数、空间的技巧，同时对码力要求也不小，一般不优先考虑使用树套树解决问题。

标签：树套,重武器,res,mid,pos,int,区间,内权值,id
From： https://www.cnblogs.com/chy12321/p/17329215.html

相关文章

  • [浅谈] 二维数据结构——树套树
    \(\color{purple}\text{Ⅰ.二维树状数组}\)\(\color{orange}\text{例一：P3372【模板】线段树1}\)$\color{green}\text{2023.1.1014:32}$回忆一下树状数组的区间修改......
  • 树套树
    线套线规定使用OI坐标系。（按我的代码习惯）竖着关于\(1\simn\)建一棵线段树，该线段树的每个节点都是一棵内层线段树，若该节点的管辖区间为\([L,R]\)，则该内层线段树......
  • 树套树做矩形加矩形求和。
    题目大意：有一个\(n\timesn\)的矩阵，每个位置上初始值都为\(0\)，\(q\)次操作，分为两种：1.把横坐标在\([x_1,x_2]\)范围内，纵坐标在\([y_1,y_2]\)范围内的所有数加上一......
  • 【YBT2023寒假Day7 C】查区间（线段树套线段树）
    查区间题目链接：YBT2023寒假Day7C题目大意给你一个序列，要你维护两种操作，区间取min和区间求第k小。思路关于区间求第k小，有一个方法，是树套树。外层线段树维护位......
  • [线段树套单调栈] 2019-2020 ICPC Asia Hong Kong Regional Contest H.[Hold the Line
    线段树套单调栈2019-2020ICPCAsiaHongKongRegionalContestH.​​HoldtheLine​​题目大意你已经建造了一条由编号从到的战壕组成的防线，每条战壕最初都是空的。士......
  • 题解 树套树
    题面二叉查找树（BST）是一种简单的数据结构，本题默认你已经熟悉BST的插入和查询两种操作。给你一棵树，每个节点有一个BST。有以下两种操作：\(u,v,k\)：在路径\((u,v)\)上每......
  • 【树套树与分治】
    降维方法可持久化条件：静态问题，且一般都是在线，因为可以离线的话，通常会用各方面更优的离线（分治）算法。减少一个维度后，时间复杂度去掉一个log对于二维问题，可持久化一维，如：......
  • 172 树套树 线段树套平衡树
    视频链接：LuoguP3380【模板】二逼平衡树（树套树）//需要开O2#include<iostream>#include<algorithm>usingnamespacestd;#defineN2000010#defineINF21474836......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99