View

可持久化线段树、可持久化权值线段树

1. LG3919 可持久化数组(可持久化线段树板子)
2. LG3834 区间第k大值(可持久化权值线段树板子)
3. [POI2014]KUR-Couriers(区间众数板子)
4. LG4137 Rmq Problem(区间mex板子)

可持久化平衡树

可持久化01trie

Detail

可持久化线段树

Note

思想

实际上就是用线段树维护了一个数组 , 然后对修改在线段树上执行可持久化的操作。

特殊地 , 在可持久化数组的实现中 , 用到线段树本身的性质只有naive的(单点查询/单点修改)。因而非叶子节点的data域可以不用维护数据。当然 , 线段树维护数组数据时可以简单维护的数组信息如区间最大值、区间和等一样可以可持久化。

可持久化针对单点修改操作 , 实际上修改掉的就是一条链。将这条由根到叶子的链复制出来进行修改 , 并返回新的根 , 就可以通过这个新的根来访问这个版本的信息(那些不变的部分由其父亲复制出来的新版本的节点直接指向从而实现了空间的节省)。

void insert(int &p, int rec, int lp, int rp, int x, int v) {
	p = tot++; ls[p] = ls[rec], rs[p] = rs[rec], dat[p] = dat[rec];     //将要修改的链上的节点rec复制一份作为当前树的节点。
	if(lp == rp) { dat[p] = v; return; }    //对叶子节点做修改
	int mid = (lp + rp) >> 1;
    //递归处理要修改的链上当前点的后继
	if(x <= mid) insert(ls[p], ls[rec], lp, mid, x, v);
	else insert(rs[p], rs[rec], mid + 1, rp, x, v);
    //如果需要用线段树维护信息 , 这里还要加上update(p)
}

空间大小的精确计算(对于普通的可持久化线段树 , 对长度为 $\mathcal{n}$ 的序列建树并做 $m$ 次修改) :

分析

由二叉树的性质 , 线段树树高上界(即链长上界)为 $\lceil \log _2 maxn \rceil + 1$ 个结点空间大小。树中结点个数的上界为 $2^{\lceil \log _2 maxn \rceil + 1} - 1$ 。

建树过程中 , 确切空间花销上界为 $2^{\lceil \log _2 maxn \rceil + 1} - 1$ 个结点空间大小。

修改过程中 , 观察每次修改实际上就是复制了一条链 , 空间花销等于链所占的空间 , 故单次修改的空间上界即为链长上界 。 则 $m$次修改的空间总花销上界为 $m(\lceil \log _2 maxn \rceil + 1)$ 个结点空间大小。

总共的空间开销上界为(单位 : 结点空间大小)

$2^{\lceil \log _2 maxn \rceil + 1} + m(\lceil \log _2 maxn \rceil + 1) - 1$

$\mathcal($ i.e. 空间复杂度为$\mathcal{O(n + m\ log n)}$ $\mathcal)$

具体写题时的操作

记忆 : 链长上界为 $\lceil \log _2 maxn \rceil + 1$ ， $maxn$ 为序列长(叶子结点个数)。

1. 先算出满足 $2^k \geqslant n$ 的最小的 $k$ , 就是 $\lceil \log _2 maxn \rceil$ 。

（p.s. 平时可以打开IDLE)

>i = 1
>k = 0
>t = ...(maxn)
>while i < t:
...	i = i * 2
...	k = k + 1
>k

2. 然后链长为 $k + 1$ , $q$ 个查询的最多产生结点个数 $q(k+1)$ 。
3. 如果有初始化build操作 , 不要忘记初始build产生的 $2k-1$ 个结点。

区间修改引发的问题及两种解决方式

在进行可持久化线段树维护区间修改的时候 , 注意不能直接下放标记。因为在修改时可能出现下放标记到的点被其他的版本共用。解决的一个方案是将要被下放到待修改的点复制一遍然后对复制出来的点做修改并作为这个版本的新点 , 这样的坏处是空间利用率非常低很容易MLE。另一种策略是标记永久化 , 但这样做的局限是要下放的标记是相对标记(区间加减是相对标记 , 区间赋值是绝对标记)???

特殊地 , 对于刚开始为空的树不用进行build操作(想想性质)。

