[原创]数据结构 [未完成 待续~待修改]

2016-08-08 08:35:28 Tabris_ 阅读数：765

博客爬取于2020-06-14 22:39:15
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/52148588

##并查集

简单并查集

算法讲义

1
不需要模板

带权并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int pre[N];
int findi(int x){
    if(pre[x]==x) return x;
    int r = findi(pre[x]);
    /**
	省略了权值间关系转化,具体视情况而定
	*/
    pre[x]=r;
    return r;
}
void join(int x,int y,int X,int Y){
    int fx = findi(x),fy = findi(y);
    pre[fx]=fy;
    /**
	省略了权值间关系转化,具体视情况而定
	*/
    return ;
}

并查集(可拆点)

代码实现

可以明确的是,对于一个并查集来说,合并操作是不可逆的,即两个元素处在同一个集合下,那么就不能将两者拆开否则会产生错误.那么问题来了
问:如果一个节点的关系发生改变了怎么办呢?
答:如果要改变节点a的关系重新创建一个节点p表示节点a,原先的节点a就不要了,通过一个映射,映射过去就行了(map[a]=p)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int pre[N],h[N],hh;
int findi(int x){
    if(pre[x]==x) return x;
    int r = findi(pre[x]);
    pre[x]=r;
    return r;
}
void join(int x,int y,int X,int Y){
    int fx = findi(x),fy = findi(y);
    pre[fx]=fy;
    return ;
}
void creat(int now){
    h[now]=++hh;
    pre[hh]=hh;
}

可持久化并查集

可持久化数据结构就是可以访问历史版本的数据结构，能修改之后还能查询之前的状态就是可持久化。

现在还没有学明白，会更新上的。

树状数组（Tree array）

详解戳这里<<—
这里有最详细的树状数组各种操作的模板
注意:一定要仔细看数据范围 如果是从0开始的 那么在树状数组中一定要加上1然后在操作 因为求和的时候有-1操作 所以不这样就会无限TLE…
1.前缀和
2.[1,n]的最大最小值 ,换句话就还是前缀的东西.
3.区间覆盖的问题 (仅限对区间进行增改值的,更新还是一样查询的时候注意只要getSum(id)就行了)

一维树状数组

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
//切记 在多组数据的题上要清空数组
const int N = 50000 + 5;			//数列的大小
# define lowbit(x)  (x&(-x))			//lowbit操作
int sum[N],cnt;
void update(int index,int val){		//单点更新  （+val）
    for(int i=index;i<=N;i+=lowbit(i)){//i<=N   不能<=cnt<--错了
        sum[i]+=val;
    }
}
int getSum(int index) {				//求解1~index的和
  int ans = 0;
  for (int i = index; i; i -= lowbit(i))
    ans += sum[i];
  return ans;
}

void update(int l,int r,int val){
	update(l,val),update(r+1,-val);
}
int query(int l,int r){
	return getSum(r)-getSum(l-1);
}
/*
一维区间更新（a,b）
update(a,1);
update(b+1,-1);

*/

二维树状数组

原理和一维的一模一样

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
const int N = 1000+5;
# define lowbit(x) (x&-x)
LL sum[N][N];
void update(int xi,int yi,int val){
    for(int i=xi;i<=N;i+=lowbit(i))
        for(int j=yi;j<=N;j+=lowbit(j))
            sum[i][j]+=val;
    return;
}

int getSum(int xi,int yi){
    int ans = 0;
    for(int i=xi;i>0;i-=lowbit(i))
        for(int j=yi;j>0;j-=lowbit(j))
            ans+=sum[i][j];
    return ans ;
}

void update(int x,int y,int X,int Y,int val){
	update(x,y,val);
	update(x,Y+1,-val);
	update(X+1,y,-val);
	update(X+1,Y+1,val);
}

int query(int x,int y,int X,int Y){
	return getSum(X,Y)-getSum(X,y-1)-getSum(x-1,Y)+getSum(x-1,y-1);
}

/*
二维区间更新{(a,b)∣a∈[x,X],b∈[y,Y]}\{(a,b)|a\in[x,X],b\in[y,Y]\}
1.update(x,y,val);
2.update(x,Y+1,-val);
3.update(X+1,y,-val);
4.update(X+1,Y+1,val);
*/

线段树（Segment Tree）

详解戳这里

线段树维护区间和。
---------------------------------------.

