可持久化平衡树

序:

  • 花了将近大半天学着写了两个可持久化平衡树代码…

可持久化平衡树:

  • 顾名思义,可持久化平衡树就是在平衡树的基础上加一个可持久化…
  • 学过可持久化线段树的都知道(我没学过),可持久化是怎么回事…
  • 可持久化是为了解决那些需要询问历史版本的题目,所以我们每一次操作都需要开辟一个新版本…
  • 但是如果每次我们都开辟一个新版本,把整棵树复制一遍,非常明显会炸空间,所以怎么办呢,我们发现我们每次操作因为有懒标记的存在其实只需要修改log(n)个点,也就是说我们其实可以使用以前的点进行操作.每次对于分裂和合并操作,我们只要新开几个点把信息复制上去然后再做就好了…
  • 也就是说我们在新开的链将要进行merge和split,然后其实不用每次操作都把点开好,只要做到哪里改哪里…
  • 我们直接来看这道题目…

luoguP3835 【模板】可持久化平衡树

分析:

  • 对于这道题目,我们只需要在原来的代码上修改就好了…
  • 我们直接对着代码讲:
int merge(int x, int y)
{
    if (!node[x].siz)
        return y;
    if (!node[y].siz)
        return x;
    int _root = ++cnt;
    if (node[x].p < node[y].p)
    {
        node[_root] = node[x];
        node[_root].ch[1] = merge(node[_root].ch[1], y);
        updata(_root);
        return _root;
    }
    else
    {
        node[_root] = node[y];
        node[_root].ch[0] = merge(x, node[_root].ch[0]);
        updata(_root);
        return _root;
    }
}
  • 我们可以看到大部分操作都是相同的,只是原来我们直接修改x和y,现在我们新开一个节点然后复制后当做新x和y使用就好了…
  • 下面看split:
void split_key(int now, int &x, int &y, int k)
{
    if (!node[now].siz)
    {
        x = y = 0;
        return;
    }
    if (node[now].key <= k)
    {
        x = ++cnt;
        node[x] = node[now];
        split_key(node[x].ch[1], node[x].ch[1], y, k);
        updata(x);
    }
    else
    {
        y = ++cnt;
        node[y] = node[now];
        split_key(node[y].ch[0], x, node[y].ch[0], k);
        updata(y);
    }
}
  • 对于分裂也一样我们给x,y分配一个新的点..
  • 看别人的博客,好像合并并不需要要开新点,因为每次合并操作必定带着分裂,分裂时已经开过新点了,所以不开新点可以省一些空间…
  • 但是,我并不管这么多,能用就好了…

代码:

#include<bits/stdc++.h>
#define LL long long
const LL N=3e7+10;
const LL inf=2147483647;
using namespace std;
template<typename tp> inline void read(tp &x)
{
    x=0; char c=getchar(); bool f=0;
    for(;c<'0'||c>'9';f|=(c=='-'),c = getchar());
    for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
    if(f) x=-x;
}
namespace Treap
{
    int a,b,c,d,e;
    int cnt=0,root[N];
    struct Node{int key,siz,p,ch[2];} node[N];
    void new_node(int key) {node[++cnt].key=key,node[cnt].p=rand(),node[cnt].siz=1;}
    void updata(int now) {node[now].siz=node[node[now].ch[0]].siz+node[node[now].ch[1]].siz+1;}
    int merge(int x,int y)
    {
        if(!node[x].siz) return y; if(!node[y].siz) return x;
        int _root=++cnt;
        if(node[x].p<node[y].p) {node[_root]=node[x];node[_root].ch[1]=merge(node[_root].ch[1],y);updata(_root);return _root;}
        else {node[_root]=node[y];node[_root].ch[0]=merge(x,node[_root].ch[0]);updata(_root);return _root;}
    }
    void split_key(int now,int &x,int &y,int k)
    {
        if(!node[now].siz) {x=y=0;return;}
        if(node[now].key<=k) {x=++cnt;node[x]=node[now];split_key(node[x].ch[1],node[x].ch[1],y,k);updata(x);}
        else {y=++cnt;node[y]=node[now];split_key(node[y].ch[0],x,node[y].ch[0],k);updata(y);}
    }
    int val(int now,int k)
    {
        if(k==node[node[now].ch[0]].siz+1) return node[now].key;
        else if(k<node[node[now].ch[0]].siz+1) return val(node[now].ch[0],k);
        else return val(node[now].ch[1],k-node[node[now].ch[0]].siz-1);
    }
    int ranks(int &root,int k,int ret=0) {split_key(root,a,b,k-1); ret=node[a].siz+1; root=merge(a,b); return ret;}
    void insert(int &root,int k) {split_key(root,a,b,k);new_node(k);root=merge(a,merge(cnt,b));}
    void Delete(int &root,int k) {split_key(root,a,b,k);split_key(a,c,d,k-1);d=merge(node[d].ch[0],node[d].ch[1]);root=merge(merge(c,d),b);}
    int pre(int &root,int k,int ret=-inf) {split_key(root,a,b,k-1);if(node[a].siz) ret=val(a,node[a].siz);root=merge(a,b);return ret;}
    int suf(int &root,int k,int ret=inf) {split_key(root,a,b,k);if(node[b].siz) ret=val(b,1);root=merge(a,b);return ret;}
}
using namespace Treap;
int n,m,num,k;
signed main()
{
    read(n);
    for(int i=1;i<=n;i++)
    {
        read(m),read(num),read(k); root[i]=root[m];
        if(num==1) insert(root[i],k);
        if(num==2) Delete(root[i],k);
        if(num==3) printf("%d\n",ranks(root[i],k));
        if(num==4) printf("%d\n",val(root[i],k));
        if(num==5) printf("%d\n",pre(root[i],k));
        if(num==6) printf("%d\n",suf(root[i],k));
    }
    return 0;
}
  • 小小压了个行,大概就这个样子,最好复制一下,自己粘贴后可以看…

