数据结构板子

并查集

判断集合，合并集合，比如图论中的kruskal，连通分支等。

//int fa[N],siz[N];
void init_set(int n){//初始化
    for(int i=1;i<=n;++i){
        fa[i]=i,siz[i]=1;
    }
}
int find(int x){//路径压缩
    return fa[x]==x?x:(fa[x]=find(fa[x]));
}
void unionfa(int x,int y){//启发式合并
    int parent_x=find(x),parent_y=find(y);
    if(parent_x==parent_y){
        return;
    }
    if(siz[parent_x]>siz[parent_y]){
        swap(parent_x,parent_y);
    }//按照节点集合大小，保证小的和到大的里面。
    fa[parent_x]=parent_y;
    siz[parent_y]+=siz[parent_x];
}

ST表

$\Theta(nlogn)预处理，\Theta(1)查询$

可重复贡献———若对某种运算$opt$，有:$xopt x=x$，例如$gcd(x,x)=x,max(x,x)=x$，则类似的区间查询，比如区间gcd，区间最大值，且$opt$满足结合律$aopt(boptc)=(aoptb)optc$,则可以使用ST表进行区间查询。
但比如区间和，opt行为就会计算两次，还是不行捏。
DP:$f(i,j)=max[i,i+2^j-1]$
$f(i,0)=max[i,i]=i$
->
$f(i,j)=max(f(i,j-1),f(i+2^{j-1},j-1))$

//以最大值为例
//#define N 2000001
const int maxlog=21;
int st[N][maxlog],logn[N];
void init_st(int n){
    logn[1]=0;
    logn[2]=1;
    for(int i=3;i<N;++i){
        logn[i]=logn[i>>1]+1;
    }
}
void st_process(int total){
    init_st();
    for(int i=1;i<=n;++i){
        cin>>st[i][0];
    }
}

树状数组

int tree[N],diff[N];
int lowbit(int x){
    return x&-x;
}
void add(int x,int k,int n){
    int tem=x*k;
    while(x<=n){
        tree[x]+=k,diff[x]+=tem;
        x+=lowbit(x);   
    }
}
void add_range(int,l,int r,int k){
    add(l,k),add(r+1,-v);
}
long long int get_sum_range(intl,int r){
    return (r+1ll)*getpre(r,tree)-1ll*l*getpre(l-1,tree)-
    (getpre(r,diff)-getpre(l-1,diff));
}
int getpre(int x,int *tree){
    int cnt=0;
    while(x) {
        cnt+=tree[x];
        x-=lowbit(x);
    }
    return cnt;
}