Tree
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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
/*
一定要注意数据范围，必要的时候必须用LL。
注意要求，来决定如何更新。
*/
const int N = 100000+5;
struct node
{
	int l,r; //节点的区间
	int val; //节点的值
    int lazy;//lazy_tag标记， 区间更新的时候用的
    int m(){return (l+r)>>1;}
    int len(){return r-l+1;}
}tree[N<<2]; //数组要开到四倍啊  这样才不会越界  ，如果超时的话也要看看是不是数组开小了

int cnt,a[N],ans;
bool vis[N];
# define ll  (rt<<1)
# define rr  (rt<<1|1)
# define mid (tree[rt].m())
void pushup(int rt)   //线段树维护值的操作
{
    tree[rt].val=tree[ll].val+tree[rr].val;
}

void build(int rt,int l,int r)//建树
{
    tree[rt].l=l,tree[rt].r=r,tree[rt].lazy=0; //记得区间更新的时候 每次建树 要将lazy_tag标记清0

    if(l==r)
    {
        tree[rt].val=1;
        return ;
    }
    build(ll,l,mid);
    build(rr,mid+1,r);
    pushup(rt);
}

void update(int rt,int pos,int val)//单点更新   当前的树的节点  更新的节点  更新的值的变化
{
    if(tree[rt].l==tree[rt].r)//单点更新的时候只要把叶子节点的值更新 剩下的log回溯就行了
    {
        tree[rt].val+=val;
        return;
    }
    if(pos<=mid)  update(ll,pos,val);
    else          update(rr,pos,val);

    pushup(rt);//必须要有的啊 。。
}

void pushdown(int rt) //向下更新的节点。
{
    if(tree[rt].lazy)
    {
        tree[ll].lazy = tree[rr].lazy =tree[rt].lazy ;//根据要求决定如何更新
        tree[ll].val  = tree[ll].len()*tree[rt].lazy ;
        tree[rr].val  = tree[rr].len()*tree[rt].lazy ;
        tree[rt].lazy = 0 ;
    }
    return ;
}

void update(int rt,int L,int R,int val) //区间更新
{
    if(L<=tree[rt].l&&tree[rt].r<=R)
    {
        tree[rt].lazy = val ;
        tree[rt].val  = val*tree[rt].len() ;
        return ;
    }
    pushdown(rt) ;
    if(L<=mid) update(ll,L,R,val) ;
    if(R >mid) update(rr,L,R,val) ;
    pushup(rt) ;
    return ;
}

int query(int rt,int L,int R)//当前查询的树的节点 [L,R]查询的区间
{
    if(L<=tree[rt].l&&tree[rt].r<=R)
		return    tree[rt].val;
    pushdown(rt);//pushdown 操作为区间更新 做的准备。。
	int ans = 0 ;
    if(L<=mid)    ans+=query(ll,L,R);
    if(R >mid)    ans+=query(rr,L,R);
	return ans ;
}

线性变换线段树

所谓线性变换，就是我们的线段树能处理ax+b这种操作。现在线段树的常用操作有add，mul，set无论是哪种我们都可以使用线性变换得到。
add v: 1x+v
mul v：vx+0
set v: 0*x+v

主席树(函数式线段树,可持久化线段树)

主席树(函数式线段树,可持久化线段树)其实就是维护多颗线段树,
每更新一个元素,那么就根据它的上一状态新建一颗线段树,然后就是线段树的操作了,
一般来维护(区间第K大,区间不同元素个数(在线做法))
每次新建一颗线段树,都只是开O(log⁡(n))O(\log(n))的节点,
然后指向前一状态的其他不需要更新的节点,这样的话大大降低了总空间复杂度

主席树的具体维护要看不同情况而定,需要怎么维护就怎么维护即可
主席树一般可以看做维护树与树的前缀和,

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
int rt[N*20];   //表示更新当前元素所形成的不同线段树的树根,
int ls[N*20];   //当前节点的左儿子
int rs[N*20];   //当前节点的右儿子
int sum[N*20];  //主席树节点维护的值
int tot;        //节点的标号

void build(int &rt,int l,int r){ //建树 一般是先建一颗空树(即没有元素更新在其上) 让之后的更新依他开始,
    rt=++tot;
    sum[rt]=0;
    if(l==r) return ;
    int m = (r+l)>>1;
    build(ls[rt],l,m);
    build(rs[rt],m+1,r);
}

void update(int &rt,int l,int r,int last,int pos){
    rt = ++tot;
    ls[rt]=ls[last];
    rs[rt]=rs[last];
    sum[rt]=sum[last]+1;
    if(l==r) return ;
    int m = (r+l)>>1;
    if(pos<=m) update(ls[rt],l,m,ls[last],pos);
    else       update(rs[rt],m+1,r,rs[last],pos);
}

