学习笔记-数据结构

YGBC_ · 2025-11-27 07:26:11 · 算法·理论

数据结构

真的非常非常重要。计算机科学等于算法（Algorithm）加数据结构（Data Structure）。

基础数据结构

1. 栈

蒟蒻学的第一个数据结构。

特点，先进先出，只有栈顶可以访问。

下面给出模板题 B3614 的代码。

STL 实现（优点：好写，维护成本低。缺点：常数大，容易报错）：

#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;

int T;

void solve()
{
    stack<ull> st;
    int N; cin>>N;
    while(N--){
        string s; cin>>s;
        if(s=="push"){
            ull x; cin>>x;
            st.push(x);
        }
        if(s=="pop"){
            if(st.empty()) cout<<"Empty\n";
            else st.pop();
        }
        if(s=="query"){
            if(st.empty()) cout<<"Anguei!\n";
            else cout<<st.top()<<'\n';
        }
        if(s=="size"){
            cout<<st.size()<<'\n';
        }
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>T;
    while(T--) solve();
}

手写实现（优点：常数小，自定义程度高，缺点：难以维护）：

#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;

class Stack{
    private:
        ull st[1000005], top;
    public:
        void init(){
            top=0;
        }
        inline void push(ull x){
            st[++top]=x;
        }
        inline void pop(){
            if(top) top--;
            else cout<<"Empty\n";
        }
        inline ull query(){
            if(top) return st[top];
            cout<<"Anguei!\n";
            return -1;
        }
        inline ull size(){
            return top;
        }
        inline bool empty(){
            return top==0;
        }
}S;

int T;

void solve()
{
    S.init();
    int N; cin>>N;
    while(N--){
        string s; cin>>s;
        if(s=="push"){
            ull x; cin>>x;
            S.push(x);
        }
        if(s=="pop"){
            S.pop();
        }
        if(s=="query"){
            ull x=S.query();
            if(~x) cout<<x<<'\n';
        }
        if(s=="size"){
            cout<<S.size()<<'\n';
        } 
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>T;
    while(T--) solve();
}

2. 队列

先进后出表，和栈一样运用广泛。

STL 实现：

#include<bits/stdc++.h>
using namespace std;

int N;
queue<int> q;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>N;
    while(N--){
        int op; cin>>op;
        if(op==1){
            int x; cin>>x;
            q.push(x);
        }
        if(op==2){
            if(q.empty()) cout<<"ERR_CANNOT_POP\n";
            else q.pop();
        }
        if(op==3){
            if(q.empty()) cout<<"ERR_CANNOT_QUERY\n";
            else cout<<q.front()<<'\n';
        }
        if(op==4){
            cout<<q.size()<<'\n';
        }
    }
}

手写实现：

#include<bits/stdc++.h>
using namespace std;

class Queue{
    private:
        int q[10005],l=0,r=-1;
    public:
        void init(){
            l=0,r=-1;
        }
        inline void push(int x){
            q[++r]=x;
        }
        inline void pop(){
            if(l>r) cout<<"ERR_CANNOT_POP\n";
            else l++;
        }
        inline int query(){
            if(l>r){
                cout<<"ERR_CANNOT_QUERY\n";
                return -1;
            } 
            return q[l];
        }
        inline int size(){
            return r-l+1;
        }
        inline bool empty(){
            return l>r;
        }
}Q;

int N;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>N;
    while(N--){
        int op; cin>>op;
        if(op==1){
            int x; cin>>x;
            Q.push(x);
        }
        if(op==2){
            Q.pop();
        } 
        if(op==3){
            int x=Q.query();
            if(~x) cout<<x<<'\n';
        }
        if(op==4){
            cout<<Q.size()<<'\n';
        }
    }
}

3. 链表

通过记录每一个节点的前驱和后继实现 O(1) 插入，O(n)遍历。

码略。

4. 二叉堆（优先队列）

通过对二叉树节点的上浮和下沉实现每次顶端都是最值。

插入，删除都是 O(\log n)，查询堆顶是 O(1) 的。

一般用优先队列（std::priority_queue）实现，代码如下：

#include<bits/stdc++.h>
using namespace std;

int N;
priority_queue<int,vector<int>,greater<int>> q;

int main()
{
    cin>>N;
    while(N--){
        int op; cin>>op;
        if(op==1){
            int x; cin>>x;
            q.push(x);
        } 
        if(op==2) cout<<q.top()<<'\n';
        if(op==3) q.pop();
    }

}

高级数据结构

1. 并查集

1.1. 并查集

用于解决集合合并，查询两元素是否在一个集合。

模板代码：

#include<bits/stdc++.h>
using namespace std;

int N,M;

