数据结构学习笔记

zhouyiran_2011 · 2023-06-11 22:38:24 · 算法·理论

1.单调栈、队列、优先队列

（1）单调栈：单调递增或单调递减的栈。

它适用于找左边/右边第一个比自己大的元素(位置)。

优点：时间复杂度为O(n)。

模版题：

洛谷 5788

（2）单调队列：单调递减或单调递增的队列。

它能够动态地维护定长序列中的最值。

优点：可以降低时间复杂度。

模版题：

洛谷 P1886

（3）优先队列：在优先队列中，元素被赋予优先级。当访问元素

时，具有最高优先级的元素最先删除。优先队列具有最高级先出

（first in, largest out）的行为特征。通常采用堆数据结构来实现。

它适用于动态维持有序状态的场景。

模版题：

洛谷 P3378

2.树状数组

树状数组结合了树的思想,常用来处理前缀问题。

优点：修改和查询节点的复杂度都是O(logN)。

模版题：

洛谷 P3374 P3368

树状数组求逆序对：

cin>>n;
for(int i=1;i<=n;i++)
{
    cin>>a[i];
    maxx=max(maxx, a[i]);
}
for(int i=1;i<=n;i++)
{   
    t1[i]=query(maxx)-query(a[i]);
    add(a[i], 1);
}

3.线段树

线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一

些单元区间，每个单元区间对应线段树中的一个叶结点。

普通线段树：

#include<bits/stdc++.h>
#define ll long long 
#define lid (id<<1)
#define rid (id<<1|1)
using namespace std;
ll n, m, a[500005], x, y, z;
string b;
struct seg_tree{
   ll l, r;
   ll sum, lazy;
}tr[2000005]; 
void pushup(int id)
{
    tr[id].sum=tr[lid].sum+tr[rid].sum;
}
void build(ll id, ll l, ll r) //建树 
{
    tr[id].l=l;
    tr[id].r=r;
    if(l==r)
    {
        tr[id].sum=a[l];
        return ; 
    }
    ll mid=(l+r)>>1;
    build(lid, l, mid);
    build(rid, mid+1, r);
    pushup(id);
}
void update(int id,int l,int k)//单点修改
{
    if(tr[id].l==l&&tr[id].r==l)
    {
        tr[id].sum+=k;
        return ;
    }
    int mid=(tr[id].r+tr[id].l)>>1;
    if(mid>=l)
    {
        update(lid,l,k);
    }
    else
    {
        update(rid,l,k);
    }
    pushup(id);
}
void pushdown(ll id) //下放lazy 
{
    if(tr[id].lazy&&tr[id].l!=tr[id].r)
    {
        tr[lid].lazy+=tr[id].lazy;
        tr[rid].lazy+=tr[id].lazy;
        tr[lid].sum+=tr[id].lazy*(tr[lid].r-tr[lid].l+1);
        tr[rid].sum+=tr[id].lazy*(tr[rid].r-tr[rid].l+1);
        tr[id].lazy=0;
   }
}
void modify(ll id, ll l, ll r, ll val)//区间修改 
{
    pushdown(id);
    if(tr[id].l==l&&tr[id].r==r)
    {
        tr[id].lazy+=val;
        tr[id].sum+=val*(tr[id].r-tr[id].l+1);
        return ;
    }   
    ll mid=(tr[id].l+tr[id].r)>>1;
    if(r<=mid)
    {
        modify(lid, l, r, val);
    }
    else if(l>mid)
    {
        modify(rid, l, r, val);
    }
    else
    {
        modify(lid, l, mid, val);
        modify(rid, mid+1, r, val);
    }
    pushup(id);
}
ll query(ll id,ll l, ll r) //区间查询 
{
    pushdown(id);
    if(tr[id].l==l&&tr[id].r==r)
    {
        return tr[id].sum;
    }
    int mid=(tr[id].l+tr[id].r)>>1;
    if(r<=mid)
    {
        return query(lid, l, r);
    }
    if(l>mid)
    {
        return query(rid, l, r);
    }
    return query(lid,l,mid)+query(rid,mid+1,r);
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];      
    }
    build(1,1,n);
    cin>>m;
    for(int i=1;i<=m;i++)
    {   
        cin>>b;
        if(b=="ADD")
        {
            cin>>x>>y>>z; 
            modify(1, x, y, z);
        }
        else
        {
            cin>>x>>y;
            cout<<query(1,x,y)<<endl;
        }
   }
   return 0;
}

