数据结构总结

数据结构模块总结归纳

【前言】

临近CSP二轮，做一些总结归纳，就当作是复习吧。加油吧！

【目录】

（注：标*号为重要）

栈
- 单调栈
队列
- 单调队列
- 双端队列
邻接表
*堆
- 对顶堆
- 优先队列
并查集
- 扩展域
- 边带权
- 连通性
树状数组
- 权值树状数组
- 二维树状数组
*线段树
- 多标记下传
- 权值线段树
- 扫描线
- 线段树合并
分块
STL
- set
- vector
- map
题型总结和综合归纳

【栈】

最简单基础的一类数据结构，但是熟练掌握也能玩出朵花来。比如双栈排序之类的。

用途：一般用于一些先入后出的常规操作，如表达式计算、递归、找环等一系列常规操作。

实现：鉴于STL的stack常常爆空间，而且还不如手写快，因此我们更常使用手写栈。

代码就不贴了。

单调栈

【队列】

也是很基础的一个数据结构，适用范围及其广泛，用处花样繁多。

用途：~~太多了。~~比如BFS、各种序列问题、各种数据结构问题。

实现：上界较大时不宜使用STL的queue，不过一般情况下推荐使用，毕竟简洁且不易错。

初学的时候的手写队列BFS：

void bfs(int i,int j)
 {
     int head=0,tail=1;
     q[tail].x=i;q[tail].y=j;
     pre[tail]=tail;
     memset(vis,0,sizeof(vis));
     do
     {
         head++;
         for(int i=0;i<4;i++)
         {
             int nx=q[head].x+dir[i][0];
             int ny=q[head].y+dir[i][1];
             if(nx>0&&nx<=5&&ny>0&&ny<=5&&vis[nx][ny]==0&&a[nx][ny]!=1)
             {
                 tail++;
                 q[tail].x=nx;
                 q[tail].y=ny;
                 pre[tail]=head;
                 vis[nx][ny]=1;
             }
             if(nx==5&&ny==5){print(tail);return;}
         }
     }while(head<tail);
 }

STL的队列不再赘述。

单调队列

好东西，可以优化dp。

【邻接表】

很有意思的一个数据结构，设计精巧（至少我是这么认为的）。

用途：大概除了存图也没什么别的大用了。

实现：OI还是不推荐使用指针，毕竟容易瞎，难调试。个人也比较喜欢数组模拟指针。

可以看作多个有代表元的数组的集合，从表头开始，使用指针指向下一个元素。

下面代码实现中，(head[x])为一个以(x)为代表元的表头，每个元素拥有一个指针指向它的下一个元素。

const int N=100010;
struct rec{
	int next,ver,edge;
}g[N<<1];
int head[N],tot;
inline void add(int x,int y)
{
	g[++tot].ver=y;
	g[tot].next=head[x],head[x]=tot;
}

【并查集】

总之，是一个非常好玩、用途广泛的数据结构。

用途：维护二元关系、维护连通性、维护其它数据结构（但是不讲~~其实是我没学~~）等。

原理：实质上，并查集维护的是一组集合。每个元素有一个tag，表示它所在的集合。我们在每个集合中选出一个代表元来作为这个tag，便于维护。并查集包括合并、查找两个操作，意为合并两个不相交集合、查找一个元素所在集合，这也是为什么它叫并查集。

实现：

初始化

初始化时，我们把每个元素的代表元设为自己。

const int N=100010;
int fa[N];
for(int i=1;i<=N;++i) fa[i]=i;

查找

int get(int x)
{
    if(x==fa[x]) return x;
    get(fa[x]);
}

合并

void Union(int x,int y){
    x=get(x),y=get(y);
    fa[x]=y;
}

路径压缩

容易发现上面那个查找算法对一条链会退化得很厉害。我们可以路径压缩，即让一个集合中得所有元素都指向同一个代表元，而不是指向它的父亲。时间复杂度(O(nlogn))，空间复杂度(O(n))。

int get(int x)
{
    return x==fa[x]?x:fa[x]=get(fa[x]);
}

启发式合并

不多讲，因为不常用。主要思路就是以合并时集合元素数量作为(h(x))函数，启发式合并。具体实现其实差不了多少。

连通性

