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

 前言：

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

董晓算法的个人空间-董晓算法个人主页-哔哩哔哩视频 (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)