数据结构一

本分类仅供复习、整理模板使用，不适用于第一次学。
与树有关的数据结构：

  • 并查集
  • ST表
  • 树状数组
  • 线段树

并查集

并查集能 O(1) 的找到点的集合，我遍历所有却仍旧没有找到归属
不得不说与其他数据结构相比，并查集真的是高效又好看，她甚至还是我的白月光……（指第一个学的数据结构）

用途及要求

判断连通性（所属集合），支持合并和查询。

原理

$fa_x$ 表示 $x$ 节点的父亲，可以构建出一个森林。同根的两点在同一集合内。若 $x$ 是根则 $fa_x=x$
合并 $x,y$：令 $x$ 的根是 $y$ 的根的父亲。
查询：递归 $fa_x$ 至 $fa_x=x$，即寻找所在的树的根。

特点

路径压缩最坏 $O(\log n)$，路径压缩+启发式合并接近 $O(1)$。一般只使用路径压缩即可。初始化 $fa_x=x, sz_x=1$

路径压缩

1
2
3
4
5
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void merge(int x,int y){
    x=find(x),y=find(y);
    if(x!=y) fa[x]=y;
}

路径压缩+启发式合并

1
2
3
4
5
6
7
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void merge(int x,int y){
    x=find(x),y=find(y);
    if(x==y) return;
    if(sz[x]>sz[y]) swap(x,y);
    fa[x]=y,sz[y]+=sz[x];
}

ST表

即使是倍增的去接近你，我也需要你能忍受我的反复才能相遇
否则无论思念如何重复，我也找不回你的答案

用途及要求

查询任意区间 $[L,R]$的值，需要满足可重复计算贡献
即 $x=cal(x,x)$，如 max, min, 按位与, 按位或, lca……

原理

倍增思想，类似 LCA 中求 $fa$
$st_{i,j}$ 表示左端点为 $i$，长度为 $2^j$ 的区间的值。

特点

预处理后不可修改。预处理 $O(n\log n)$，查询 $O(1)$

1
2
3
4
5
6
7
8
9
10
void init(){
    for(int i=1;i<=n;i++) st[i][0]=a[i];
    for(int len=1;(1<<len)<=n;len++)
        for(int l=1;l+(1<<len)-1<=n;l++)
            st[l][len]=max(st[l][len-1],st[l+(1<<len-1)][len-1]);
}
int query(int l,int r){
    int k=log(r-l+1)/log(2.0);
    return max(st[l][k],st[r-(1<<k)+1][k]);
}

树状数组

有了线段树，你还会爱我吗?
会的。我们只是正常朋友关系。
可她比我全能，要求比我少，心思比我更好想！
不要再多虑了，你的常数和码量都是她无法比拟的。
还有，你是我心中那个只会单点修改的小傻瓜啊

用途及要求

基础：单点修改+区间查询
扩展：区间修改+查询
树状数组维护的信息及运算要满足结合律且可差分的。（OI-wiki）
如区间和、区间乘、区间异或。

单点修改

原理

原理类似线段树，对半分为很多个小区间，但发现有的区间是可以通过大减小等方式又由其他区间计算而得，可以删去。剩下的区间找规律，发现：$tr_i$ 表示以 $i$ 为右边界，长度为 lowbit(i)=i&-i 的区间和。这样可以计算出任何 $[1,i]$ 的值。

特点

原版支持单点修改+区间查询，复杂度均为 $O(\log n)$
搭配差分即可实现区间修改+单点查询。
实现比线段树简单，常数比线段树小，原理比线段树复杂。

1
2
3
4
5
6
7
8
void add(int i,int x){
    while(i<=n){tr[i]+=x;i+=i&-i;}
}
int query(int i){
    int res=0;
    while(i){res+=tr[i];i-=i&-i;}
    return res;
}

区间修改

