前言：
本系列是学习了董晓老师所讲的知识点做的笔记
董晓算法的个人空间-董晓算法个人主页-哔哩哔哩视频 (bilibili.com)
动态规划系列（还没学完）
【董晓算法】动态规划之背包DP问题（2024.5.11）-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);
}