namespace DSU
{

int fa[200005];

void init(){
    for(int i=1;i<=N;i++) fa[i]=i;
}
int find(int x){
    if(fa[x]==x) return x;
    return fa[x]=find(fa[x]);
}
void merge(int x,int y){
    int fx=find(x), fy=find(y);
    if(fx==fy) return ;
    fa[fx]=fy;
}

}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>N>>M;
    DSU::init();
    while(M--){
        int z,x,y; cin>>z>>x>>y;
        if(z==1) DSU::merge(x,y);
        if(z==2){
            int fx=DSU::find(x), fy=DSU::find(y);
            if(fx==fy) cout<<"Y\n";
            else cout<<"N\n"; 
        } 
    }
}

1.2. 扩展域并查集

通过对元素拓展多个域进行合并，解决朋友，敌人，捕食等多种复杂关系。

P1892 代码：

#include<bits/stdc++.h>
using namespace std;

int N,M,P;
int fa[2005];

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

int main()
{
    cin>>N>>M;
    for(int i=1;i<=2*N;i++) fa[i]=i;
    for(int i=1;i<=M;i++){
        char ch;
        int x,y;
        cin>>ch>>x>>y;
        if(ch=='F') fa[find(y)]=find(x);
        else{
            fa[find(N+x)]=find(y);
            fa[find(N+y)]=find(x);
        }
    }
    for(int i=1;i<=N;i++){
        if(fa[i]==i) P++;
    }
    cout<<P;
    return 0;
} 

1.3. 带权并查集

记录自己与父亲节点的边权，以处理更复杂的关系。

扩展域并查集与带权并查集的适用范围差不多。

P2024 代码：

#include<bits/stdc++.h>
using namespace std;

int N,k;
int res;
int fa[100005],d[100005];

int find(int x){
    if(fa[x]!=x){
        int f=fa[x];
        fa[x]=find(fa[x]);
        d[x]=(d[x]+d[f])%3;
    }
    return fa[x];
}

void merge(int x,int y,int w){
    int fx=find(x), fy=find(y);
    if(fx==fy){
        if(((d[x]-d[y]+3)%3)!=w-1) res++;
    }
    else{
        fa[fx]=fy;
        d[fx]=(d[y]-d[x]+w+2)%3;
    }
}

int main()
{
    cin>>N>>k;
    for(int i=1;i<=N;i++) fa[i]=i;

    while(k--){
        int w,x,y; cin>>w>>x>>y;
        if(x>N||y>N||x==y&&w==2) res++;
        else merge(x,y,w);
    }

    cout<<res;
}

2. 树状数组

2.1. 单点修改&区间查询

模板题 P3374 代码：

#include<bits/stdc++.h>
using namespace std;

int N,M;
int a[500005];

inline int lowbit(int x){
    return x&-x;
}

class Tree{
    private:
        int t[500005];
        void update(int p,int x){
            while(p<=N){
                t[p]+=x;
                p+=lowbit(p);
            }
        }
        int get_sum(int p){
            int res=0;
            while(p){
                res+=t[p];
                p-=lowbit(p);
            }
            return res;
        }
    public:
        void modify(int p,int x){
            update(p,x);
        }
        int query(int l,int r){
            return get_sum(r)-get_sum(l-1);
        }
}T; 

int main()
{
    cin>>N>>M;
    for(int i=1;i<=N;i++){
        cin>>a[i];
        T.modify(i,a[i]);
    }
    while(M--){
        int op,x,y; cin>>op>>x>>y;
        if(op==1) T.modify(x,y);
        if(op==2) cout<<T.query(x,y)<<'\n';
    }
}

2.2. 区间修改&单点查询

维护差分数组即可，略。

2.3 区间修改&区间查询

维护两个差分数组。像这样的操作通常用线段树维护，代码略。

3 线段树

直接给出超级线段树代码：

#include<bits/stdc++.h>
using namespace std;

int N;
int a[100005];

namespace SGT{

struct Node{
    int l,r;
    int dat;
    int maxn,minn;
    int add,mul;
    int ass;
};

class Tree{

#define int long long
#define ls i<<1
#define rs i<<1|1

