算法学习
9 minutes read (About 1420 words)

算法学习-可持久化数据结构

概述

可持久化数据结构可以存储数据集在任意时间的历史状态。“可持久化”的基本思想是在每项操作结束后，仅创建数据结构中发生改变的部分的副本，不拷贝其他部分。这样一来，维护数据结构的时间复杂度没有增加，空间复杂度仅增长为与时间同级的规模。换言之，可持久化数据结构能够高效地记录一个数据结构的所有历史状态。

可持久化Trie

【实现过程】

  1. 设当前可持久化Trie的根节点为root，令p=root，i=0
  2. 建立一个新的节点，令root‘=q
  3. 若p!=0，则对于每种字符c，令trie[q,c]=trie[p,c]
  4. 建立一个新的节点q’，令trie[q,s]=q‘
  5. 令p=trie[p,s]，q=trie[q,s]，i=i+1
  6. 重复步骤3-5，直到i到达字符串末尾

【例题】最大异或和 luogu-p4735

给定一个非负整数序列{a}，初始长度为N。

有M个操作，有以下两种操作类型：

  1. A x：添加操作，表示在序列末尾添加一个数x，序列的长度N+1。
  2. Q l r x：询问操作，你需要找到一个位置p，满足l≤p≤r，使得： a[p]⊕a[p+1]⊕…⊕a[N]⊕x 最大，输出最大是多少。

【分析】

考虑异或前缀和。根据异或运算的性质：
$$
a[p]\oplus a[p+1]\oplus …\oplus a[N]\oplus x=s[p-1]\oplus s[N]\oplus x
$$
对于添加操作，序列s很容易维护。对于询问操作，问题变为：已知一个整数val=s[N] xor x，求一个位置p，满足l-1<=p<=r-1，使得s[p] xor val最大。显然可以将s数组插入可持久化Trie中，每次取出在l与r范围内的数据进行贪心（尽量往相反的节点走），从而求出答案。

【代码】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#pragma GCC optimize(3)//QwQ
#include<bits/stdc++.h>
using namespace std;

const int MAXN=600005;
const int DEP=24;

int N,M;
int trie[MAXN*26][2],sum[MAXN*26];
int head[MAXN],cnt=1;
int s[MAXN];

inline void insert(int c,int u,int val,int d){
    sum[u]=sum[c]+1;
    if(d<0) return;
    int x=(val>>d)&1;
    trie[u][!x]=trie[c][!x];
    insert(trie[c][x],trie[u][x]=++cnt,val,d-1);
}

inline int query(int c,int u,int val,int d){
    if(d<0) return 0;
    int x=(val>>d)&1;
    if(sum[trie[u][!x]]>sum[trie[c][!x]])
        return (1<<d)+query(trie[c][!x],trie[u][!x],val,d-1);
    else
        return query(trie[c][x],trie[u][x],val,d-1);
}

int main(){
    scanf("%d%d",&N,&M);
    insert(0,0,0,DEP);
    for(register int i=1;i<=N;++i){
        int a;
        scanf("%d",&a);
        s[i]=s[i-1]^a;
        insert(head[i-1],head[i]=++cnt,s[i],DEP);
    }
    for(register int i=1;i<=M;++i){
        char opt;
        getchar(),opt=getchar();
        if(opt=='A'){
            int a;
            scanf("%d",&a);
            N++;
            s[N]=s[N-1]^a;
            insert(head[N-1],head[N]=++cnt,s[N],DEP);
        }
        else{
            int l,r,a;
            scanf("%d%d%d",&l,&r,&a);
            if(l==r) printf("%d\n",s[l-1]^s[N]^a);
            else printf("%d\n",query(head[l-2],head[r-1],a^s[N],DEP));
        }
    }
    return 0;
}

可持久化数组

【例题】【模板】可持久化数组 luogu-p3919

如题，你需要维护这样的一个长度为 N 的数组，支持如下几种操作

  1. 在某个历史版本上修改某一个位置上的值
  2. 访问某个历史版本上的某一位置的值

此外，每进行一次操作（对于操作2，即为生成一个完全一样的版本，不作任何改动），就会生成一个新的版本。版本编号即为当前操作的编号（从1开始编号，版本0表示初始状态数组）

【分析】

在原数组上建立线段树，在叶子节点上记录原数组数值。执行完修改操作后，根据可持久化的思想，只需更改一条链上的节点信息；执行完访问操作后，则可以将目前操作的根节点指针指向被查询的历史状态根节点。

【代码】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<bits/stdc++.h>
using namespace std;

const int MAXN=1000005;

struct Node{
    int l,r,val;
}node[MAXN*22+5];

int N,M,cnt;
int a[MAXN],head[MAXN];

