本文主要是介绍【董晓算法】竞赛常用知识点之数据结构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)
这篇关于【董晓算法】竞赛常用知识点之数据结构1的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