维护最大子段和（应该是对的）

#include<bits/stdc++.h>
#define lid id<<1
#define rid id<<1|1
using namespace std;
const int maxn=1e5+10;
int n, m, a[maxn];
struct seg_tree{
    int ms, ls, rs, s;//最大子段和,区间紧靠左端点的最大子段和,区间紧靠左端点的最大子段和,区间子段和  
}tr[maxn<<2];
void pushup(int id)
{
    tr[id].ms=max(max(tr[lid].ms, tr[rid].ms), tr[lid].rs+tr[rid].ls);
    tr[id].ls=max(tr[lid].ls,tr[rid].ls+tr[lid].s);
    tr[id].rs=max(tr[rid].rs,tr[lid].rs+tr[rid].s);
    tr[id].s=tr[lid].s+tr[rid].s;
}
void build(int id,int l,int r)
{
    if(l==r)
    {
        tr[id].ms=tr[id].ls=tr[id].rs=tr[id].s=a[l];
        return ;
    }
    int mid=(l+r)>>1;
    build(lid, l, mid);
    build(rid, mid+1, r);
    pushup(id);
}
void add(int id,int l,int r,int u,int v)
{
    if(l==r)
    {
        tr[id].ms=tr[id].ls=tr[id].rs=tr[id].s=v;
        return ;
    }
    int mid=(l+r)>>1;
    if(u<=mid)
    {
        add(lid, l, mid, u, v);
    }
    else
    {
        add(rid, mid+1, r, u, v);
    }
    pushup(id);
}
seg_tree query(int id,int l,int r,int ql,int qr)
{
    if(ql<=l&&r<=qr)
    {
        return tr[id];
    }
    seg_tree x, y, w;
    int mid=(l+r)>>1;
    if(qr<=mid)
    {
        w=query(lid, l, mid, ql, qr);
    }
    else if(ql>mid) 
    {
        w=query(rid, mid+1, r, ql, qr);
    }
    else
    {
        x=query(lid, l, mid, ql, mid);
        y=query(rid, mid+1, r, mid+1, qr);
        w.s=x.s+y.s;
        w.ls=max(x.ls, x.s+y.ls);
        w.rs=max(y.rs, y.s+x.rs);
        w.ms=max(max(x.ms, y.ms), x.rs+y.ls);
    }
    return w;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    cin>>m;
    build(1, 1, n);
    for(int i=1;i<=m;i++)
    {
        int x, y, z;
        cin>>x>>y>>z;
        if(x==0) add(1, 1, n, y, z);
        else 
        {
            seg_tree x=query(1, 1, n, y, z);
            cout<<x.ms<<endl;
        }
    }
    return 0;
}

线段树做题技巧：

一般需要线段树优化的题有一些特点：

有明显的修改和查询操作，考虑该如何转换。
有类似于合并的操作，一段区间的值与两个端点的合并有关。
直接考虑计算时间复杂度。

线段树优化怎么写：

线段树要维护的就是与答案相关的值（一般都是能协助区间合并的），就像dp状态设计一样，例如山海经中的最大子段和、区间前后缀等等。
合并可能会很复杂，考虑分类讨论。
剩下的直接套板子。

动态开点线段树(千万不要复制，是错的)

int cnt=1, ans;
void pushdown(int id,int l,int r)
{
    if(lazy[id])
    {
        if(!ls[id]) ls[id]=++cnt;
        if(!rs[id]) rs[id]=++cnt;
        int mid=(l+r)>>1;
        lazy[ls[id]]+=lazy[id];
        lazy[rs[id]]+=lazy[id];
        tr[ls[id]]+=lazy[id]*(mid-l+1);
        tr[rs[id]]+=lazy[id]*(r-mid);
        lazy[id]=0;
    }
}
void pushup(int id)
{
    tr[id]=tr[ls[id]]+tr[rs[id]];
}
void add(int &id,int l,int r,int x,int v)//单点修改 
{
    if(!id) id=++cnt;
    if(l==r)
    {
        tr[id]=v;
        return ;
    }
    int mid=(l+r)>>1;
    if(x<=mid)
    {
        return add(id, l, mid, x, v);
    }
    else
    {
        return add(id, mid+1, r, x, v);
    }
    pushup(id);
}
void updata(int &id,int l,int r,int vl,int vr,int v)//区间修改 
{
    if(!id) id=++cnt;
    if(r<vl||l>vr)  return ;
    if(vl<=l&&r<=vr)
    {
        tr[id]+=(r-l+1)*v;
        return ;
    }
    int mid=(l+r)/2;
    pushdown(id, l, r);
    updata(ls[id], l, mid, vl, vr, v);
    updata(rs[id], mid+1, r, vl, vr, v);
} 
int query(int id,int l,int r,int x)//区间查询 
{
    if(!id) return 0;
    pushdown(id, l, r);
    if(r<vl||l>vr) return 0;
    if(vl<=l&&r<=vr)
    {
        return tr[id];
    }
    return query(ls[id], l, mid, vl, vr)+query(ls[id], mid+1, r, vl, vr)
}