inline void build(Node& u,int l,int r){
    if(l==r){
        u.val=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(node[u.l=++cnt],l,mid);
    build(node[u.r=++cnt],mid+1,r);
}

inline void change(Node c,Node& u,int l,int r,int p,int val){
    if(l==r){
        u.val=val;
        return;
    }
    int mid=(l+r)>>1;
    if(p<=mid){
        change(node[c.l],node[u.l=++cnt],l,mid,p,val);
        u.r=c.r;
    }
    else{
        change(node[c.r],node[u.r=++cnt],mid+1,r,p,val);
        u.l=c.l;
    }
}

inline int query(Node u,int l,int r,int p){
    if(l==r) return u.val;
    int mid=(l+r)>>1;
    if(p<=mid) return query(node[u.l],l,mid,p);
    else return query(node[u.r],mid+1,r,p);
}

int main(){
    scanf("%d%d",&N,&M);
    for(register int i=1;i<=N;++i)
        scanf("%d",&a[i]);
    build(node[0],1,N);
    for(register int i=1;i<=M;++i){
        int v,opt,p,val;
        scanf("%d%d",&v,&opt);
        if(opt==1){
            scanf("%d%d",&p,&val);
            change(node[head[v]],node[head[i]=++cnt],1,N,p,val);
        }
        else{
            scanf("%d",&p);
            head[i]=head[v];
            printf("%d\n",query(node[head[i]],1,N,p));
        }
    }
    return 0;
}

可持久化值域线段树（主席树）

【例题】【模板】可持久化线段树 luogu-p3834

给定N个整数构成的序列，将对于指定的闭区间查询其区间内的第K小值。

【分析】

值域有负数出现，考虑离散化。假设离散化后的值域为[1,L]。

在值域上建立线段树，每个节点上存储该值域内有多少个数据。对线段树进行可持久化处理，与上一题可持久化数组实现方式类似。

在查询时，如果一个节点的左子节点上的cnt值小于等于正在查询的K，则问题转化为求左半区间内第K小值；否则，转化为求右半区间内第K-cnt小值。

查询时的操作类似于在值域上的二分，因此复杂度在log级别。

【代码】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<bits/stdc++.h>
using namespace std;
#define id(x) (lower_bound(b+1,b+L+1,a[x])-b)
#define rid(x) (b[x])
const int MAXN=200005;

struct Node{
    int l,r,sum;
}node[MAXN<<6];

int N,M,L,cnt;
int a[MAXN],b[MAXN];
int head[MAXN];

inline void build(Node u,int l,int r){
    u.sum=0;
    if(l==r) return;
    int mid=(l+r)>>1;
    build(node[u.l=++cnt],l,mid);
    build(node[u.r=++cnt],mid+1,r);
}

inline void insert(Node c,Node& u,int l,int r,int p){
    u.sum=c.sum+1;
    if(l==r) return;
    int mid=(l+r)>>1;
    if(p<=mid) insert(node[c.l],node[u.l=++cnt],1,mid,p),u.r=c.r;
    else insert(node[c.r],node[u.r=++cnt],mid+1,r,p),u.l=c.l;
}

inline int query(Node c,Node u,int l,int r,int k){
    if(l==r) return l;
    int sum=node[u.l].sum-node[c.l].sum,mid=(l+r)>>1;
    if(sum>=k) return query(node[c.l],node[u.l],1,mid,k);
    else return query(node[c.r],node[u.r],mid+1,r,k-sum);
}

int main(){
    scanf("%d%d",&N,&M);
    for(register int i=1;i<=N;++i){
        scanf("%d",&a[i]);
        b[i]=a[i];
    }
    sort(b+1,b+N+1);
    L=unique(b+1,b+N+1)-(b+1);
    head[0]=0;
    build(node[0],1,L);
    for(register int i=1;i<=N;++i)
        insert(node[head[i-1]],node[head[i]=++cnt],1,L,id(i));
    for(register int i=1;i<=M;++i){
        int l,r,k;
        scanf("%d%d%d",&l,&r,&k);
        printf("%d\n",rid(query(node[head[l-1]],node[head[r]],1,L,k)));
    }
    return 0;
}
# 主席树, 可持久化trie, 数据结构, 线段树
公告 2019-04-08
题解-luogu-p4516潜入行动

Comments

Follow

一言（ヒトコト）


    2333



Recent

Categories

Tag Cloud

0/1分数规划 2-SAT FFT/NTT KMP Pólya计数 ST算法 bitset dfs序 python set 主席树 乘法逆元 二分图 二分图匹配 二分答案 二叉堆 二维偏序 倍增 分块 前缀和 动态点分治 动态规划 单调队列 博弈论 卡特兰数 可持久化trie 后缀自动机 启发式合并 哈希(hash) 堆 复杂度分析 多项式 字符串 容斥原理 差分 差分约束系统 平衡树 异或 强连通分量 排序 搜索 数学 数学期望 数据结构 数论 最小割 最短路 最短路树 最近公共祖先 构造 栈 树上前缀和 树上差分 树套树 树形dp 树状数组 树链剖分 概率 欧拉函数 欧拉路 点分治 状态压缩 生成函数 生成树 矩阵 离散化 素数 线性基 线段树 组合数 组合计数 网络流 群论 背包 虚树 行列式 计数dp 计算几何 贪心 费用流 逆元 高斯消元
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×