【董晓算法】竞赛常用知识点之数据结构1

发布于:2024-05-16 ⋅ 阅读:(31) ⋅ 点赞:(0)

 前言:

本系列是学习了董晓老师所讲的知识点做的笔记

董晓算法的个人空间-董晓算法个人主页-哔哩哔哩视频 (bilibili.com)

 动态规划系列(还没学完)

【董晓算法】动态规划之线性DP问题-CSDN博客

【董晓算法】动态规划之背包DP问题(2024.5.11)-CSDN博客

【董晓算法】动态规划之背包DP与树形DP-CSDN博客

字符串系列

【董晓算法】竞赛常用知识之字符串1-CSDN博客

【董晓算法】竞赛常用知识之字符串2-CSDN博客

并查集

P3367 【模板】并查集 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

fa初始化

每个节点指向它自己

fa[x]存节点x的父节点

  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 unionset(int x,int y){
  fa[find(x)]=find(y);
}

判断是否在同一集合内

x=find(x),y=find(y);
if(x==y) puts("true")
else puts("false");

按秩合并

把小集合的根指向大集合的根。

void unionset(int x,int y){
  x=find(x),y=find(y);
  if(x==y)return;
  if(siz[x]>siz[y])swap(x,y);
  fa[x]=y;
  siz[y]+=siz[x];
}

线段树+懒标记

线段树是基于分治思想的二叉树,用来维护区间信息(区间和,区间最值,区间GCD等),可以在logn的时间内执行区间修改和区间查询。线段树中每个叶子节点存储元素本身非叶子节点存储区间内元素的统计值

递归建树

#define lc p<<1
#define rc p<<1|1
#define N 500005
int n, w[N];
struct Tree{ 
  int l,r,sum
}tr[N*4];
void build(int p,int l,int r){ //建树
  tr[p={l,r,w[l]};
  if(l==r) return;
  int m=l+r>>1;
  build(lc,l,m);
  build(rc,m+1,r);
  tr[p].sum=tr[lc].sum+tr[rc].sum;
 }

点修改

从根节点进入。递归找到叶子节点[x,x],把该节点的值增加k。然后从下往上更新其祖先节点上的统计值。

void update(int p,int k,intR){
  if(tr[p].1==x&&tr[p].r==x){
     tr[p].sum+=k;
     return;
   }
   int m=tr[p].1+tr[p].r>>1;//非叶子则裂开 
    if(x<=m)update(lc,x,k);
    if(x>m)update(rc,x,k);
    tr[p].sum=tr[lc].sum+tr[rc].sum;
}

区间查询

拆分与拼凑的思想。

例如,查询区间[4,9]可以拆分成 [4.5],[6.8〕 和 [9,9],通过合并这三个区间的答案求得查询答案。

int query(int p,int l,int r){ 
  if(l<=tr[p].l && tr[p].r<=r) return tr[p].sum;
  int m=tr[p].l+tr[p].r>>1;
  pushdown(p);
  int sum=0;
  if(l<=m) sum+=query(lc,l,r);
  if(r>m) sum+=query(rc,l,r);
  return sum;
}

区间修改

做懒惰修改,当 [x,y] 完全覆盖节点区间 [a.b]时先修改该区间的 sum 值再打上一个"懒标记"然后立即返回。等下次需要时再下传“懒标记",可以把每次修改和查询的时间都控制到O(logn)

void pushup(int u){ //向上更新
  tr[u].sum=tr[lc].sum+tr[rc].sum;
}
void pushdown(int p){ //向下更新
  if(tr[p].add){
    tr[lc].sum+=tr[p].add*(tr[lc].r-tr[lc].l+1),
    tr[rc].sum+=tr[p].add*(tr[rc].r-tr[rc].l+1),
    tr[lc].add+=tr[p].add,
    tr[rc].add+=tr[p].add,
    tr[p].add=0;      
  }
}
void update(int p,int k,intR){
  if(tr[p].1==x&&tr[p].r==x){//覆盖则修改
     tr[p].sum+=(tr[p].r-tr[p].l+1)*k;
     tr[p].add+=k;
     return;
   }
   int m=tr[p].1+tr[p].r>>1;//不覆盖则裂开 
     pushdown(p);
    if(x<=m)update(lc,x,k);
    if(x>m)update(rc,x,k);
    tr[p].sum=tr[lc].sum+tr[rc].sum;
    pushup(p);
}

 P3372 【模板】线段树 1 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)


网站公告

今日签到

点亮在社区的每一天
去签到