Java教程

高级数据结构笔记

本文主要是介绍高级数据结构笔记,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

树套树

顾名思义,就是一个树套一个树。。。

广义的树套树是指嵌套多层的数据结构。常见的有:线段树套线段树(二维线段树),线段树套平衡树(“二逼平衡树”),分块套平衡树,树状数组套线段树(带修主席树)等等。

在这里,由于 setmap 等 STL 内部实现是平衡树,因此将这些 STL 的嵌套也算作树套树。

树套树解决偏序问题

树套树最典型的应用就是解决各种各样的偏序问题。

P3810 【模板】三维偏序(陌上花开)

经典解法是 CDQ 分治。这里使用树状数组套权值线段树解决。

首先第一维是经典的排序,第二维可以使用树状数组维护起来。树状数组的每个节点维护一棵动态开点线段树,维护这个节点范围内所有节点的第三维信息。

时间复杂度 \(O(n \log ^ 2 n)\),空间 \(O(n \log n)\)

放一下主体部分代码:

struct node {
	int ls, rs, s;
}tr[M];
#define lc tr[u].ls
#define rc tr[u].rs
#define mid (l + r >> 1)
void add(int &u, int l, int r, int x) {
	if (!u) u = ++ cnt; tr[u].s ++ ; 
	if (l == r) return;
	if (x <= mid) add(lc, l, mid, x);
	else add(rc, mid + 1, r, x);
}
void ADD(int x, int y) {
	for (int i = x; i <= m; i += (i & -i)) add(rt[i], 1, m, y);
}
int sum(int &u, int l, int r, int x) {
	if (!u or l > x) return 0;
	if (r <= x) return tr[u].s;
	return sum(lc, l, mid, x) + sum(rc, mid + 1, r, x);
}
int SUM(int x, int y, int s = 0) {
	for (int i = x; i; i -= (i & -i)) s += sum(rt[i], 1, m, y); return s;
}

P3157 [CQOI2011] 动态逆序对

将删点操作倒过来,就是逆序加点的过程。

将加点的顺序(即时间轴)看做第一维,将下标看做第二维,将权值看做第三维。

这就是典型的三维偏序问题。直接树套树带走。

提交记录

  • Levko and Array

树套树解决二维数点问题

这里的二维数点定义比较广泛,包括点个数的计数,以及满足某些性质的点集查询等。

通常,二维数点问题有以下几种做法:

  • 将第一维分块,块内套 set 等数据结构维护第二维。同时对于每个 \(x\) 坐标建立一个 set,用于维护散块信息。

  • 对第一维建线段树,线段树节点里面套 set / 平衡树。

  • 对第一维建树状数组,树状数组每个节点里套 set / 平衡树。

对于第一种方法,直接对于整块 / 散块里的平衡树 lower_bound 即可。

对于第二种方法,定位到线段树上的 \(O(\log n)\) 个区间之后和第一种一样。

对于第三种方法,需要根据情况具体分析。有时需要维护树状数组后缀 \(\max\) 或者前缀 \(\max\),有时需要维护点数等等。优势是常数小。

CF19D Points

很好的一道题。但是由于题目丧心病狂的卡常,我至今没有用树状数组套 set 卡过去。

题目显然是二维数点,属于求满足某种条件的点集类型题目。条件是某个点右上方的最左下的点。

第一种思路是分块套 set。对于横纵坐标离散化之后,对于每个横坐标维护一个 set,记录横坐标为该值的所有纵坐标。同时对每个块维护一个类型为 pairset,维护横坐标在该块内的所有点。

每次插入和查询复杂度都是 \(O(\log n)\)。查询复杂度需要查询 \(O(\sqrt n)\) 个整块,每个整块需要 \(O(\log n)\) 的复杂度。需要查询 \(O(\sqrt n)\) 个单点,单点复杂度 \(O(\log n)\)。因此总复杂度 \(O(m \sqrt n \log n)\)。轻松的跑过去了。

第二种思路是树状数组套 set。对于纵坐标用树状数组维护,内层套 set 维护横坐标。插入的时候只需要在右端点 \(< y\) 的节点的 set 内插点就可以了。对于查询操作,只需要在左端点 \(\ge y\) 的节点 setlower_bound 即可。复杂度 \(O(m \log ^ 2 n)\)

不知道为什么,常数和复杂度都小的树状数组套 set 没有卡过去/kk

分块套 set 代码

树状数组套 set :

set<PII> s[N]; vector<int> p;
int n, lim;
struct Q { int op, x, y; }q[N];
void add(int x, int y) {
	for (int i = y; i; i -= (i & -i)) s[i].insert(mp(x, y));
}
void del(int x, int y) {
	for (int i = y; i; i -= (i & -i)) s[i].erase(mp(x, y));
}
PII ask(int x, int y) {
	PII ans = mp(INF, INF);
	for (int i = y; i <= lim; i += (i & -i))
		ans = min(ans, *s[i].lower_bound(mp(x, y)));
	return ans;
}
int main() {
	read(n);
	rep(i, 1, n) {
		char ch[7]; int x, y;
		scanf("%s", ch); read(x, y);
		if (*ch == 'a') q[i] = {0, x, y};
		if (*ch == 'r') q[i] = {1, x, y};
		if (*ch == 'f') q[i] = {2, ++ x, ++ y};
		p.push_back(y);
	} sort(all(p)); p.resize(unique(all(p)) - p.begin()); 
	lim = p.size();
	auto find = [](int x) -> int {
		return lower_bound(all(p), x) - p.begin() + 1;
	};
	rep(i, 1, n) q[i].y = find(q[i].y);
	rep(i, 1, lim) s[i].insert(mp(INF, INF));
	rep(i, 1, n) {
		if (q[i].op == 0) add(q[i].x, q[i].y);
		if (q[i].op == 1) del(q[i].x, q[i].y);
		if (q[i].op == 2) {
			register PII ans = ask(q[i].x, q[i].y);
			if (ans.first == INF) puts("-1");
			else write(' ', ans.first, p[ans.second - 1]), pc('\n');
		}
	} return 0;
}