可持久化权值线段树

对权值线段树进行可持久化 , 可以得到不同历史版本的区间上的权值信息。

动态开点

对于未定的值域采用动态开点是权值线段树的常见操作。但是由于可持久化线段树本身也是动态开点的 , 所以几乎不用做任何修改 , 直接上即可。在细节处需注意特判p = 0的情况以及其意义。

维护任意区间

思想

把序列下标顺序作为时间轴 , 按照序列递进作为时间演进顺序 , 可以得到所有前缀序列$[1, i]$的信息。具体地 , 从左向右扫一遍序列 $A = {a_1, a_2, ..., a_n}$ , 每次插入1个值 $a_i$ , 当前版本即为区间$[1,i]$的信息。

对于支持区间减的信息 , 可以用 $r$ 版本的线段树的数据减去 $l-1$ 版本的数据进而统计区间 $[l-1, r]$ 上的信息(同时对两棵树同步递归查询 , 值域相减就相当于一棵 $[l,r]$ 区间上的线段树)。

对于另一部分信息 , 可以维护一个最晚出现的时间 , 在查询 $[l,r]$ 时查询 $r$ 版本的树并判断是否在 $[l,r]$ 内(比较最晚出现的位置和 $l$ 的大小关系)。

用途

对于可持久化权值线段树维护的区间可查询任意一段区间的权值信息(用r版本的个数减去l-1版本的个数得到区间 $[l, r]$ 上的权值信息)。进而用来高效求不带修的在线查询任意区间第 $k$ 大值 , 任意区间众数等等。

做题思路

实际思考中 , 考虑在当前版本(序列即前缀区间)上维护一个信息 , 然后再拓展到可持久化上。

在线段树/权值线段树维护的序列上能简单高效查询的信息几乎都可以用可持久化线段树/权值线段树利用前缀和的思想支持任意区间快速查询。

实现带修

用树状数组套线段树 , 可以实现维护任意区间带修。

习题

LG3919可持久化数组(可持久化线段树板子)

思路

可持久化数组使用可持久化线段树来维护 , 本题不需要用到线段树的其他性质。

事项

1. 在insert下传时 , 不要忘记将原链上的点变为后继 , 即insert(..., ls[pre], ...)不要写成insert(..., pre, ...)。

Code

#include <bits/stdc++.h>

using namespace std;

const int maxs = 23000010, maxn = 1000010;

int dat[maxs], ls[maxs], rs[maxs], tot;
int vers[maxn];

inline void read(int &x) {
	x = 0; int f = 1; char ch = getchar();
	while(ch < '0' || ch > '9') {if(ch == '-') f = -f; ch = getchar();}
	while(ch >= '0' && ch <= '9') x = (x<<3) + (x<<1) + (ch&15), ch = getchar();
	x *= f;
}

void build(int &p, int lp, int rp) {
	p = tot++;
	if(lp == rp) { read(dat[p]); return; }
	int mid = (lp + rp) >> 1;
	build(ls[p], lp, mid);
	build(rs[p], mid + 1, rp);
}

void insert(int &p, int rec, int lp, int rp, int x, int v) {
	p = tot++; ls[p] = ls[rec], rs[p] = rs[rec], dat[p] = dat[rec];
	if(lp == rp) { dat[p] = v; return; }
	int mid = (lp + rp) >> 1;
	if(x <= mid) insert(ls[p], ls[rec], lp, mid, x, v);
	else insert(rs[p], rs[rec], mid + 1, rp, x, v);
}

int qry(int p, int lp, int rp, int x) {
		if(lp == rp) return dat[p];
	int mid = (lp + rp) >> 1;
	if(x <= mid) return qry(ls[p], lp, mid, x);
	return qry(rs[p], mid + 1, rp, x);
}

int main() {
	int n, m;
	read(n); read(m);
	tot = 1;
	build(vers[0], 1, n);
	int v, op, loc, value;
	for(int vs = 1; vs <= m; ++vs) {
		read(v); read(op); read(loc);
		if(op == 1) {
			read(value);
			insert(vers[vs], vers[v], 1, n, loc, value);
		} else {
			printf("%d\n",qry(vers[v], 1, n, loc));
			vers[vs] = vers[v];
		}
	}
	return 0;
}