int query(int ss,int tt,int l,int r,int k){
    if(l==r)return l;
    int m = (l+r)>>1;
    int cnt=sum[ls[tt]]-sum[ls[ss]];
    if(k<=cnt) return query(ls[ss],ls[tt],l,m,k);
    else       return query(rs[ss],rs[tt],m+1,r,k-cnt);
}

ST（SparseTable）算法

预处理出ST表 实现O(1)O(1)查询区间最大/小值的算法.(即RMQ问题)
要求数组是静态的(就是不会有元素更改,删除等操作)

ST表其实就是通过倍增的思想,先将一段一段的区间最大/小值处理出来,然后通过O(1)的计算的出所要求的解.

形象一点就是
st[i][j]st[i][j]表示第i个位置开始长度为1<<j1<<j的最大最小值,
在预处理的时候我们就能够倍增的求出每个位置的st[][]的值,st[i][j]=max/min(st[][j−1],st[][j−1]);st[i][j] = max/min(st[][j-1],st[][j-1]);

那么这时候每次查询的[l,r][l,r]就是 因为倍增过来的都是2n2^n长度的.那么就可以找到两个同样长度的区间一个是从ll开始包含ll向后的区间,另一个是从rr开始包含rr向前的区间.取二者的max/minmax/min就可以了.
max/min(st[l][log⁡2(r−l+1)],st[r−log⁡2(r−l+1)+1][log⁡2(r−l+1)])max/min(st[l][\log_{2}{(r-l+1)}],st[r-\log_{2}{(r-l+1)}+1][\log_{2}{(r-l+1)}])

最后一点就是开数组的时候一定是st[N][log⁡(n)]st[N][\log(n)]不要st[N][log⁡(n)]st[N][\log(n)]后者容易超时.

代码实现

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
int st[n][17];
void ST(){
    for(int j=1; (1<<j)<=n; j++)
        for(int i=0; i+(1<<j)-1<n; i++)
            st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}
int getST(int l,int r){
    int k=(int)(log(r-l+1.0)/log(2.0));
    return max(st[l][k],st[r-(1<<k)+1][k]);
}
在求上述的k的时候还有一种线性的预处理的方法,会比取对数快一些,但是有点浪费空间.
void initrmq(int n,int b[]){
    mm[0]=-1;
    for(int i=1;i<=n;i++)
    {
        mm[i]=((i&(i-1))==0)?mm[i-1]+1:mm[i-1];
        dp[i][0]=b[i];
    }
    for(int j=1;j<=mm[n];j++)
        for(int i=1;i+(1<<j)-1<=n;i++)
        dp[i][j]=min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
}
int rmq(int x,int y){
    int k=mm[y-x+1];
    return min(dp[x][k],dp[y-(1<<k)+1][k]);
}

树形结构转化为线形结构

1. dfs序

其实就是从根节点进行搜索，
然后向下dfs遍历树，依次进行编号，
同时能保证子树的编号一定大于父节点的编号，

同时借用两个数组，$L[_],R[_]分别表示这个节点分别表示这个节点u的子树的节点编号在的子树的节点编号在\big(L[u],R[u]\big),开区间$ 内。

这样在进行对子树 进行的操作的时候 可以借助数据结构 对区间进行查找，

1
2
3
4
5
6
7
vector<int >G[N];
int cnt = 0;
void dfs(int u){
    L[u]=cnt++;
    for(int i=0;i<G[u].size();i++) dfs(G[u][i]);
    R[u]=cnt;
}

2. 树链剖分

树链剖分是一种将树形结构转化为线性结构的算法
通过两次树的遍历,将树剖分成一个个的[重链],
且对每个节点进行编号,确保一条链上的节点编号连续
这样一来,我们就能通过一个维护区间关系的数据结构来维护树上,属同一个链上的元素

在维护两个节点(u,v)的时候即:维护两个节点(u,v)间的元素,
我么从深度大的不断向上维护,最后遍历的位置,两个节点一定在一条链上(且深度小的就是LCA(u,v))

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
int dep[N];   //每个节点的深度
int fa[N];    //每个节点的父节点
int sz[N];    //每个节点所有的子节点个数(包括自身)
int son[N];   //每个节点的重儿子
void dfs1(int u,int ff,int deep){
    son[u]=0;fa[u]=ff;sz[u]=1;dep[u]=deep;
    for(int i=head[u];i!=-1;i=G[i].next){
        int v=G[i].to;
        if(v==ff) continue;
        dfs1(v,u,deep+1);
        sz[u]+=sz[v];
        if(sz[v]>sz[son[u]]) son[u]=v; //重儿子子节点个数大
    }
}