这时候就有聪明的小朋友要问了：那我要是想既能区间修改，又能区间查询呢？
直接线段树
查询总比修改简单，所以我们在差分后能区间修改的树状数组基础上改，考虑区间查询。
设原数组 $a$，差分数组 $d$，区间和 $sum$，则有：
$$a_i=\sum_{j=1}^id_j$$
$$sum_k=\sum_{i=1}^ka_i=\sum_{i=1}^k\sum_{j=1}^id_j$$

解法1：

$$\sum_{i=1}^k\sum_{j=1}^id_j=\sum_{j=1}^k\sum_{i=j}^kd_j=\sum_{j=1}^kd_j\times(k-j+1)$$

解法2：

$a_1=d_1$
$a_2=d_1+d_2$
$a_3=d_1+d_2+d_3$
$\dots$
$a_k=d_1+d_2+d_3+\dots+d_k$
不难发现，对 $a$ 求和的话（即竖着加），$d_j$ 出现了 $k-j+1$ 次，结果同解法1。
$$sum_k=\sum_{j=1}^kd_j\times(k-j+1)=(k+1)\sum_{j=1}^kd_j-\sum_{j=1}^kd_j\times j$$
其中 $k$ 是定值，我们发现令 $b_j=d_j\times j$ 的话，两个求和都可以分别用 $d$ 和 $b$ 的树状数组查询，那么 $sum$ 就可求了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void add(int i,int x){
    int k=i; 
    while(i<=n){
        tr1[i]+=x,tr2[i]+=x*k; 
        i+=i&-i;
    }
}
void add(int l,int r,int x){
    add(l,x);add(r+1,-x);
} 
int query(int i){
    int res=0,k=i;
    while(i){
        res+=(k+1)*tr1[i]-tr2[i];
        i-=i&-i;
    }
    return res;
}
int query(int l,int r){
    return query(r)-query(l-1);
}

（函数名重复？引用名言：参数不一样~ ）

线段树

树状数组，你听我解释！！！
即使是万能的线段树，也无法维护你我之间的关系。因为，我们的联系不容得懒惰的标记。

用途及要求

请输入文本
基本啥区间信息都能维护，就是难写。能区间修改，区间查询。

特点

建树 $O(n)$，查询和修改 $O(\log n)$，常数出了名的大，容易被卡。
卡常：喜欢无脑写线段树的小朋友你们好啊，我是卡常，老老实实给我写树状数组或其他方法去吧。

普通线段树+懒惰标记

基本只用修改 tag 函数，其他地方很容易改。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#define ls o<<1
#define rs o<<1|1
struct node{
    int val,lzy;//维护的值和懒惰标记
}tr[N<<2];
void pushup(int o){
    //更新父节点
}
void tag(int o,int l,int r,/*标记*/){
    //打标记+更新值
}
void pushdown(int o,int l,int r){//更新子节点
    int mid=l+r>>1;
    tag(ls,l,mid);
    tag(rs,mid+1,r);
    //重置标记
}
void build(int o,int l,int r){
    if(l==r){
        tr[o].sum=a[l];//初始化
        return; 
    } 
    int mid=l+r>>1;
    build(ls,l,mid);
    build(rs,mid+1,r);
    pushup(o);
} 
void update(int o,int l,int r,int L,int R){
    if(l>=L&&r<=R){
        tag(o,l,r);
        return;
    }
    pushdown(o,l,r);
    int mid=l+r>>1;
    if(L<=mid) update(ls,l,mid,L,R);
    if(R>mid) update(rs,mid+1,r,L,R);
    pushup(o); 
}
int query(int o,int l,int r,int L,int R){
    if(l>=L&&r<=R) return tr[o].val;
    pushdown(o,l,r);
    int mid=l+r>>1,res=0;
    if(L<=mid) res+=query(ls,l,mid,L,R);//合并区间值
    if(R>mid) res+=query(rs,mid+1,r,L,R);
    return res;
}

动态开点