LG3834 区间第K大值(可持久化权值线段树板子)

思路

用可持久化权值线段树来维护权值size信息的区间前缀和 ，不同版本的两棵树作差得到任意区间权值size信息。

事项

1. 在开始扫原数组之前树是空的 , 并且可以不用建树(想一想性质 , 与动态开点线段树中往空树插第一个数据时的情形类似)。
2. 可以使用动态开点线段树思想过掉本题(这样不用离散化) , 但是在某些值域更大的题目据说会MLE。(对于动态开点 , 一定不要去build(实际上非动态开点在本题中也不需要) , 然后直接下来就可以了 , 不用做更改 , 因为可持久化线段树的开点操作本来就是动态的 , 需要注意的是在负数内除以2下取整要用lp + rp >> 1 , 不要使用 (lp + rp) / 2 , 它在负数情况中会向上取整)。

Code

#include <bits/stdc++.h>

using namespace std;

const int maxs = 4000010, maxn = 200010;
int dat[maxs], ls[maxs], rs[maxs], idx[maxn], tot;
int a[maxn], b[maxn];

inline void read(int &x) {
	char ch; int f = 1; x = 0;
	do{ch = getchar(); if(ch == '-') f = -1;} while(ch < '0' || ch > '9');
	do{ x = (x<<3)+(x<<1)+(ch&15), ch = getchar(); } while(ch >= '0' && ch <= '9');
	x *= f;
}

int getbound(int l, int r, int xx) {
	while(l < r) {
		int mid = (l + r) >> 1;
		if(b[mid] == xx) return mid;
		else if(b[mid] > xx) r = mid - 1;
		else l = mid + 1;
	}
	return l;
}

void insert(int &p, int pre, int lp, int rp, int x) {
	p = ++tot; ls[p] = ls[pre], rs[p] = rs[pre], dat[p] = dat[pre] + 1;
	if(lp == rp) return;
	int mid = (lp + rp) >> 1;
	if(x <= mid) insert(ls[p], ls[pre], lp, mid, x);
	else insert(rs[p], rs[pre], mid + 1, rp, x);
}

int findkth(int r, int lol, int lp, int rp, int k) {
	if(lp == rp) return lp;
	int mid = (lp + rp) >> 1;
	if(k <= dat[ls[r]] - dat[ls[lol]]) return findkth(ls[r], ls[lol], lp, mid, k);
	else return findkth(rs[r], rs[lol], mid + 1, rp, k - dat[ls[r]] + dat[ls[lol]]);
}

int main() {
	int n, m, l, r, k;
	read(n); read(m);
	for(int i = 1; i <= n; ++i) {
		read(a[i]);
		b[i] = a[i];
	}
	sort(b + 1, b + n + 1);
	int nn = 1;
	for(int i = 2; i <= n; ++i)
		if(b[i] != b[i-1])
			b[++nn] = b[i];
	tot = dat[0] = ls[0] = rs[0] =  idx[0] = 0;
	for(int i = 1; i <= n; ++i)
		insert(idx[i], idx[i-1], 1, nn, getbound(1, nn, a[i]));	
	while(m--) {
		read(l); read(r); read(k);
		printf("%d\n", b[findkth(idx[r], idx[l - 1], 1, nn, k)]);
	}
	return 0;
}

[POI2014] KUR-Couriers(区间众数板子)

思路

先考虑用序列上权值线段树求序列众数 , 即每次向权值大于 $\frac{1}{2}$ 区间长度的子树走 , 能到子树结点且size大于 $\frac{1}{2}$ 则当前权值即为区间众数 , 否则没有区间众数。

任意区间则对权值线段树可持久化实现维护前缀序列的权值信息。两树做差得到其间区间的信息。

事项

Code

#include <bits/stdc++.h>

using namespace std;

const int maxs = 10000010, maxn = 500010;

int dat[maxs], ls[maxs], rs[maxs], tot;
int root[maxn], a[maxn], b[maxn];