并查集还可以做一些图论有关连通性的题，~~吊打Tarjan~~。

用途：找环、判断联通性等。

最好的例子就是最小生成树了。

扩展域

用途：维护二元关系。

原理：这里涉及到必修五的知识（雾，没学过可以去看一下必修五第一章逻辑用语。主要维护充要条件，大致意思是可以相互推导的关系。我们将并查集分为多个“域”，可以理解做不同种的逻辑命题，当我们合并不同域的集合的某两个元素(p,q)时，我们可以理解作(pLeftrightarrow q)。

这些关系具有传递性，意即若(pLeftrightarrow q,qLeftrightarrow r)，则有(pLeftrightarrow r)。因此，我们不妨把一个命题看作一个点，这种关系看作维护点与点之间的联通性，这就转换为了一个并查集可做的问题了。

实现：

拿一道例题吧，不然讲不清楚。

P1525 关押罪犯

题解

边带权

用途：动态统计链长、环长等。

原理：很简单，说白了就是动态统计集合元素数量。

实现：

看一道例题P1197 星球大战

题解

【堆】

很好用的辅助数据结构，很多问题可以借助堆优化。

用途：动态维护第(k)小，维护最小/大值。

原理：一句话，上小下大（小根堆）/上大下小（大根堆）。

实现：一般使用STL的优先队列，不排除卡常毒瘤题要求手写堆。

priority_queue<data_type> queue[N];

手写堆（搬的）：

int n,m,y,ans,t; 
int tree[2000003];
void change(int a,int b)
{
    int temp=tree[a];
    tree[a]=tree[b];
    tree[b]=temp;
}
void insert(int x)
{
    int d,f=0;//作为判断新加入的节点与其根节点大小的标志 
    while(x!=1&&f==0)//边界条件 
    {
        if(tree[x/2]>tree[x])//新节点小于根节点则交换值 
        {
            d=x/2;
            change(x,d);
        }
        else f=1;//新节点大于根节点则不发生改变 
        x=x/2;//继续查找下一个根节点（大概是爷爷节点吧（雾）是否小于该新节点，不是则继续查找，直到下一个根节点值小于该新节点 
    }
}
void del(int x)//将tree[n]放在tree[1]不满足小根堆的性质，所以要进行调整 
{
    int d=x,f=0;
    while(x*2<=t&&f==0)//边界条件
    {
        if(tree[x]>tree[x*2]&&x*2<=t)
        {
            d=x*2;
        }
        if(tree[x]>tree[x*2+1]&&tree[x*2+1]<tree[x*2]&&x*2+1<=t) 
        {
            d=x*2+1;
        }
        if(x!=d)
        {
            change(x,d);
            x=d;
        }
        else f=1;
    } 
}
————————————————
版权声明：本文为CSDN博主「MerakAngel」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/MerakAngel/article/details/75434737

对顶堆

用途：动态维护第(k)小。

原理：对于一个序列(a[1sim n])，建立一个大根堆一个小根堆，大根堆维护(ksim n)大值，小根堆维护(1sim k-1)大值。

【树状数组】

常数小，又好写，能用尽量用吧，虽然可扩展性差，但省事。

用途：解决一系列区间问题、二维区间问题、奇奇怪怪的数据结构问题。维护前缀和、二维偏序之类。

原理：

基于二进制划分。首先定义(lowbit(x)) 运算，含义是正整数(x)二进制表示下最低位的1表示的十进制数。

举个例子：(lowbit(5)=1)，((3)_{10}=(101)_2)。(lowbit(12)=4)，((12)_{10}=(1100)_2)。

关于(lowbit(x))的实现，我们可以利用计算机的补码来做。比如((1100)_2)取反之后变成((0011)_2)，加1之后与上(x)就是(lowbit(x))了，这个操作正好是补码的操作。所以，(lowbit(x)=x&-x)。

树状数组将(1sim n)这个区间划分为若干个以2的次幂为长度的小区间。对于任意位置(i)，它维护一个长度为(lowbit(i))的区间，即(i-lowbit(i)+1sim i)这个区间的和。

时间复杂度为(O(nlogn))，空间复杂度(O(n))。

由于树状数组只能维护关于前缀和的信息，所以这些信息必须满足前缀和可减性。