int top[N];   //节点所在链上的【根】
int tree[N];  //节点对应在线段树/树状数组的位置
int pre[N];   //在线段树/树状数组的位置对应的节点的标号  (树状数组时一般不需要)
int cnt;      //对链上节点编号
void dfs2(int u,int ff){
    tree[u]=++cnt;pre[tree[u]]=u;top[u]=ff;
    if(son[u]) dfs2(son[u],ff); //先遍历重链
    else return ;
    for(int i=head[u];i!=-1;i=G[i].next){
        int v=G[i].to;
        if(v!=fa[u]&&v!=son[u]) dfs2(v,v);
    }
}

int findi(int x,int y){
    int fx=top[x],fy=top[y];
    int ans = 0;
    while(fx!=fy){
        if(dep[fx]<dep[fy]) myswap(x,y),myswap(fx,fy);
        ans+=getSum(tree[x])-getSum(tree[fx]-1);  //不断向上维护区间
        x=fa[fx],fx=top[x];
    }
    if(dep[x]>dep[y]) myswap(x,y);
    if(x!=y) ans+=getSum(tree[y])-getSum(tree[x]);
    return ans ;
}

平衡树

SPLAY

本质还是一个二叉查找树,但是根据树的旋转,能将一些在某种情况下树退化为单链的时候重新旋转为树
这是最好实现的平衡树了，能够实现求区间翻转，前驱，后继，第K大，查找值，插入，删除，合并，分离 等其他二叉查找树能够做到的功能 and so on
学习SPLAY最终要的是先要理解二叉查找树,然后就要理解好伸展,旋转操作就行了,其他操作原理上和普通二叉查找树是一样的

附下个人的SPLAY模板(Bate 1)

SPLAY操作可以在优化,旋转操作可以在优化,各种功能还没有写

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
int ch[N][2];  //ch[][0] lson ch[][1] rson
int f[N];      //father
int sz[N];     //size
int val[N];    //value
int lazy[N];   //lazy-tag
int rev[N];    //tag of revear
int root;      //root of splay-tree
int tot;       //tot,total,is the number of node of tree

void update_rev(int x){
    if(!x) return ;
    swap(ch[x][0],ch[x][1]);
    rev[x]^=1;
}

void pushdown(int x){
    if(rev[x]){
        update_rev(ch[x][0]);
        update_rev(ch[x][1]);
        rev[x]=0;
    }
}

void pushup(int x){
    sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+1;
}

void rotate(int x,int k){   // k = 0 左旋， k = 1 右旋

    int y=f[x];int z=f[y];
    pushdown(y),pushdown(x);
    ch[y][!k]=ch[x][k];if(ch[x][k])f[ch[x][k]]=y;
    f[x]=z;if(z)ch[z][ch[z][1]==y]=x;
    f[y]=x;ch[x][k]=y;
    pushup(y);
}

void splay(int x,int goal){
    pushdown(x);
    while(f[x]!=goal){
        int y=f[x];int z=f[y];
        if(z==goal){
            pushdown(y),pushdown(x);
            rotate(x,ch[y][0]==x);
        }
        else{
            pushdown(z),pushdown(y),pushdown(x);
            if(ch[z][0]==y){
                if(ch[y][0]==x)rotate(y,1),rotate(x,1);
                else           rotate(x,0),rotate(x,1);
            }
            else{
                if(ch[y][1]==x)rotate(y,0),rotate(x,0);
                else           rotate(x,1),rotate(x,0);
            }
        }
    }
    pushup(x);
    if(goal==0) root=x;
}

void build(int &rt,int l,int r,int fa){
    if(l>r) return ;
    int m = r+l >> 1;
    rt = m;
    f[rt]=fa;
    ch[rt][0]=ch[rt][1]=0;
    sz[rt]=1,rev[rt]=0;
    build(ch[rt][0],l,m-1,rt);
    build(ch[rt][1],m+1,r,rt);
    pushup(rt);
}

void init(int n){
    root=tot=0;
    f[0]=sz[0]=ch[0][0]=ch[0][1]=rev[0]=0;
    build(root,1,n,0);
    pushup(root);
}

SPLAY

由于SPLAY比较长 所以单独开了一贴

帖子在这里