算法模板总结——数据结构

发表于 | 分类于 | 阅读次数:
字数统计: 2,924 字

为省赛整理的常用算法模板，数据结构部分

字符串相关算法

KMP算法

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
int strStr(string s, string p) {
    int len = p.size();
    if(len == 0) return 0;
    // 生成next数组
    vector<int> next(len, 0);
    getNext(next, p);
    // 两个数组的遍历指针
    int i = 0, j = 0;
    while(i < s.size() && j < len)
    {
        if(s[i] == p[j])
        {
            i++;
            j++;
        }
        else
        {
            if(j == 0) i++;
            // 根据next数组中的信息进行重新指向
            else j = next[j];
        }
    }
    return j == len ? i - j : -1;
}
    
void getNext(vector<int> &next, string p)
{
    next[0] = -1;
    // k表示最长前缀后缀的长度
    int k = -1, i = 0;
    // 计算到最后一位
    while(i < p.size() - 1)
    {
        // 相匹配的时候对next数组赋值
        if(k == -1 || p[i] == p[k])
            next[++i] = ++k;
        else
            k = next[k];
    }
}

Manacher算法

求字符串的最大回文子串问题

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
// Manacher 算法
string longestPalindrome(string s) {
    // 添加辅助字符#
    string new_s;
    new_s.push_back('#');
    for(int i = 0; i < s.size(); i++)
    {
        new_s.push_back(s[i]);
        new_s.push_back('#');
    }
    s = new_s;
    int len = s.size();
    if(len == 0) return 0;
    // 回文半径数组
    vector<int> pArr(len, 0);
    // C表示回文中心， R表示回文右边界
    int C = -1, R = -1;
    int maxv = INT_MIN, maxi = 0;
    for(int i = 0; i < len; i++)
    {
        // 在回文右边界里面与否的区分
        // 此时pArr表示的是起码不用验的区域 
        pArr[i] = R > i ? min(pArr[2*C - i], R - i) : 1;
        // 区域没有越界
        while(i + pArr[i] < len && i - pArr[i] > -1)
        {
            // 情况1+4 扩充
            if(s[i + pArr[i]] == s[i - pArr[i]])
                pArr[i]++;
            // 情况2+3
            else
                break;
        }
        if(i + pArr[i] > R)
        {
            R = i + pArr[i];
            C = i;
        }
        if(maxv < pArr[i])
        {
            maxv = pArr[i];
            maxi = i;
        }
    }
    string res;
    for(int i = maxi - maxv + 1; i <= maxi + maxv - 1; i++)
        if(s[i] != '#') res.push_back(s[i]);
    return res;
}

并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int par[maxn];

void init(int n){
    for(int i=1;i<=n;++i){     //注意数据范围
        par[i]=i;
    }
}

int find(int x){
    if(par[x]==x)
        return x;
    else
        return par[x]=find(par[x]);
}

void unite(int x,int y){
    x=find(x);
    y=find(y);
    if(x==y) return;
    par[x]=y;
}

带权并查集

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
void init()
{
    for(int i=1;i<=SIZE;i++)
    {
        fa[i]=i;
        son[i]=1;
        rm[i]=0;   //初始情况下每个结点下面的结点数目为0
    }
}

int Find(int x)
{
    if(fa[x]==x)
        return fa[x];
    int t=fa[x];
    fa[x]=Find(fa[x]);     //压缩路径
    rm[x]+=rm[t];       //压住的结点数相加
    return fa[x];
}

void Union(int x,int y)  //x放在y上
{
    int fx=Find(x);
    int fy=Find(y);

    if(fx!=fy)
    {
        fa[fx]=fy;
        rm[fx]=son[fy];    //加上的结点压住的结点数目刚好是y结点的子结点数目
        son[fy]+=son[fx];   //更新子结点的数目
    }
}

树状数组

解决查询区间和线段树类似可解的问题，注意数组从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
29
30
31
32
33
34
35
36
37
int N,c[maxn+1];    //树状数组

int lowbit(int i)
{
	return i&(-i);   //得到最高位1以后的剩下的数的二进制数
}

//修改节点操作（添加值）
void add(int i,int value)  //i表示序号
{
   i++;
	while(i<=N)
	{
		c[i]+=value;
		i+=lowbit(i);
	}
}

// 初始化
void init()
{
    for(int i=0; i<N; i++)
        add(i, t[i])
}

//求和操作
int sum(int i)
{
   i++;
	int sum=0;
	while(i>0)
	{
		sum+=c[i];
		i-=lowbit(i);
	}
	return sum;
}