int query(int id,int vl,int vr,int l,int r)
{
    if(!id) return 0;
    if(vl<=l&&r<=vr)
    {
        return si[id];
    }
    int mid=(l+r)>>1;
    pushdown(id);
    int sum=0;
    if(vl<=mid) 
    {
        sum+=query(ls[id], vl, vr, l, mid);
    }
    if(vr>mid)
    {
        sum+=query(rs[id], vl, vr, mid+1, r);
    }
    return sum;
}

int find(int id,int l,int r,int k)
{
    if(l==r)    return l;
    pushdown(id);
    int mid=(l+r)>>1;
    if(k<=si[ls[id]])
    {
        return find(ls[id], l, mid, k);
    } 
    else return find(rs[id], mid+1, r, k-si[ls[id]]);
}

线段树合并

int merge(int a,int b,int x,int y)
{
    if(!a) return b;
    if(!b) return a;
    if(x==y)
    {
        tr[a]+=tr[b];
        return a;
    }
    int mid=(x+y)>>1;
    ls[a]=merge(ls[a], ls[b], x, mid);
    rs[a]=merge(rs[a], rs[b], mid+1, y);
//  pushup(a);
    return a;
}

还有这一版

int merge(int a, int b, int l, int r) 
{
    if(!a||!b) 
    {
        return a+b;
    }
    int p=++cnt;
    if(l==r) 
    {
        tr[p]=tr[a]+tr[b];
        return p;
    }
    int mid=(l+r)>>1;
    tr[p]=tr[a]+tr[b];
    ls[p]=merge(ls[a], ls[b], l, mid);
    rs[p]=merge(rs[a], rs[b], mid+1, r);
    return p;
}

4.树链剖分

树剖是通过轻重边将树分割成多条链，然后利用数据结构来维护这些链（本质上是一种优化暴力）。

一些概念和性质

重儿子：父亲节点的所有儿子中子树结点数目最多的节点。

轻儿子：父亲节点中除了重儿子以外的儿子。

其他什么的也不用解释了。

整棵树会被剖分成若干条重链。
轻儿子一定是每条重链的顶点。
任意一条路径被切分成不超过 logn 条链。
重链的各个节点的dfs序都是连续的。

板子：

struct edge{
    int next,int to;
}edge[maxn<<1];
struct node{
    int sum, lazy, l, r, lid, rid;
}node[maxn<<1];
int rt, n, m, r, a[maxn], cnt, d[maxn], f[maxn], head[maxn];
int size[maxn], son[maxn], rk[maxn], top[maxn], id[maxn];
//d:深度 f:父节点 size:子树节点个数 son:重儿子 
//rk:当前dfs标号在原树中所对应的节点编号 top:当前节点所在链的顶端节点
//id:每个节点剖分后的新编号 
void dfs1(int u,int fa,int dep)//处理出f,size,son,d数组 
{
    f[u]=fa;
    d[u]=dep;
    size[u]=1;
    for(int i=head[u];i;i=edge[i].next)
    {
        int v=edge[i].to;
        if(v==fa) continue;
        dfs1(v,u,dep+1);
        size[u]+=size[v];
        if(size[v]>size[son[u]])
        {
            son[u]=v;
        }
    }
}
void dfs2(int u,int t)//处理出top,id,rk数组 (t表示重链顶端） 
{
    top[u]=t;
    id[u]=++cnt;
    rk[cnt]=u;
    if(!son[u]) return ;
    dfs2(son[u],t);
    for(int i=head[u];i;i=edge[i].next)//轻链 
    {
        int v=edge[i].to;
        if(v!=son[u]&&v!=f[u])
        {
            dfs2(v,v);
        }
    }
}