实现：

单点修改

void add(int x,int y)
{
    for(;x<=N;x+=x&-x) c[x]+=y;
}

单点查询

int ask(int x)
{
    int ans=0;
    for(;x;x-=x&-x) ans+=c[x];
    return ans;
}

区间修改+单点查询

由于树状数组只能做单点修改，所以区间修改要用到差分。

int d[N];
void add(int x,int y)
{
    for(;x<=N;x+=x&-x) d[x]+=y;
}
int ask(int x)
{
    int ans=0;
    for(;x;x-=x&-x) ans+=d[x];
    return ans;
}
int main()
{
    //do something
        
    add(l,1),add(r,-1);//区间修改
    
    //do something
        
    cout<<ask(pos)<<endl;//pos为单点询问位置
}

区间修改+区间查询

对于(1sim n)的前缀和，我们要维护这样一个东西

[sum_{i=1}^nsum_{k=1}^i d[k] ]

考察(d[k])出现的次数，(d[1])出现(n)次，(d[2])出现(n-1)次，(d[k])就出现(n-k+1)次。

所以我们要维护的东西变成

[sum_{k=1}^n (n-k+1)*d[k] ]

所以维护(d[k]*k,d[k])两个东西即可。

void add(int x,int y)
{
    for(int i=x;i<=N;i+=i&-i) c1[i]+=y,c2[i]+=x*y;
}
int ask1()
{
    int ans=0;
    for(int i=x;i<=N;i+=i&-i) ans+=c1[x];
    return ans;
}
int ask2()
{
    int ans=0;
    for(int i=x;i<=N;i+=i&-i) ans+=c2[x];
    return ans;
}
int main()
{
    //do something
        
    add(l,1),add(r,-1);//区间修改
    
    //do something
        
    cout<<ask2(pos)-r*ask1(pos)<<endl;//pos为单点询问位置
}

二维树状数组

单点查询+区间修改

不再赘述

int c[N][N],n;
inline void add(int x,int y,int val)
{
    for(;x<=n;x+=x&-x)
     for(int j=y;j<=n;j+=j&-j) c[x][j]+=val;
}
inline int ask(int x,int y)//请不要在意这个鬼畜的二维树状数组
{
    int ans=0;
    for(;x;x-=x&-x)
     for(int j=y;j;j-=j&-j) ans+=c[x][j];
    return ans;
}
inline void change(int x1,int y1,int x2,int y2)//要修改的左上角、右下角
{
    add(x1,y1,1),add(x1,y2+1,-1),add(x2+1,y1,-1),add(x2+1,y2+1,1);
}

区间查询+区间修改

维护这个式子

[sum_{i=1}^nsum_{j=1}^msum_{k=1}^isum_{p=1}^j d[k][p] ]

仍然是考察(d[k][p])出现多少次，(d[1][1])出现(n*m)次，(d[1][2])出现(n*(m-1))，(d[2][1])出现((n-1)*m)次，(d[k][p])出现((n-k+1)*(m-p+1))次。所以我们维护这个式子

[sum_{k=1}^isum_{p=1}^j (n-k+1)*(m-p+1)*d[k][p] ]

整理得

[sum_{k=1}^isum_{p=1}^j (n-k+1)*(m-p+1)*d[k][p]\ =sum_{k=1}^isum_{p=1}^j ((n+1)*(m+1)*d[k][p]-k*(m+1)*d[k][p]-p*(n+1)*d[k][p]+k*p*d[k][p]) ]

维护四个东西(d[p][k],k*d[k][p],p*d[k][p],k*p*d[k][p])。

代码没写，摘自胡小兔的博客