    private:
        Node t[400005];
        void push_up(int i){
            t[i].dat=t[ls].dat+t[rs].dat;
            t[i].maxn=max(t[ls].maxn,t[rs].maxn);
            t[i].minn=max(t[ls].minn,t[rs].minn);
        }
        void tag_add(int i,int x){
            t[i].add+=x;
            t[i].dat+=(t[i].r-t[i].l+1)*x;
            t[i].maxn+=x, t[i].minn+=x;
        }
        void tag_mul(int i,int x){
            t[i].mul*=x, t[i].add*=x;
            t[i].dat*=x, t[i].maxn*=x, t[i].minn*=x;
        }
        void tag_ass(int i,int x){
            t[i].add=0, t[i].mul=1;
            t[i].ass=x;
            t[i].dat=(t[i].r-t[i].l+1)*x;
            t[i].maxn=t[i].minn=x;
        }
        void push_down(int i){
            if(t[i].ass!=-1){
                tag_ass(ls,t[i].ass);
                tag_ass(rs,t[i].ass); 
                t[i].ass=-1;
            }
            if(t[i].mul){
                tag_mul(ls,t[i].mul);
                tag_mul(rs,t[i].mul); 
                t[i].mul=1;
            }
            if(t[i].add){
                tag_add(ls,t[i].add);
                tag_add(rs,t[i].add); 
                t[i].add=0;
            }
        }
        void build(int i,int L,int R,int a[]){
            t[i].l=t[i].r=0, t[i].add=0, t[i].mul=1;
            if(L<=t[i].l&&t[i].r<=R){
                t[i].dat=t[i].maxn=t[i].minn=a[L];
                return ;
            }
            int Mid=L+R>>1;
            build(ls,L,Mid,a);
            build(rs,Mid+1,R,a);
            push_up(i);
        }
        void update_add(int i,int L,int R,int x){
            if(L<=t[i].l&&t[i].r<=R){
                tag_add(i,x);
                return ;
            }
            int mid=t[i].l+t[i].r>>1;
            push_down(i);
            if(L<=mid) update_add(ls,L,R,x);
            if(mid<R) update_add(rs,L,R,x);
            push_up(i);
        }
        void update_mul(int i,int L,int R,int x){
            if(L<=t[i].l&&t[i].r<=R){
                tag_mul(i,x);
                return ;
            }
            int mid=t[i].l+t[i].r>>1;
            push_down(i);
            if(L<=mid) update_mul(ls,L,R,x);
            if(mid<R) update_mul(rs,L,R,x);
            push_up(i);
        }
        void update_ass(int i,int L,int R,int x){
            if(L<=t[i].l&&t[i].r<=R){
                tag_ass(i,x);
                return ;
            }
            int mid=t[i].l+t[i].r>>1;
            push_down(i);
            if(L<=mid) update_ass(ls,L,R,x);
            if(mid<R) update_ass(rs,L,R,x);
            push_up(i);
        }
        int get_sum(int i,int L,int R){
            if(L<=t[i].l&&t[i].r<=R) return t[i].dat;
            int mid=t[i].l+t[i].r>>1, res=0;
            push_down(i);
            if(L<=mid) res+=get_sum(ls,L,R);
            if(mid<R) res+=get_sum(rs,L,R);
        }
        int get_max(int i,int L,int R){
            if(L<=t[i].l&&t[i].r<=R) return t[i].maxn;
            int mid=t[i].l+t[i].r>>1, res=0;
            push_down(i);
            if(L<=mid) res=max(res,get_max(ls,L,R));
            if(mid<R) res=max(res,get_max(rs,L,R));
        }
        int get_min(int i,int L,int R){
            if(L<=t[i].l&&t[i].r<=R) return t[i].minn;
            int mid=t[i].l+t[i].r>>1, res=1e18;
            push_down(i);
            if(L<=mid) res=min(res,get_min(ls,L,R));
            if(mid<R) res=min(res,get_min(rs,L,R));
        }

    public:
        void init(int a[]){
            build(1,1,N,a);
        }
        void modify(int op,int L,int R,int x){
            if(op==1) update_add(1,L,R,x);
            if(op==2) update_mul(1,L,R,x);
            if(op==3) update_ass(1,L,R,x);
        }
        int query_sum(int L,int R){
            return get_sum(1,L,R);
        }
        int query_max(int L,int R){
            return get_max(1,L,R);
        }
        int query_min(int L,int R){
            return get_min(1,L,R);
        }

#undef int
#undef ls
#undef rs

};

}

int main()
{

}

4. 分块

4.1 基础分块

数列分块入门 1 代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;

int N;
int a[300005];
int tag[1005];
int B[300005],L[1005],R[1005];

void build(){
    int Bl=sqrt(N);
    int l=1,r=Bl,cnt=1;
    while(true){
        bool flag=0;
        if(r>N) r=N, flag=1;
        L[cnt]=l, R[cnt]=r;
        for(int i=l;i<=r;i++) B[i]=cnt;
        if(flag) break;
        l+=Bl, r+=Bl, cnt++;
    }
}

void modify(int l,int r,int c){
    int lb=B[l], rb=B[r];
    if(lb==rb){
        for(int i=l;i<=r;i++) a[i]+=c;
        return ;
    }
    for(int i=l;i<=R[lb];i++) a[i]+=c;
    for(int i=lb+1;i<=rb-1;i++) tag[i]+=c;
    for(int i=L[rb];i<=r;i++) a[i]+=c;
}