查找

int query(int id,int l,int r)
{
    if(l<=tr[id].l&&r>=tr[id].r)
    {
        return tr[id].sum;
    }
    int mid=(tr[id].l+tr[id].r)/2;
    int res=0;
    if(l<=mid) 
    {
        res+=query(lc, l, r);
    }
    if(r>mid)
    {
        res+=query(rc, l, r);
    } 
    return res;
}

边权放点权

#include<bits/stdc++.h>
#define lid (u*2)
#define rid (u*2+1)
using namespace std;
const int maxn=1e5+10;
int n,cnt, x[maxn], y[maxn], z[maxn];
int dian[maxn];
int a[maxn];
int son[maxn],f[maxn],size[maxn],top[maxn],d[maxn],rk[maxn],id[maxn];
int tr[maxn<<2];
struct edge{
    int next,to,w;
}edge[maxn<<1];
int head[maxn], edgenum;
void add(int from,int to,int w)
{
    edge[++edgenum].next=head[from];
    edge[edgenum].to=to;
    edge[edgenum].w=w;
    head[from]=edgenum;
}
void dfs1(int u,int fa)
{
    f[u]=fa;
    d[u]=d[fa]+1;
    size[u]=1;
    for(int i=head[u];i;i=edge[i].next)
    {
        int y=edge[i].to;
        if(y==fa) continue;
        a[y]=edge[i].w;
        dfs1(y,u);
        size[u]+=size[y];
        if(size[y]>size[son[u]])
        {
            son[u]=y;
        }
    }
}
void dfs2(int u,int t)
{
    top[u]=t;
    id[u]=++cnt;
    rk[cnt]=u;
    if(son[u]) 
    {
        dfs2(son[u],t);
    }
    for(int i=head[u];i;i=edge[i].next)
    {
        int y=edge[i].to;
        if(y!=son[u]&&y!=f[u])
        {
            dfs2(y,y);
        }
    }
}
void build(int u,int l,int r)
{
    if(l==r)
    {
        tr[u]=a[rk[l]];
        return;
    }
    int mid=(l+r)>>1;
    build(lid,l,mid);
    build(rid,mid+1,r);
    tr[u]=max(tr[lid],tr[rid]);
    return;
}
void updata(int u,int l,int r,int pos,int z)
{
    if(l==r)
    {
        tr[u]=z;
        return;
    }
    int mid=(l+r)>>1;
    if(pos<=mid)
    {
        updata(lid,l,mid,pos,z);
    }
    else 
    {
        updata(rid,mid+1,r,pos,z);
    }
    tr[u]=max(tr[lid],tr[rid]);
}
int mx(int u,int l,int r,int ql,int qr)
{
    if(ql>r||qr<l)
    {
        return -1e9;
    }
    if(ql<=l&&r<=qr)
    {
        return tr[u];
    }
    int mid=(l+r)>>1;
    return max(mx(lid,l,mid,ql,qr),mx(rid,mid+1,r,ql,qr));
}
int qsum(int x,int y)
{
    int res=-1e9;
    while(top[x]!=top[y])
    {
        if(d[top[x]]<d[top[y]])
        {
            swap(x,y);
        }
        res=max(res,mx(1,1,n,id[top[x]],id[x]));
        x=f[top[x]];
    }
    if(d[x]>d[y])  swap(x,y);
    res=max(res,mx(1,1,n,id[x]+1,id[y]));
    return res;
}
int main()
{
    cin>>n;
    for(int i=1;i<n;i++)
    {
        cin>>x[i]>>y[i]>>z[i];
        add(x[i], y[i], z[i]);
        add(y[i], x[i], z[i]);
    }
    dfs1(1,0);
    dfs2(1,1);
    for(int i=1;i<n;i++)
    {
        if(d[x[i]]>d[y[i]])
        {
            swap(x[i], y[i]);
        }
    }
    build(1,1,n);
    string s;
    while(cin>>s)
    {
        if(s[0]=='D') break;
        if(s[0]=='C')
        {
            int x,z;
            cin>>x>>z;
            updata(1,1,n,id[y[x]],z);
        }
        if(s[0]=='Q')
        {
            int x,y;
            cin>>x>>y;
            cout<<qsum(x, y)<<endl;
        }
    }
    return 0;
}

有时间再来好好修整一下 