Intersection of Permutations

比较套路的一道题。若有 \(b_x = a_y\),那么记 \(t_x = y\)

问题转化成了:

  • 查询操作:查询在 \(l_b \sim r_b\) 中,有多少 \(t_i \in [l_a, r_a] \bigcup \mathbb{Z}\)

  • 修改操作:交换 \(t_x, t_y\)

这是一个带修的二维数点,直接树状数组套权值线段树带走。

注意要写空间回收,要不然会 MLE。

struct node { int ls, rs, s; }tr[M];
#define ls tr[u].ls
#define rs tr[u].rs
#define mid (l + r >> 1)
int New() { return !top ? ++ cnt : stk[top -- ]; }
void add(int &u, int l, int r, int x, int v) {
	if (l > x or r < x) return;
	if (!u) u = New(); tr[u].s += v; if (l == r) return;
	add(ls, l, mid, x, v), add(rs, mid + 1, r, x, v);
	if (!tr[u].s) stk[ ++ top] = u, u = 0;
}
void ADD(int x, int p, int v) {
	for (int i = x; i <= n; i += (i & -i)) add(rt[i], 1, n, p, v);
}
int ask(int u, int l, int r, int L, int R) {
	if (!u or r < L or l > R) return 0;
	if (l >= L and r <= R) return tr[u].s;
	return ask(ls, l, mid, L, R) + ask(rs, mid + 1, r, L, R);
}
int ASK(int la, int ra, int lb, int rb, int s = 0) { lb -- ;
	for (int i = rb; i; i -= (i & -i)) s += ask(rt[i], 1, n, la, ra);
	for (int i = lb; i; i -= (i & -i)) s -= ask(rt[i], 1, n, la, ra); return s;
}
int main() {
	scanf("%d%d", &n, &m);
	rep(i, 1, n) scanf("%d", &a[i]), bin[a[i]] = i;
	rep(i, 1, n) scanf("%d", &b[i]);
	rep(i, 1, n) t[i] = bin[b[i]], ADD(i, t[i], 1);
	while (m -- ) {
		int op, la, ra, lb, rb, x, y;
		scanf("%d", &op);
		if (op & 1) {
			scanf("%d%d%d%d", &la, &ra, &lb, &rb);
			printf("%d\n", ASK(la, ra, lb, rb));
		} else {
			scanf("%d%d", &x, &y);
			ADD(x, t[x], -1); ADD(y, t[y], -1);
			swap(t[x], t[y]); ADD(x, t[x], 1); ADD(y, t[y], 1);
		}
	} return 0;
}

树套树解决带修区间第 \(k\) 大问题

不带修的区间第 \(k\) 大,正经解法就是主席树。

那么如果带修了呢?

可以外层一个树状数组维护下标,内层一个权值线段树维护这个区间的权值。

这样相当于把一棵主席树拆成了许多个动态开点线段树。

修改时,每次修改树状数组的 \(\log\) 个节点,每修改一个节点需要一个老哥,所以就是 \(O(\log ^ 2 n)\)

查询就是前缀和的容斥。前缀和要在树状数组上做,所以是两个 \(\log\)

经典例题:

P2617 Dynamic Rankings

放一下主体部分代码:

struct node {
	int ls, rs, s;
}tr[M]; int rt[N];
vector<int> L, R;
int n, m, cnt, a[N];
#define lc tr[u].ls
#define rc tr[u].rs
#define mid (l + r >> 1)
void add(int &u, int l, int r, int x, int v) {
	if (l > x or r < x) return;
	if (!u) u = ++ cnt; tr[u].s += v;
	if (l == r) return;
	add(lc, l, mid, x, v); add(rc, mid + 1, r, x, v);
}
void ADD(int x, int v, int c) {
	for (int i = x; i <= n; i += (i & -i))
		add(rt[i], 0, V, v, c);
}
int ask(int l, int r, int k) {
	if (l == r) return r; int s = 0;
	for (auto &u : R) s += tr[lc].s;
	for (auto &u : L) s -= tr[lc].s;
	if (k <= s) {
		for (auto &u : L) u = lc;
		for (auto &u : R) u = lc;
		return ask(l, mid, k);
	}
	for (auto &u : L) u = rc;
	for (auto &u : R) u = rc;
	return ask(mid + 1, r, k - s);
}
int ASK(int l, int r, int k) {
	L.clear(); R.clear(); l -- ;
	for (int i = r; i; i -= (i & -i)) R.pb(rt[i]);
	for (int i = l; i; i -= (i & -i)) L.pb(rt[i]);
	return ask(0, V, k);
}

Summary: 在大部分时候,需要维护的信息具有左 / 右端点固定或者可差分性时,使用树状数组套数据结构是一个不错的选择。

当然,有时分块套数据结构可以获得意想不到的小常数。

这篇关于高级数据结构笔记的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!