inline int read() {
	char ch; int f = 1, x = 0;
	do{ch=getchar();if(ch=='-')f=-f;}while(ch<'0'||ch>'9');
	do{x=(x<<3)+(x<<1)+(ch&15),ch=getchar();}while(ch>='0'&&ch<='9');
	return x * f;
}

void insert(int &p, int pre, int lp, int rp, int x) {
	p = ++tot; ls[p] = ls[pre]; rs[p] = rs[pre]; dat[p] = dat[pre] + 1;
	if(lp == rp) return;
	int mid = lp + rp >> 1;
	if(x <= mid) insert(ls[p], ls[pre], lp, mid, x);
	else insert(rs[p], rs[pre], mid + 1, rp, x);
}

int hf;
int qry(int rtr, int lol, int lp, int rp) {
	if(lp == rp || dat[rtr] - dat[lol] <= hf) return dat[rtr] - dat[lol] > hf ? lp : 0;
	int mid = lp + rp >> 1;
	if(dat[ls[rtr]] - dat[ls[lol]] > hf) return qry(ls[rtr], ls[lol], lp, mid);
	return qry(rs[rtr], rs[lol], mid + 1, rp);
}

int main() {
	int n = read(), m = read(), nn = 1, ll, rr;
	for(int i = 1; i <= n; ++i) a[i] = b[i] = read();
	sort(b + 1, b + n + 1);
	for(int i = 2; i <= n; ++i)
		if(b[i] != b[i-1]) b[++nn] = b[i];
	for(int i = 1; i <= n; ++i)
		insert(root[i], root[i-1], 1, nn, lower_bound(b + 1, b + nn + 1, a[i]) - b); 
	while(m--) {
		ll = read(), rr = read();
		hf = rr - ll + 1 >> 1;
		printf("%d\n", b[qry(root[rr], root[ll-1], 1, nn)]); 
	}
	return 0;
}

LG4137 Rmq Problem(区间mex板子)

思路

用可持久化线段树维护前缀区间中每个权值最晚出现的次数的最小值。在前缀版本 $[1,r]$ 中查询询问 $[l,r]$ , 若 $dat < l$ 说明该段中某个权值在区间之外(序列中不存在该数用初值 $0$ 表示)。优先向左查 , 到叶子返回(必然存在区间mex)。

权值较大需要动态开点。

事项

1. 动态开点树中孩子不存在的情况 , 说明它代表的区间的 $dat$ 为 $0$ , 或者说 , 这些权值不存在。递归到这样的点"则直接返回区间左端点。不要忘记特判。

code

#include <bits/stdc++.h>

using namespace std;

const int maxn = 200010, maxs = 6200010;

int dat[maxs], ls[maxs], rs[maxs], tot;
int root[maxn], a[maxn];

inline void read(int &x) {
	x=0; char ch; int f=1;
	do{ch=getchar();if(ch=='-')f=-f;}while(ch<'0'||ch>'9');
	do{x=(x<<3)+(x<<1)+(ch&15),ch=getchar();}while(ch>='0'&&ch<='9');
	x*=f;
}

void insert(int &p, int pre, int lp, int rp, int x, int v) {
	p = ++tot; ls[p] = ls[pre]; rs[p] = rs[pre]; dat[p] = dat[pre];
	if(lp==rp) {
		dat[p] = v; return;
	}
	int mid = lp + rp >> 1;
	if(x <= mid) insert(ls[p], ls[pre], lp, mid, x, v);
	else insert(rs[p], rs[pre], mid + 1, rp, x, v);
	dat[p] = min(dat[ls[p]], dat[rs[p]]);
}

int limit;
int qry(int p, int lp, int rp) {
	if(!p || lp == rp) return lp;
	int mid = lp + rp >> 1;
	if(dat[ls[p]] < limit) return qry(ls[p], lp, mid);
	return qry(rs[p], mid + 1, rp);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int n, m, mx = -1, l, r;
	read(n); read(m);
	for(int i = 1; i <= n; ++i) {
		read(a[i]); mx = max(mx, a[i]);
	}
	++mx;
	for(int i = 1; i <= n; ++i)
		insert(root[i], root[i-1], 0, mx, a[i], i);
	while(m--) {
		read(l); read(r);
		limit = l;
		printf("%d\n", qry(root[r], 0, mx));
	}
	return 0;
}