左偏树

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
int merge(int r1,int r2)  //合并操作，所有左偏树的基础
{
    if(r1==0)return r2;
    if(r2==0)return r1;
    if(heap[r2].val>heap[r1].val)swab(r1,r2);
    heap[r1].r=merge(heap[r1].r,r2);   
    heap[heap[r1].r].par=r1;  //向下进行合并

    if(heap[heap[r1].l].dis
        swap(heap[r1].l,heap[r2].r);     //回溯保证左偏树的性质
    else
        heap[r1].dis=heap[heap[r1].r].dis+1;    //距离值进行更新
    return r1;
}

int push(int x,int y) // 将y插入x左偏树中
{
    return merge(x,y);
}

int pop(int &x) //在左偏树中删除x
{
    int l=heap[x].l;
    int r=heap[x].r;
    //heap[l].par=l;
    //heap[r].par=r;
    //heap[x].l=heap[x].r=heap[x].dis=0;
    merge(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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int maxn=20000;

int MAX[max<<2];  //开四倍的空间
int MIN[max<<2];
int SUM[max<<2];

void PushUP(int rt)  //向下更新
{
	MAX[rt]=max(MAX[rt<<1],MAX[rt<<1|1]);
	MIN[rt]=min(MIN[rt<<1],MIN[rt<<1|1]);
	SUM[rt]=SUM[rt<<1]+SUM[rt<<1|1];
}

void build(int l,int r,int ru)  //建立线段树
{
	if(l==r)
	{
		int x;
		scanf("%d",&x);
		MAX[rt]=MIN[rt]=SUM[rt]=x;
		return;		
	}
	int m=(r+l)>>1;
	build(lson);
	build(rson);
	PushUP(rt);   //递归建立两个子树以后更新当前结点维护的线段值
}

void update(int p,int tem,int l,int r,int rt)   //实现单点替换
{
	if(l==r)
	{
		MAX[rt]=MIN[rt]=SUM[rt]=tem; //tem为替换值
	}
	int m=(r+l)>>1;
	if(p<=m) update(p,tem,lson);
	else update(p,tem,rson);   //找到替换的点
	PushUP(rt);  //替换之后的更新
}

void update1(int p,int add,int l,int r,int rt)  //添加点
{
	if(l==r)
	{
		SUM[rt]+=add;
		return;
	}
	int m=(l+r)>>1;
	if(p<=m) update1(p,add,lson);
	else update1(p,add,rson);  //找到要添加的点
	PushUP(rt);
}

int quety(int L,int R,int l,int r,int rt)    //查找最大值
{
	if(L<=l && r<=R)
	{
		return MAX[rt];
	}
	int m=(l+r)>>1;
	int ret=-1;   //初始值的设置
	if(L<m) ret=max(ret,quety(L,R,lson));  分开查找
	if(R>m) ret=max(ret,quety(L,R,rson));
	return ret;
}

int quety1(int L,int R,int l,int r,int rt)     //查找和
{
	if(L<=l && r<=R)
	{
		return	SUM[rt];
	}
	int m=(l+r)>>1;
	int ret=0;
	if(L<=m) ret+=quety1(L,R,lson);  //左半部分相加
	if(R>m) ret+=quety1(L,R,rson);   //注意等于号只取一次
	return ret;
}

线段树中区间替换和区间增减
lazy思想：对于一个结点进行操作，先记录下来一开始不操作，直到要查询某个结点的值时，再进行更新，查询某一个结点区间时，先对左右结点的值进行更新，再确定具体的值

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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
//区间替换 lazy思想

int lazy[max<<2];
int sum[max<<2];

viod PushUP(int rt)   //有由左右子结点向上更新结点
{
	sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}

void pushdonw(int ln,int rn,int rt)  //确定左右结点维护的区间大小进行向下更新
{
    if(lazy[rt])
    {
        lazy[rt<<1]+=lazy[rt];
        lazy[rt<<1|1]+=lazy[rt];
        sum[rt<<1]+=(ll)ln*lazy[rt];
        sum[rt<<1|1]+=(ll)rn*lazy[rt];
        lazy[rt]=0;
    }
}

void build(int l,int r,int rt)   //建树
{
	lazy[rt]=0;
	if(l==r)
	{
		scanf("%d",&sum[rt]);
		return;
	}
	int m=(l+r)>>1;
	build(lson);
	build(rson);
	PushUP(rt);
}

void update(int L,int R,int c,int l,int r,int rt)  //更新
{
	if(L<=l &&　r<=R)
	{
		lazy[rt]=c;
		sum[rt]=c*(r-l+1);
		return;
	}
	PushDown(rt,r-l+1);   //处理当前结点的懒惰结点
	int m=(l+r)>>1;
	if(L<=m) update(L,R,c,lson);
	if(R>m) update(L,R,c,rson);
	PushUP(rt);
}

ll query(int L,int R,int l,int r,int rt)   //区间查询
{
	if(L<=l && r<=R)
	{
		return sum[rt];
	}
	PushDown(rt,r-l+1);
	int m=(l+r)>>1;
	ll ret=0;
	if(L<=m) ret+= query(L,R,lson);
	if(m
	return ret;
}

//区间增减

ll lazy[max<<2];
ll sum[max<<2];

void PushUP(int rt)   //向上更新
{
	sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}

void pushdonw(int ln,int rn,int rt)  //确定左右结点维护的区间大小进行向下更新
{
    if(lazy[rt])
    {
        lazy[rt<<1]+=lazy[rt];
        lazy[rt<<1|1]+=lazy[rt];
        sum[rt<<1]+=(ll)ln*lazy[rt];
        sum[rt<<1|1]+=(ll)rn*lazy[rt];
        lazy[rt]=0;
    }
}

void build(int l,int r,int rt)   //建树
{
	lazy[rt]=0;
	if(l=r)
	{
		scanf("I64%d",&sum[rt]);
	}
	int m=(l+r)>>1;
	build(lson);
	build(rson);
	PushUp(rt);
}

void update(int L,int R,int c,int l,int r,int rt)  //更新
{
	if(L<=l && r<=R)
	{
		lazy[rt]+=c;
		sum[rt]+=(ll)c*(r-l+1);
		return;
	}
	int m=(l+r)>>1;
	pushdown(m-l+1,r-m,rt);
	if(L<=m) update(L,R,c,lson);
	if(m
	PushUp(rt);
}

ll quety(int L,int R,int l,int r,int rt)  //查询
{
	if(L<=l && r<=R)
	{
		return sum[rt];
	}
	int m=(l+r)>>1;
	pushdown(m-l+1,r-m,rt);
	ll ret=0;
	if(L<=m) ret+=quety(L,R,lson);
	if(m
	return ret;
}

可持续化线段树（主席树）

在普通的线段树的基础上记录了历史版本

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
90
91
92
93
94
95
96
97
98
99
100
101
struct segnode
{
    int lt,rt,lv,rv;     //左右孩子结点的位置，维护的区间值
    ll sum,lazy;      //lazy思想，在查询的时候再进行修改
}tree[maxn<<4];
int cnt,now,a[maxn],root[maxn];
void build(int &id,int l,int r)
{
    tree[++cnt]=tree[id];
    id=cnt;
    tree[id].lv=l;
    tree[id].rv=r;
    if(l==r)
    {
        tree[id].sum=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(tree[id].lt,l,mid);   //引用的妙处
    build(tree[id].rt,mid+1,r);
    tree[id].sum=tree[tree[id].lt].sum+tree[tree[id].rt].sum;
    return;
}
void update(int &id,int l,int r,int v)
{
    tree[++cnt]=tree[id];
    id=cnt;
    tree[id].sum+=(min(r,tree[id].rv)-max(l,tree[id].lv)+1)*v;
    if(l<=tree[id].lv && tree[id].rv<=r)
    {
        if(tree[id].lv!=tree[id].rv)
            tree[id].lazy+=v;
        return;
    }
    int mid=(tree[id].lv+tree[id].rv)>>1;
    if(r<=mid)
        update(tree[id].lt,l,r,v);    //引用的妙用
    else if(l>mid)
        update(tree[id].rt,l,r,v);
    else
    {
        update(tree[id].lt,l,r,v);
        update(tree[id].rt,l,r,v);
    }
}
ll query(int id,int l,int r)
{
    if(l<=tree[id].lv && tree[id].rv<=r)
        return tree[id].sum;
    ll ret=(min(r,tree[id].rv)-max(l,tree[id].lv)+1)*tree[id].lazy;
    int mid=(tree[id].lv+tree[id].rv)>>1;
    if(r<=mid)
        ret+=query(tree[id].lt,l,r);
    else if(l>mid)
        ret+=query(tree[id].rt,l,r);
    else
        ret+=query(tree[id].lt,l,r)+query(tree[id].rt,l,r);
    return ret;
}
void solve()
{
    int n,m,l,r,t,d;
    char op;
    bool hh=0;
    while(scanf("%d %d",&n,&m)!=EOF)
    {
        if(hh)
            printf("\n");
        else
            hh=1;
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        now=cnt=0;
        build(root[0],1,n);
        for(int i=0;i<m;i++)
        {
            scanf(" %c",&op);    //注意前面要加一个空格
            if(op=='C')
            {
                now++; //时间增加
                scanf("%d %d %d",&l,&r,&d);
                update(root[now]=root[now-1],l,r,d);
            }
            if(op=='Q')
            {
                scanf("%d %d",&l,&r);
                printf("%lld\n",query(root[now],l,r));
            }
            if(op=='H')
            {
                scanf("%d %d %d",&l,&r,&t);
                printf("%lld\n",query(root[t],l,r));
            }
            if(op=='B')
            {
                scanf("%d",&now);
                cnt=root[now+1]-1;   //释放结点
            }
        }
    }
}

通过代码我们可以发现，充分利用已有数据生成新的线段树的关键在于生成节点的函数中引用&