int query(int p){
    int b=B[p];
    return a[p]+tag[b];
}

signed main()
{
    cin>>N;
    build();
    for(int i=1;i<=N;i++) cin>>a[i];
    for(int i=1,op,l,r,c;i<=N;i++){
        cin>>op>>l>>r>>c;
        if(op==0) modify(l,r,c);
        else cout<<query(r)<<'\n';
    }
}

数列分块入门 2 代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;

int N,q,Bl;
int B[1000005],L[30005],R[30005],tag[30005];
int a[1000005],b[1000005];

void build(){
    Bl=sqrt(N);
    int l=1-Bl,r=0,cnt=0;
    while(true){
        l+=Bl, r+=Bl, cnt++;
        if(r>N) r=N;
        L[cnt]=l, R[cnt]=r;
        for(int i=l;i<=r;i++) B[i]=cnt;
        if(r==N) break;
    }
    for(int i=1;i<=N;i++) cin>>a[i];
    for(int i=1;i<=B[N];i++){
        for(int j=L[i];j<=R[i];j++) b[j]=a[j];
        sort(b+L[i],b+R[i]+1);
    }

}

void modify(int l,int r,int c){
    int lb=B[l],rb=B[r];
    if(lb==rb){
        for(int i=l;i<=r;i++) a[i]+=c;
        for(int i=L[lb];i<=R[lb];i++) b[i]=a[i];
        sort(b+L[lb],b+R[lb]+1);
        return ;
    }

    for(int i=l;i<=R[lb];i++) a[i]+=c;
    for(int i=L[lb];i<=R[lb];i++) b[i]=a[i];
    sort(b+L[lb],b+R[lb]+1);

    for(int i=lb+1;i<=rb-1;i++) tag[i]+=c;

    for(int i=L[rb];i<=r;i++) a[i]+=c;
    for(int i=L[rb];i<=R[rb];i++) b[i]=a[i];
    sort(b+L[rb],b+R[rb]+1);
}

int query(int l,int r,int c){
    int lb=B[l],rb=B[r],res=0;
    if(lb==rb){
        for(int i=l;i<=r;i++)
            if(a[i]+tag[lb]<c) res++;
        return res;
    }

    for(int i=l;i<=R[lb];i++)
        if(a[i]+tag[lb]<c) res++;
    for(int i=L[rb];i<=r;i++)
        if(a[i]+tag[rb]<c) res++;

    for(int i=lb+1;i<=rb-1;i++){
        int p=c-tag[i];
        res+=lower_bound(b+L[i],b+R[i]+1,p)-(b+L[i]);
    }

    return res;

}

signed main()
{
    cin>>N;
    build();
    for(int i=1;i<=N;i++){
        int opt,l,r,c;
        cin>>opt>>l>>r>>c;
        if(!opt) modify(l,r,c);
        else cout<<query(l,r,c*c)<<'\n';
    }
}

4.2 莫队

模板题 P2709 代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;

int N,M,k,B; 
int a[50005],b[50005];
int bel[50005],res[50005];

struct Q{
    int l,r;
    int id,ans;
}q[50005];

vector<Q> G[505];

bool cmp1(Q a,Q b){ return a.r<b.r; }
bool cmp2(Q a,Q b){ return a.id<b.id; }

signed main()
{
    cin>>N>>M>>k; B=sqrt(N);
    for(int i=1;i<=N;i++){
        cin>>a[i];
        bel[i]=(i+B-1)/B;
    }
    for(int i=1;i<=M;i++){
        cin>>q[i].l>>q[i].r;
        q[i].id=i;
        G[bel[q[i].l]].push_back(q[i]);
    }
    for(int i=1;i<=2*B;i++)
        sort(G[i].begin(),G[i].end(),cmp1);
    for(int i=1;i<=2*B;i++){
        if(G[i].empty()) continue;
        memset(b,0,sizeof b);
        int lp=G[i][0].l,rp=G[i][0].r,ans=0;
        for(int j=lp;j<=rp;j++){
            ans+=2*b[a[j]]+1;
            b[a[j]]++;
        }
        res[G[i][0].id]=ans;
        for(int j=1;j<G[i].size();j++){
            while(rp<G[i][j].r){
                ans+=2*b[a[++rp]]+1;
                b[a[rp]]++;
            }
            while(lp<G[i][j].l){
                ans-=2*b[a[lp]]-1;
                b[a[lp]]--; lp++;
            }
            while(lp>G[i][j].l){
                ans+=2*b[a[--lp]]+1;
                b[a[lp]]++;
            }
            res[G[i][j].id]=ans;
        }
    } 
    for(int i=1;i<=M;i++) cout<<res[i]<<'\n';
}