#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long ll;
ll read(){
    char c; bool op = 0;
    while((c = getchar()) < '0' || c > '9')
        if(c == '-') op = 1;
    ll res = c - '0';
    while((c = getchar()) >= '0' && c <= '9')
        res = res * 10 + c - '0';
    return op ? -res : res;
}
const int N = 205;
ll n, m, Q;
ll t1[N][N], t2[N][N], t3[N][N], t4[N][N];
void add(ll x, ll y, ll z){
    for(int X = x; X <= n; X += X & -X)
        for(int Y = y; Y <= m; Y += Y & -Y){
            t1[X][Y] += z;
            t2[X][Y] += z * x;
            t3[X][Y] += z * y;
            t4[X][Y] += z * x * y;
        }
}
void range_add(ll xa, ll ya, ll xb, ll yb, ll z){ //(xa, ya) 到 (xb, yb) 的矩形
    add(xa, ya, z);
    add(xa, yb + 1, -z);
    add(xb + 1, ya, -z);
    add(xb + 1, yb + 1, z);
}
ll ask(ll x, ll y){
    ll res = 0;
    for(int i = x; i; i -= i & -i)
        for(int j = y; j; j -= j & -j)
            res += (x + 1) * (y + 1) * t1[i][j]
                - (y + 1) * t2[i][j]
                - (x + 1) * t3[i][j]
                + t4[i][j];
    return res;
}
ll range_ask(ll xa, ll ya, ll xb, ll yb){
    return ask(xb, yb) - ask(xb, ya - 1) - ask(xa - 1, yb) + ask(xa - 1, ya - 1);
}
int main(){
    n = read(), m = read(), Q = read();
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            ll z = read();
            range_add(i, j, i, j, z);
        }
    }
    while(Q--){
        ll ya = read(), xa = read(), yb = read(), xb = read(), z = read(), a = read();
        if(range_ask(xa, ya, xb, yb) < z * (xb - xa + 1) * (yb - ya + 1))
            range_add(xa, ya, xb, yb, a);
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++)
            printf("%lld ", range_ask(i, j, i, j));
        putchar('
');
    }
    return 0;
}

【线段树】

最常用的数据结构，可扩展性强，直观，缺点是常数大、码量大，不过练熟之后还是用处很大的。

用途：解决各种区间问题（基本上除了区间众数）、树剖、优化dp。用于维护满足结合律的信息。

原理：

这里只讲数组下标实现的线段树。

基于完全二叉树和分治思想，将区间（线段）逐层二分为小段，并维护每一小段的信息，主要考虑每层直接的信息传递与推导的具体做法。线段树是递归定义的。

线段树的特征

线段树的每个节点都代表一个区间
线段树具有唯一的根节点，代表的区间是整个统计范围。
线段树的每个叶节点都代表一个长度为(1)的元区间。
对于每个内部节点([l,r])，它的左子节点是([l,mid]),右子节点是([mid+1,r])，其中(mid=(l+r)/2(floor));

下面以加法操作为例，实现了一个单标记线段树。

建树

#define LL long long
void build(LL p,LL l,LL r)
{
	t[p].l=l;t[p].r=r;
	if(l==r){
		t[p].sum=a[l];//前提题目有需求初始化数列，否则空线段树无需sum值
		return;
	}
	LL mid=(l+r)>>1;
	built(p<<1,l,mid);
	built((p<<1)|1,mid+1,r);
	t[p].sum=t[p<<1].sum+t[(p<<1)|1].sum;
}

区间修改

void change(LL p,LL l,LL r,LL k)
{
	if(l<=t[p].l&&t[p].r<=r){
		t[p].sum+=k*(t[p].r-t[p].l+1);
		return;
	}
    spread(p);
	LL mid=(t[p].l+t[p].r)>>1;
	if(l<=mid) change(p<<1,l,r,k);
	if(r>mid) change((p<<1)|1,l,r,k);
	t[p].sum=t[p<<1].sum+t[(p<<1)|1].sum;
}

区间查询

LL ask(LL p,LL l,LL r)
{
	if(l<=t[p].l&&t[p].r<=r) return t[p].sum;
    spread(p);
	LL mid=(t[p].l+t[p].r)>>1;
	LL val=0;
	if(l<=mid) val+=ask(p<<1,l,r);
	if(r>mid) val+=ask((p<<1)|1,l,r);
	return val;
}

标记下传

void spread(LL p)
{
	if(t[p].add){
		t[(p<<1)|1].sum+=t[p].add*(t[(p<<1)|1].r-t[(p<<1)|1].l+1);
		t[p<<1].sum+=t[p].add*(t[p<<1].r-t[p<<1].l+1);
		t[(p<<1)|1].add+=t[p].add;
		t[p<<1].add+=t[p].add;
		t[p].add=0;
	}
}