Q&A
-
主席树与可持久化线段树有什么区别？
主席树全称：可持久化权值线段树。
定义
可查询与修改历史版本的线段树。
基本思想
根据某个定理：
空间复杂度一定不会超过时间复杂度。
所以我们没有必要在每一次操作时把整个线段树复制一遍。
我们在更新版本时，把我们要访问的节点单独复制一遍，然后重新设置父子关系，最后正常更新数据。
简称：一复二设三更新。
实现
struct SegTree {
int lc[MAXN * 20], rc[MAXN * 20], sum[MAXN * 20], rt[MAXN], tot;
int nw() {
tot++;
lc[tot] = rc[tot] = sum[tot] = 0;
return tot;
}
int build(int l, int r) {
int root = nw();
if (l == r)
return root;
int md = l + r >> 1;
lc[root] = build(l, md);
rc[root] = build(md + 1, r);
return root;
}
int update(int k, int l, int r, int x) {
// 一复
int root = nw();
lc[root] = lc[k];
rc[root] = rc[k];
sum[root] = sum[k] + 1;
// ======
if (l == r)
return root;
int md = l + r >> 1;
// 二设
if (x <= md)
lc[root] = update(lc[root], l, md, x);
else
rc[root] = update(rc[root], md + 1, r, x);
// 三更新
sum[root] = sum[lc[root]] + sum[rc[root]];
return root;
}
int query(int k, int l, int r, int x) {
if (l == r)
return l;
int t = sum[lc[k]];
int md = l + r >> 1;
if (x <= t)
return query(lc[k], l, md, x);
else
return query(rc[k], md + 1, r, x - t);
}
} seg;
以上是单点修改区间查询。
根据这个口诀就能很快写出来。
标记永久化
我们如果要进行区间修改区间查询，这个时候就会用到懒标记。
但是这里有个问题，我们不能对原树进行修改，如果修改了就会影响到历史值查询。
但是 pushdown 会神不知鬼不觉地修改历史数据，如果你每一次 pushdown 都新建节点，那空间可能要去见阎王老爷了。
这个时候标记永久化是个很好的选择。
什么意思？就是把 pushdown 直接删除，然后直接在答案统计的时候算上懒标记的贡献就行了。
struct SegTree {
int lc[MAXN * 40], rc[MAXN * 40], l[MAXN * 40], r[MAXN * 40], sum[MAXN * 40], rt[MAXN], lz[MAXN * 40], tot;
int nw() {
tot++;
lc[tot] = rc[tot] = sum[tot] = 0;
l[tot] = r[tot] = 0;
lz[tot] = 0;
return tot;
}
void pushup(int k, int L, int R) {
sum[k] = sum[lc[k]] + sum[rc[k]] + lz[k] * (R - L + 1);
// if (k == 24)
// cerr << sum[k] << endl;
}
int build(int L, int R) {
int root = nw();
l[root] = L;
r[root] = R;
if (L == R) {
sum[root] = v[L];
return root;
}
int md = L + R >> 1;
lc[root] = build(L, md);
rc[root] = build(md + 1, R);
pushup(root, L, R);
return root;
}
int update(int k, int L, int R, int x) {
int root = nw();
lc[root] = lc[k];
rc[root] = rc[k];
l[root] = l[k];
r[root] = r[k];
lz[root] = lz[k];
sum[root] = sum[k];
if (l[root] == L and r[root] == R) {
sum[root] += x * (R - L + 1);
lz[root] += x;
return root;
}
int md = (l[root] + r[root]) / 2;
if (R <= md)
lc[root] = update(lc[root], L, R, x);
else if (L > md)
rc[root] = update(rc[root], L, R, x);
else {
lc[root] = update(lc[root], L, md, x);
rc[root] = update(rc[root], md + 1, R, x);
}
pushup(root, l[root], r[root]);
return root;
}
int query(int k, int L, int R) {
if (l[k] == L and r[k] == R)
return sum[k];
int md = (l[k] + r[k]) / 2;
int ans = lz[k] * (R - L + 1);
if (R <= md)
ans += query(lc[k], L, R);
else if (L > md)
ans += query(rc[k], L, R);
else {
ans += query(lc[k], L, md);
ans += query(rc[k], md + 1, R);
}
return ans;
}
void print(int k) {
if (!k)
return;
cerr << k << "\t" << l[k] << "\t" << r[k] << "\t" << lc[k] << "\t" << rc[k] << "\t" << sum[k] << "\t" << lz[k] << endl;
print(lc[k]);
print(rc[k]);
}
} seg;
这就是标记永久化实现的区间修改区间查询。
具体运用
实际上运用的更多的是主席树（本质上差不多），就是离散化+值域维护。
区间第 \(k\) 小/大
将序列的 \(n\) 个元素依次插入主席树中，查询区间第 \(k\) 小就是查询时看左子树在这个历史内的数的数量是否大于等于排名，大于等于就向左子树扫，不然向右子树扫。
细心的人可能发现，实际上主席树的运用范围覆盖了普通莫队乃至带修莫队，而且时间复杂度也更胜一筹，但是较莫队来讲思想较复杂，调试较困难，需要均衡考量。
各种时间穿梭
这种就不用说了，很裸。
标签：md,持久,lc,int,线段,笔记,tot,rc,root From： https://www.cnblogs.com/LightningCreeper/p/17966368