专栏文章

算法与数据结构

NNoxfer
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqrp1z3
此快照首次捕获于
2025/12/04 09:38
3 个月前
此快照最后确认于
2025/12/04 09:38
3 个月前
查看原文

模板

https://www.luogu.com.cn/paste/et2y2jvx

数据结构

单调栈/单调队列

每次入栈/队列,通过把所有影响单调性的元素扔出去来维护单调性，单调队列可用双端队列与滑动窗口结合
CPP
//单调栈
stack<int> st;
int a[MAXN];

while (!st.empty()&&a[st.top()]<a[i]) st.pop() //单调递减
//while (!st.empty()&&a[st.top()]>a[i]) st.pop() 
st.push(i);

//单调队列
deque<int> q;
int a[MAXN];
  //插入
while (!q.empty(0&&a[q.back()]<a[i]) st.pop_back(); //单调递减
//while (!q.empty(0&&a[q.back()]>a[i]) st.pop_back();
q.push(i);
  //取出
while (!q.empty()&&q.front()+x<i) q.pop_front();
  dat=a[q.front()];

ST表

用倍增实现区间RMQ问题。
首先预处理出 lgilg_i 表示 log⁡i\log i 的值，预处理 fi,jf_{i,j} 表示 从 ii 开始往后 2j2^j 区间的最大值
预处理复杂度 O(nlog⁡n)\Omicron(n \log n)
查询 l,rl,r 区间最值，就是找到两个长度为 log⁡(r−l+1)\log(r-l+1) 下取整的区间，一个的左端点为 ll，一个的右端点为rr
CPP
int n,m,f[100005][20],lg[100005];
inline void init(){
	lg[1]=0;
	for (int i = 2;i <= n;i ++) lg[i]=lg[i>>1]+1;
	for (int j = 1; j <= lg[n]; j ++)
		for (int i = 1;i+(1<<j)-1<=n;i ++)
			f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}
inline int query(int l,int r){
	int len=lg[r-l+1];
	return max(f[l][len],f[r-(1<<len)+1][len]);
}

树状数组

维护几个2的几次方的区间和
用 lowbit(i)lowbit(i) 表示只保留二进制 ii 的最低为 11 后的值，可以发现每次 +lowbit(i)+lowbit(i) 可以到达下一个连续区间，查询就是查询前缀和，如果是区间查询就是差分
以上是单点修改，区间查询，如果是区间修改，单点擦汗寻，就维护一个差分数组
CPP
struct BIT{
	int t[500005],n;
	void resize(int num){n=num;}
	void add(int pos,int k){
		for (;pos<=n;pos+=pos&(-pos)) t[pos]+=k;	
	}
	int query(int pos){
		int res=0;
		for (;pos;pos-=pos&(-pos)) res+=t[pos];
		return res;	
	}
}T;

线段树

维护一个一棵树，每个节点维护一个区间的一些信息，左儿子就是父亲节点区间的左半部分，右儿子就是右半部分，普通线段树左右儿子下标用 u<<1,u<<1∣1u<<1,u<<1|1 表示。
重要操作是区间修改下放标记，如果每次区间修改都递归修改所有子区间的复杂度太奢侈，考虑用给极大区间打标记，当需要向下递归的时候修改儿子区间并给儿子打标记
CPP
#define MAXN 100005
#define root 1,1,n
#define lson ls(pos),l,m
#define rson rs(pos),m+1,r
#define ll unsigned long long
int n,m,op,x,y;
ll a[MAXN],k;
struct mtree{
	int l,r;
	bool istag;
	ll tag,sum;
}t[4*MAXN];

inline int ls(int pos){return pos<<1;}
inline int rs(int pos){return pos<<1|1;}
inline int len(int l,int r){return r-l+1;}

inline void pushup(int pos){t[pos].sum=t[ls(pos)].sum+t[rs(pos)].sum;}
inline void pushdown(int pos){
	if (t[pos].istag){
		t[ls(pos)].istag=t[rs(pos)].istag=true;
		t[ls(pos)].sum+=len(t[ls(pos)].l,t[ls(pos)].r)*t[pos].tag;
		t[rs(pos)].sum+=len(t[rs(pos)].l,t[rs(pos)].r)*t[pos].tag;
		t[ls(pos)].tag+=t[pos].tag;
		t[rs(pos)].tag+=t[pos].tag;
		t[pos].istag=false;
		t[pos].tag=0;
	}
}

void tree_build (int pos,int l,int r){
	t[pos].l=l,t[pos].r=r,t[pos].sum=t[pos].tag=0,t[pos].istag=false;
	if (l==r){
		t[pos].sum=a[l];
		return;
	}
	int m=(l+r)>>1;
	tree_build (lson);
	tree_build (rson);
	pushup(pos);
}
void tree_change(int pos,int l,int r,int nl,int nr,ll k){
	if (nl<=l && r<=nr){
		t[pos].sum+=len(l,r)*k;
		t[pos].tag+=k;
		t[pos].istag=true;
		return;
	}
	pushdown(pos);
	int m=(l+r)>>1;
	if (nl<=m) tree_change(lson,nl,nr,k);
	if (m<nr) tree_change(rson,nl,nr,k);
	pushup(pos);
}
ll tree_query(int pos,int l,int r,int nl,int nr){
	if (nl<=l && r<=nr) return t[pos].sum;
	pushdown(pos);
	int m=(l+r)>>1;
	ll res=0;
	if (nl<=m) res+=tree_query(lson,nl,nr);
	if (m<nr) res+=tree_query(rson,nl,nr);
	return res;
}

可持续化线段树

注意到普通线段树每次操作最多影响 log⁡n\log n 个节点，不难想到记录根节点和每次修改的log⁡n\log n个节点
时空复杂度 O(nlog⁡n+qlog⁡n)\Omicron(n \log n + q \log n)
但这其实是可持续化数组
CPP
#include <bits/stdc++.h>
using namespace std;
#define MAXN 1000006
int n,q,a[MAXN],root[MAXN];
int op,rt,x,y,tot;
struct node{
    int ls,rs,val;
}t[MAXN<<5];
void build(int &u,int l,int r){
    u=++tot;
    if (l==r){
        t[u].val=a[l];
        return;
    }
    int m=(l+r)>>1;
    build(t[u].ls,l,m);build(t[u].rs,m+1,r);
}
void change(int &u,int pre,int l,int r,int x,int y){
    u=++tot;
    t[u]=t[pre];
    if (l==r){
        t[u].val=y;
        return;
    }
    int m=(l+r)>>1;
    if (x<=m) change(t[u].ls,t[pre].ls,l,m,x,y);
    else change(t[u].rs,t[pre].rs,m+1,r,x,y);
}
int query(int u,int l,int r,int x){
    if (l==r) return t[u].val;
    int m=(l+r)>>1;
    if (x<=m) return query(t[u].ls,l,m,x);
    return query(t[u].rs,m+1,r,x);
}
int main(){
    cin >>n>>q;
    for (int i = 1;i <= n;i ++) scanf ("%d",&a[i]);
    build(root[0],1,n);
    for (int i = 1; i <= q;i ++){
        scanf ("%d%d%d",&rt,&op,&x);
        if (op==1){
            scanf ("%d",&y);
            change(root[i],root[rt],1,n,x,y);
        }else{
            printf ("%d\n",query(root[rt],1,n,x));
            root[i]=root[rt];
        }
    }
    return 0;
}
如果是可持续化权值线段树，我们可以把数组下标作为根节点，查询区间第 kk 大只需要在递归的时候把两个端点对应的区间信息相减，类似前缀和的思路
CPP
#include <bits/stdc++.h>
using namespace std;
#define MAXN 200005
int n,m,tot;
int a[MAXN],b[MAXN],rt[MAXN];
struct node{
    int ls,rs,val;
}t[MAXN<<5];
void update(int &u,int pre,int l,int r,int x){
    u=++tot;
    t[u]=t[pre];t[u].val++;
    if (l<r){
        int mid=(l+r)>>1;
        if (x<=mid) update(t[u].ls,t[pre].ls,l,mid,x);
        else update(t[u].rs,t[pre].rs,mid+1,r,x);
    }
}
int query(int u,int v,int l,int r,int k){
    if (l>=r) return l;
    int x=t[t[v].ls].val-t[t[u].ls].val,mid=(l+r)>>1;
    if (k<=x) return query (t[u].ls,t[v].ls,l,mid,k);
    return query(t[u].rs,t[v].rs,mid+1,r,k-x);
}
int main(){
    cin >>n>>m;
    for (int i = 1;i <= n;i ++){
        cin >>a[i];
        b[i]=a[i];
    }
    sort(b+1,b+n+1);
    int cnt=unique(b+1,b+n+1)-b-1;
    for (int i = 1;i <= n;i ++){
        int x=lower_bound(b+1,b+cnt+1,a[i])-b;
        update(rt[i],rt[i-1],1,cnt,x);
    }
    int l,r,k;
    while (m--){
        cin >>l>>r>>k;
        cout <<b[query(rt[l-1],rt[r],1,cnt,k)]<<'\n';
    }
    return 0;
}

线段树合并

可持续化+启发式合并即可，类似FHQ的merge
CPP
struct node{
    int ls,rs;
    pair<int,int> mx;
}t[MAXN<<6];
inline void pushup(int u){
    t[u].mx=make_pair(0,0);
    if (t[u].ls) t[u].mx=max(t[u].mx,t[t[u].ls].mx);
    if (t[u].rs) t[u].mx=max(t[u].mx,t[t[u].rs].mx);
}
void insert(int &u,int l,int r,int x,int k){
    if (!u) u=++tot;
    if (l==r){
        t[u].mx.fi+=k;
        t[u].mx.se=-x;
        return;
    }
    int m=(l+r)>>1;
    if(x<=m) insert(t[u].ls,l,m,x,k);
    else insert(t[u].rs,m+1,r,x,k);
    pushup(u);
}
int merge(int x,int y,int l,int r){
    if (!x||!y) return x|y;
    if (l==r){
        t[x].mx.fi+=t[y].mx.fi;
        return x;
    }
    int m=(l+r)>>1;
    t[x].ls=merge(t[x].ls,t[y].ls,l,m);
    t[x].rs=merge(t[x].rs,t[y].rs,m+1,r);
    pushup(x);
    return x;
}

并查集

维护一个树形结构，每次查询就是查询根节点，递归即可，合并就是把一个树挂到另一个根节点下面
CPP
struct DSU{
	int fa[10005];
	DSU(){for (int i = 1;i <= 10000;++i) fa[i]=i;}
	int find(int pos){
		if (fa[pos]==pos) return pos;
		else{fa[pos]=find(fa[pos]);return fa[pos];}
	}	
	void uni(int u,int v){
		u=find(u),v=find(v);
		fa[u]=v;	
	}
	bool check(int u,int v){
		u=find(u),v=find(v);
		return u==v;	
	}
}D;

可持续化并查集

可持续化的思想都差不多，无非每次修改变化的部分比较少可以记录，前提是没有路径压缩可以用一个栈记录每次启发式合并
CPP
#include <bits/stdc++.h>
using namespace std;
#define MAXN 200005
int n,m,op[MAXN],x[MAXN],y[MAXN],ans[MAXN];
struct Edge{
	int u,v,nxt;	
}e[MAXN];
int head[MAXN],cnt;
inline void addedge(int u,int v){
	++cnt;
	e[cnt].u=u;
	e[cnt].v=v;
	e[cnt].nxt=head[u];
	head[u]=cnt;	
}
int fa[MAXN],sz[MAXN];
stack <int> st;
int find(int u){
	if (fa[u]==u) return u;
	return find(fa[u]);
}
inline void merge(int u,int v){
	u=find(u),v=find(v);
	if (u==v) return;
	if (sz[u]<sz[v]) swap(u,v);
	fa[v]=u;
	sz[u]+=sz[v];
	st.push(v);
}	
inline void back(){
	int u=st.top();
	st.pop();
	sz[fa[u]]-=sz[u];
	fa[u]=u;
}	
void dfs(int u){
	int tim=st.size();
	if (op[u]==1) merge(x[u],y[u]);
	else if (op[u]==3) ans[u]=(find(x[u])==find(y[u]));
	for (int i = head[u]; i; i = e[i].nxt){
		int v=e[i].v;
		dfs(v);
	}
	while (st.size()>tim) back();
}
int main(){
	cin >>n>>m;
	for (int i = 1;i <= n;i ++) fa[i]=i,sz[i]=1;
	for (int i = 1;i <= m;i ++){
		cin >>op[i];
		if (op[i]==1){
			cin >>x[i]>>y[i];
			addedge(i-1,i);
		}else if (op[i]==2){
			cin >>x[i];
			addedge(x[i],i);
		}else{
			cin >>x[i]>>y[i];
			addedge(i-1,i);
		}
	}
	dfs(0);
	for (int i = 1;i <= m;i ++) if (op[i]==3) cout <<ans[i]<<'\n';
	return 0;
}

FHQ平衡树

两个重要操作，合并和分裂。
分裂就是如果根节点满足条件，就把根节点作为左子树，看还能从右儿子拆出来多少挂到根节点的右儿子上，剩下的就是右子树
合并就是启发式合并，谁大谁是根节点
CPP
#define MAXN 100005
int n,op,x,root,cnt;
struct node{
    int val,pri,sz;
    int ls,rs;
}t[MAXN];
inline void newnode(int x){
    ++cnt;
    t[cnt].ls=t[cnt].rs=0;
    t[cnt].val=x;
    t[cnt].sz=1;
    t[cnt].pri=rand();
}
inline void pushup(int u){t[u].sz=t[t[u].ls].sz+t[t[u].rs].sz+1;}
int merge(int L,int R){
    if (L==0 || R==0) return L+R;
    if (t[L].pri>t[R].pri){
        t[L].rs=merge(t[L].rs,R);
        pushup(L);
        return L;
    }else{
        t[R].ls=merge(L,t[R].ls);
        pushup(R);
        return (R);
    }
}
void split(int u,int x,int &L,int &R){
    if (u==0){L=R=0;return;}
    if (t[u].val<=x){
        L=u;
        split(t[u].rs,x,t[u].rs,R);
    }else{
        R=u;
        split(t[u].ls,x,L,t[u].ls);
    }
    pushup(u);
}
inline void insert(int x){
    int L,R;
    split(root,x,L,R);
    newnode(x);
    root=merge(merge(L,cnt),R);
}
inline void del(int x){
    int L,R,M;
    split(root,x,L,R);
    split(L,x-1,L,M);
    root=merge(merge(L,merge(t[M].ls,t[M].rs)),R);
}
int _rank(int u,int x){
    if (u==0) return 1;
    if (x<=t[u].val) return _rank(t[u].ls,x);
    return _rank(t[u].rs,x)+t[t[u].ls].sz+1;
}
int _kth(int u,int x){
    if (x==t[t[u].ls].sz+1) return t[u].val;
    if (x<=t[t[u].ls].sz) return _kth(t[u].ls,x);
    return _kth(t[u].rs,x-t[t[u].ls].sz-1);
}
int _pre(int u,int x){
    if (u==0) return -1e9;
    if (x<=t[u].val) return _pre(t[u].ls,x);
    return max(_pre(t[u].rs,x),t[u].val);
}
int _nxt(int u,int x){
    if (u==0) return 1e9;
    if (x>=t[u].val) return _nxt(t[u].rs,x);
    return min(_nxt(t[u].ls,x),t[u].val);
}
inline int Rank(int x){return _rank(root,x);}
inline int kth(int x){return _kth(root,x);}
inline int pre(int x){return _pre(root,x);}
inline int nxt(int x){return _nxt(root,x);}

文艺平衡树

区间修改类似线段树打标记即可，而且FHQ可以通过合并，实现 O(n)\Omicron(n) 的区间插入，这比splay通过笛卡尔树建树再旋转挂到树上的复杂度要低很多
CPP
#define MAXN 100005
int n,m,l,r,root,cnt;
struct node{
    int val,pri,sz;
    int ls,rs;
    bool tag;
}t[MAXN];
inline void newnode(int x){
    ++cnt;
    t[cnt].ls=t[cnt].rs=0;    
    t[cnt].pri=rand();
    t[cnt].val=x;
    t[cnt].sz=1;
    t[cnt].tag=false;
}
inline void pushup(int u){t[u].sz=t[t[u].ls].sz+t[t[u].rs].sz+1;}
inline void pushdown(int u){
    if( t[u].tag){
        swap(t[u].ls,t[u].rs);
        t[t[u].ls].tag^=1;
        t[t[u].rs].tag^=1;
        t[u].tag=false;
    }
}
void split(int u,int x,int &L,int &R){
    if (u==0){L=R=0;return;}
    pushdown(u);
    if (t[t[u].ls].sz+1<=x){
        L=u;
        split(t[u].rs,x-t[t[u].ls].sz-1,t[u].rs,R);
    }else{
        R=u;
        split(t[u].ls,x,L,t[u].ls);
    }
    pushup(u);
}
int merge(int L,int R){
    if (!L||!R) return L+R;
    if (t[L].pri>t[R].pri){
        pushdown(L);
        t[L].rs=merge(t[L].rs,R);
        pushup(L);
        return L;
    }else{
        pushdown(R);
        t[R].ls=merge(L,t[R].ls);
        pushup(R);
        return R;
    }
}
void inorder(int u){
    if (u==0) return;
    pushdown(u);
    inorder(t[u].ls);write(t[u].val,' ');inorder(t[u].rs);
}

树链剖分

把一颗树分成几条链的形式，这里讲重链剖分，也就是每次选择以儿子为根的子树最大的儿子，每个链底部都是叶子节点，由于是链，链上DFS序是连续的，可以用线段树快速的维护一些信息，代码实现线一次DFS跑出每个点的深度，父亲，子树的大小，以及重儿子，第二遍DFS跑出链头和DFS序，注意更新A数组，线段树维护的下标是DFS序，不是原来A的下标，需要新数组存储
CPP
class Segment_Tree{...}T;
class Heavy_Light_Decomposition{
private:
    int fa[MAXN],sz[MAXN],son[MAXN],top[MAXN],dep[MAXN],dfn[MAXN],idx;
    void dfs1(int u,int father){
        dep[u]=dep[father]+1;
        fa[u]=father;
        sz[u]=1;
        for (int i = head[u];i;i=e[i].nxt){
            int v=e[i].v;
            if (v==father) continue;
            dfs1(v,u);
            sz[u]+=sz[v];
            if (!son[u] || sz[son[u]]<sz[v]) son[u]=v;
        }
    }
    void dfs2(int u,int topx){
        dfn[u]=++idx;
        newa[idx]=a[u];
        top[u]=topx;
        if (!son[u]) return;
        dfs2(son[u],topx);
        for (int i = head[u];i;i=e[i].nxt){
            int v=e[i].v;
            if (v==fa[u]||v==son[u]) continue;
            dfs2(v,v);
        }
    }   
public:
    void init(){dfs1(s,0);dfs2(s,s);}
    int LCA(int u,int v){
        while (top[u]!=top[v]){
            if (dep[top[u]]<dep[top[v]]) swap(u,v);
            u=fa[top[u]];
        }
        return dep[u]<dep[v]?u:v;
    }
    void add_range(int u,int v,int x){
        while (top[u]!=top[v]){
            if (dep[top[u]]<dep[top[v]]) swap(u,v);
            T.add(root,dfn[top[u]],dfn[u],x);
            u=fa[top[u]];
        }
        if (dep[u]>dep[v]) swap(u,v);
        T.add(root,dfn[u],dfn[v],x);
    }
    int query_range(int u,int v){
        long long res=0;
        while (top[u]!=top[v]){
            if (dep[top[u]]<dep[top[v]]) swap(u,v);
            res+=T.query(root,dfn[top[u]],dfn[u]);
            res%=p;
            u=fa[top[u]];
        }
        if (dep[u]>dep[v]) swap(u,v);
        res+=T.query(root,dfn[u],dfn[v]);
        return res%p;
    }
    void add_tree(int u,int x){T.add(root,dfn[u],dfn[u]+sz[u]-1,x);}
    int query_tree(int u){return T.query(root,dfn[u],dfn[u]+sz[u]-1);}
}HLD;

图论

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...