luoguP5055 【模板】可持久化文艺平衡树

分析:

  • 这道题目堪称毒瘤,我整整打了5,6个小时…
  • 这道题目要支持在历史上的区间翻转,我们已经知道,这题要用到懒标记…
  • 然后按照道理,我们也正常写,然后,这题比上一题多了一个push_down操作…这个怎么写呢…
  • 已知,当我们每次访问一个点的时候我们要先下放标记,因为如果这个点有懒标记,那么他的左右儿子要互换,也就是说我们不可以先去询问哪个子树大,这样会导致操作失误,所以我们先下放标记…
  • 怎么下放呢…
  • 我的写法非常暴力,给他左右儿子复制一遍,直接交换然后下传就好了…

代码:

#include <bits/stdc++.h>
#define LL long long
#define P pair<int, int>
const LL N = 2e7 + 10;
const LL mod = 998244353;
const LL inf = 0x3f3f3f3f;
const double eps = 1e-9;
using namespace std;
template <typename tp>
inline void read(tp &x)
{
    x = 0; char c = getchar(); bool f = 0;
    for (; c < '0' || c > '9'; f |= (c == '-'), c = getchar());
    for (; c >= '0' && c <= '9'; x = (x << 3) + (x << 1) + c - '0', c = getchar());
    if (f) x = -x;
}
namespace Treap
{
    int a, b, c, d, e, root[N], cnt;
    struct Node {int key, ch[2], rev, p, siz; LL sum;} node[N];
    void new_node(int key) {node[++cnt].key = key; node[cnt].sum = key; node[cnt].siz = 1; node[cnt].p = rand(); node[cnt].rev = 0; node[cnt].ch[0] = node[cnt].ch[1] = 0;}
    void updata(int now) {node[now].siz = node[node[now].ch[0]].siz + node[node[now].ch[1]].siz + 1; node[now].sum = node[node[now].ch[0]].sum + node[node[now].ch[1]].sum + node[now].key;}
    void push_down(int now)
    {
        if (!node[now].rev) return; node[now].rev = 0; int l = node[now].ch[0], r = node[now].ch[1];
        node[++cnt] = node[r]; node[now].ch[0] = cnt; if (node[cnt].siz) node[cnt].rev ^= 1;
        node[++cnt] = node[l]; node[now].ch[1] = cnt; if (node[cnt].siz) node[cnt].rev ^= 1;
    }
    int merge(int x, int y)
    {
        if (!node[x].siz) return y; if (!node[y].siz) return x;
        int rt = ++cnt;
        if (node[x].p < node[y].p) {push_down(x); node[rt] = node[x]; node[rt].ch[1] = merge(node[rt].ch[1], y); updata(rt); return rt;}
        else {push_down(y); node[rt] = node[y]; node[rt].ch[0] = merge(x, node[rt].ch[0]); updata(rt); return rt;}
    }
    void split_k(int now, int &x, int &y, int k)
    {
        if (!node[now].siz) {x = y = 0; return;} push_down(now);
        if (node[node[now].ch[0]].siz < k) {x = ++cnt; node[x] = node[now]; split_k(node[x].ch[1], node[x].ch[1], y, k - node[node[now].ch[0]].siz - 1); updata(x);}
        else {y = ++cnt; node[y] = node[now]; split_k(node[y].ch[0], x, node[y].ch[0], k); updata(y);}
    }
    void insert(int &root, int k, int key){ split_k(root, a, b, k); new_node(key); root = merge(merge(a, cnt), b);}
    void Delete(int &root, int k) {split_k(root, a, b, k - 1); split_k(b, c, d, 1); root = merge(a, d);}
    void Reverse(int &root, int l, int r) {split_k(root, a, b, r); split_k(a, c, d, l - 1); node[d].rev ^= 1; root = merge(merge(c, d), b);}
    LL Sum(int &root, int l, int r, LL ret = 0) {split_k(root, a, b, r); split_k(a, c, d, l - 1); ret = node[d].sum; root = merge(merge(c, d), b); return ret;}
} // namespace Treap
using namespace Treap;
LL n, m, opt, l, r, last;
signed main()
{
    read(n);
    for (int i = 1; i <= n; i++)
    {
        read(m); read(opt); root[i] = root[m];
        if (opt == 1) read(l), read(r), insert(root[i], l ^ last, r ^ last);
        if (opt == 2) read(l), Delete(root[i], l ^ last);
        if (opt == 3) read(l), read(r), Reverse(root[i], l ^ last, r ^ last);
        if (opt == 4) read(l), read(r),printf("%lld\n", last = Sum(root[i], l ^ last, r ^ last));
    }
    return 0;
}

关于“可持久化平衡树”我的5个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注