Decade
Data Structure Algorithm
Zhongjun Qiu 元婴开发者
  2022-12-31 20:48:00   2025-06-01 17:39:25    4.3k Words  20 Mins  

数据结构与算法的常见应用，涵盖并查集、树状数组、线段树、ST表和分块算法等。涉及并查集的路径压缩与秩压缩优化，树状数组的区间查询与更新操作，线段树的区间求和与区间最值查询，ST表的倍增技术用于区间最值查询等。

并查集

并查集是一种树形的数据结构，它用于处理一些不交集的 合并 及 查询 问题。 它支持两种操作：

  • 查找（Find）：确定某个元素处于哪个子集；
  • 合并（Union）：将两个子集合并成一个集合。

并不能提供删除操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int[] father;
int[] rank; //秩压缩
UnionSet(int n){
    father = new int[n];
    rank = new int[n];
    for (int i = 0;i < n;i++) father[i] = i; //初始化 每个i肯定在它本身所对应的集合中
}
void join(int x, int y){
    x = find(x); y = find(y);
    if (x != y){
        if (rank[x] > rank[y]) father[y] = x;
        else{
            if (rank[x] == rank[y]) rank[y]++;
            father[x] = y;
        }
    }// 简单点 直接 father[x] = y;
}
int find(int x){
    if (x == father[x]) return x;
    return father[x] = find(father[x]); //路径压缩
}

树状数组

单点修改 区间查询

1
2
3
4
5
6
7
8
9
10
11
12
13
static long[] tr; //树状数组 （不是原数组）
static int lowbit(int x){
    return x & -x;
}
static void add(int idx, int w){ //原数组a[idx] += w;
    for (int i = idx;i <= n;i += lowbit(i)) tr[i] += w;
}
static long sum(int idx){ //求原数组a[1]+a[2]+...+a[idx]和
    long res = 0;
    for (int i = idx;i > 0;i -= lowbit(i)) res += tr[i];
    return res;
}
System.out.println(sum(r)-sum(l-1)); //求原数组a[l]+a[l+1]+...+a[r]和

add时间复杂度

sum时间复杂度

区间修改 单点查询

1
2
3
4
5
6
7
static int[] tr, ori; //tr维护的是ori（原数组）的差分数组
static int lowbit(int x){...}
static void add(int idx, int w){...}
static long sum(int idx){...}
for (int i = 1;i <= n;i++) add(i, ori[i]-ori[i-1]); //初始化差分数组
add(l, w); add(r+1, -w); //ori区间l~r上都加上w
System.out.println(sum(idx)); //计算ori[idx]

区间修改 区间查询

位置p的前缀和 =

在等式最右侧的式子 中， d[1] 被用了 p 次， d[2] 被用了 p − 1 次…..那么我们可以写出: 位置p的前缀和 =

那么我们可以维护两个差分数组的前缀和（d[i]是a[i]的差分数组）: 一个数组是 sum 1[i] = ∑d[i] ， 另一个数组是 sum 2[i] = ∑d[i] * i 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
static long[] tr1, tr2; //对应上面的sum1[], sum2[]
static int[] ori;
static int lowbit(int x){...}
static void add(int idx, long w){
    for (int i = idx;i <= n;i += lowbit(i)){
        tr1[i] += w;
        tr2[i] += w*idx; //不是 w*i
    }
}
static long sum(int idx){ //求ori区间 1~idx 的和
    long res = 0;
    for (int i = idx;i > 0;i -= lowbit(i)){
        res += (idx+1)*tr1[i]-tr2[i]; //不是 (i+1)*tr[1]
    }
    return res;
}
for (int i = 1;i <= n;i++) add(i, ori[i]-ori[i-1]); //初始化差分数组
add(l, w); add(r+1, -w); //ori区间l~r上都加上w
System.out.println(sum(r)-sum(l-1)); //求原数组ori[l]+ori[l+1]+...+ori[r]和

最值问题

树状数组 C[i] 所包含的区间[i − lowbit(i) + 1, i], 其中区间的个数是 个, C[i] 一定包含A[i]

树状数组下标都从1开始

image-20250601173428110 
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
static void update(int x) {
    for (int i = x;i <= n;i += lowbit(i)){
        tr[i] = ori[i];·
        for (int j = 1;j < lowbit(i);j <<= 1) tr[i] = max(tr[i], tr[i-j]);
    }
}
static int query(int l, int r){
    int ans = ori[r];
    while (l <= r){
        ans = max(ans, ori[r--]);
        while (r-lowbit(r) >= l){
            ans = max(ans, tr[r]);
            r -= lowbit(r);
        }
    }
    return ans;
}
public static void main(String[] args) throws Exception{
    for (int i = 1;i <= n;i++){
        ori[i] = nextInt();//初始化
        update(i);
    }
    while (m-- > 0){
        io = in.readLine().split(" ");
        char ops = io[0].charAt(0);
        int x = Integer.parseInt(io[1]), y = Integer.parseInt(io[2]);
        if (ops == 'U'){
            ori[x] = y;// 更新 首先更新原数组值 （把x处的值变成y）
            update(x);
        }
        else System.out.println(query(x, y));
    }
}

求解GCD，LCM等其他问题只需要把里面max()换成GCD()就行了

项链

线段树

  • 求和基本操作

线段树将每个长度不为 的区间划分成左右两个区间递归求解，把整个线段划分为一个树形结构，通过合并左右两区间信息来求得该区间的信息。 有个大小为 5 的数组 a = {10, 11, 12, 13, 14}，要将其转化为线段树，有以下做法：设线段树的根节点编号为 1，用数组d来保存我们的线段树， d[i]用来保存线段树上编号为i的节点的值（这里每个节点所维护的值就是这个节点所表示的区间总和）。

image-20250601173516107 
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
// f[i]:以i为根对应的区间和 v[i]:表示以i为根对应的区间是否要修改 a[i]:原数组
static long[] f = new long[N], v = new long[N], a = new long[M];
static void build(int k, int l, int r){
    if (l == r){
        f[k] = a[l];
        return;
    }
    int m = l+r >> 1;
    build(k*2, l, m);
    build(k*2+1, m+1, r);
    f[k] = f[k*2]+f[k*2+1];
}
static void down(int k, int l, int r, int m){
    if (v[k] == 0) return;
    f[k*2] += v[k]*(m-l+1);
    f[k*2+1] += v[k]*(r-m); //更新下一层f
    v[k*2] += v[k]; 
    v[k*2+1] += v[k]; //更新下一层标记
    v[k] = 0; //这一层标记清0
}
static void add(int k, int l, int r, int s, int t, long w){
    if (s <= l && r <= t){
        f[k] += w*(r-l+1);
        v[k] += w;
        return;
    }
    int m = l+r >> 1;
    down(k, l, r, m);
    if (s <= m) add(k*2, l, m, s, t, w);
    if (t > m) add(k*2+1, m+1, r, s, t, w);
    f[k] = f[k*2] + f[k*2+1];
}
static long sum(int k, int l, int r, int s, int t){
    if (s <= l && r <= t) return f[k];
    int m = l+r >> 1;
    down(k, l, r, m);
    long res = 0;
    if (s <= m) res += sum(k*2, l, m, s, t);
    if (t > m) res += sum(k*2+1, m+1, r, s, t);
    return res;
}
build(1, 1, n); //建树
add(1, 1, n, x, y, w); //原数组[x, y]上加w
sum(1, 1, n, x, y)； //原数组[x, y]求和

关于线段树的空间：d = new int[n <  < 2] 开四倍空间

再提供一个C++版本的动态开点版本：

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
48
49
50
51
52
struct node{
    int val = 0, add = 0;
    node *left = nullptr, *right = nullptr;
};
void down(node* cur, int l, int r, int m){
    int t = cur->add;
    if (cur->left == nullptr) cur->left = new node();
    if (cur->right == nullptr) cur->right = new node();
    cur->left->val += t*(m-l+1);
    cur->right->val += t*(r-m);
    cur->left->add += t;
    cur->right->add += t; 
    cur->add = 0;
}
void upd(node* cur, int l, int r, int s, int t, int val){
    if (s <= l && r <= t){
        cur->val += val*(r-l+1);
        cur->add += val;
        return;
    }
    int m = l+r >> 1;
    down(cur, l, r, m);
    if (s <= m) upd(cur->left, l, m, s, t, val);
    if (m+1 <= t) upd(cur->right, m+1, r, s, t, val);
    cur->val = cur->left->val+cur->right->val;
}
int qry(node* cur, int l, int r, int s, int t){
    if (s <= l && r <= t) return cur->val;
    int m = l+r >> 1, res = 0;
    down(cur, l, r, m);
    if (s <= m) res += qry(cur->left, l, m, s, t);
    if (m+1 <= t) res += qry(cur->right, m+1, r, s, t);
    return res;
}

// example
node* root;
int MAXV = 1e9;
NumArray(vector<int>& nums) {
    root = new node();
    for (int i = 1;i <= nums.size();i++){
        upd(root, 1, MAXV, i, i, nums[i-1]);
    }
}

void update(int index, int val) {
    upd(root, 1, MAXV, index+1, index+1, val);
}

int sumRange(int left, int right) {
    return qry(root, 1, MAXV, left+1, right+1);
}

ST表(离线区间查询)

ST表（Sparse Table，稀疏表）是一种简单的数据结构，主要用来解决RMQ（Range Maximum/Minimum Query，区间最大/最小值查询）问题。它主要应用倍增的思想，可以实现O(nlog n)预处理、 O(1)查询。

主要思想：倍增

ST表板子

F[i][j]:原数组区间[i, i + 2j − 1]的最值

  • 预处理原理 f[j][i] = Max(f[j][i-1], f[j+(1<<(i-1))][i-1]);
image-20250601173733251
  • 查询原理 res = Math.max(f[l][s], f[r-(1<<s)+1][s]);

需要找到两个[l, r]的子区间，它们的并集恰是 [l, r](可以相交)。

image-20250601173757465 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
static int[][] f = new int[N][17]; //第二维的大小根据数据范围决定，不小于log2(N)
static int[] log2 = new int[N];
private static void init() {
    for (int i = 2;i <= n;i++) log2[i] = log2[i/2]+1; //对log2也进行一次递推的预处理
    for (int i = 1;i <= n;i++) f[i][0] = A[i]; //初始化 区间[i, i]最值就是A[i]本身
    for (int i = 1;i <= 17;i++){
        for (int j = 1;j + (1<<i)-1 <= n;j++){
            f[j][i] = Math.max(f[j][i-1], f[j+(1<<(i-1))][i-1]);
        }
    }
}
private static int query(int l, int r) {
    int s = log2[r-l+1];
    int res = Math.max(f[l][s], f[r-(1<<s)+1][s]);
    return res;
}

其实ST表不仅能处理最大值/最小值，凡是符合结合律且可重复贡献的信息查询都可以使用ST表高效进行。什么叫可重复贡献呢？设有一个二元运算 f(x, y)，满足 f(a, a) = a，则f(x, y)是可重复贡献的。显然最大值(max)、最小值(min)、最大公因数(GCD)、最小公倍数(LCM)、按位或(|)、按位与(&)都符合这个条件。可重复贡献的意义在于，可以对两个交集不为空的区间进行信息合并。区间和就不具有这个性质，求区间和的时候采用的预处理区间重叠了，则会导致重叠部分被计算两次；即f(a, a) = 2a。

分块

P3372 【模板】线段树 1 - 洛谷 | 计算机科学教育新生态

传说中的根号算法，比线段树和树状数组好理解，优雅的暴力。

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
48
49
50
51
static int n, m, bel[]=new int[N];
static int sq, st[]=new int[N], ed[]=new int[N];
static long a[]=new long[N], sum[]=new long[N], f[]=new long[N];
static void update(int l, int r, long v){
    // 当x与y在同一块内时，直接暴力修改原数组和sum数组：
    if (bel[l] == bel[r]){
        for (int i = l;i <= r;i++){
            a[i] += v;
            sum[bel[i]] += v;
        }
    }else{ // 否则，先暴力修改左右两边的零散区间：
        for (int i = l;i <= ed[bel[l]];i++){
            a[i] += v;
            sum[bel[i]] += v;
        }
        for (int i = st[bel[r]];i <= r;i++){
            a[i] += v;
            sum[bel[i]] += v;
        } // 对中间的整块打上标记 （与线段树的打标记类似）
        for (int i = bel[l] + 1; i < bel[r]; ++i) f[i] += v;
    }
}
static long query(int l, int r){
    long ans = 0;
    if (bel[l] == bel[r]){ // 左右两边在同一块，直接暴力计算区间和。
        for (int i = l;i <= r;i++) ans += a[i];
    }else{ // 否则，先暴力计算左右两边零碎块
        for (int i = l;i <= ed[bel[l]];i++) ans += a[i]+f[bel[i]];
        for (int i = st[bel[r]];i <= r;i++) ans += a[i]+f[bel[i]];
        // 处理中间整块 （不要忘了把标记值也加上去）
        for (int i = bel[l] + 1; i < bel[r]; ++i) ans += sum[i]+f[i]*(ed[i]-st[i]+1);
    }
    return ans;
}
static void solve() throws Exception {
    sq = (int)Math.sqrt(n); //获得块数
    for (int i = 1;i <= sq;i++){
        st[i] = n/sq*(i-1)+1; // st[i]表示i号块的第一个元素的下标
        ed[i] = n/sq*i; // ed[i]表示i号块的最后一个元素的下标
    }
    ed[sq] = n; 
    //数组的长度并不一定是一个完全平方数，所以这样下来很可能会漏掉一小块，我们把它们纳入最后一块中。
    for (int i = 1; i <= sq; ++i){
        for (int j = st[i]; j <= ed[i]; ++j){
            bel[j] = i; //为每个元素确定它所归属的块：
            sum[i] += a[j]; //预处理每个块中所有元素的和
        }
    }
    update(l, r, x); //[l, r]加上x
    query(l, r); //查询[l, r]和
}

算算时间复杂度

首先看查询操作:

  • 若 l 和 r 在同一个块内，直接暴力求和即可，因为块长为 s ，因此最坏复杂度为 O(s) 。

  • 若 l 和 r 不在同一个块内，则答案由三部分组成：以 l 开头的不完整块，中间几个完整块，以 r 结尾的不完整块。对于不完整的块，仍然采用上面暴力计算的方法，对于完整块，则直接利用已经求出的 bi 求和即可。这种情况下，最坏复杂度为 。

接下来是修改操作：

  • 若 l 和 r 在同一个块内，直接暴力修改即可，因为块长为 s ，因此最坏复杂度为 O(s) 。

  • 若 l 和 r 不在同一个块内，则需要修改三部分：以 l 开头的不完整块，中间几个完整块，以 r 结尾的不完整块。对于不完整的块，仍然是暴力修改每个元素的值（别忘了更新区间和 bi ）， 对于完整块，则直接修改 bi 即可。这种情况下，最坏复杂度和仍然为 。

利用均值不等式可知，当 ，即 时，单次操作的时间复杂度最优，为 。

对于数组长度为 n，查询和修改次数为 m，时间复杂度为

莫队

基于分块思想，复杂度为 。

一般来说，如果可以在 O(1) 内从 [l,r] 的答案转移到 [l−1,r] 、 [l+1,r] 、 [l,r−1] 、 [l,r+1] 这四个与之紧邻的区间的答案，则可以考虑使用莫队。

SPOJ DQUERY - D-query

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
static int[] a = new int[N], cnt = new int[N], ans = new int[N];
static int[][] q = new int[N][3];
static void add(int p){
    if (cnt[a[p]]++ == 0) cur++;
}
static void del(int p){
    if (--cnt[a[p]] == 0) cur--;
}
static void solve() throws Exception{
    n = ni(); sq = (int)Math.sqrt(n);
    for (int i = 1;i <= n;i++) a[i] = ni();
    m = ni();
    for (int i = 1;i <= m;i++){
    q[i][0] = ni();
    q[i][1] = ni();
    q[i][2] = i;
    }
    Arrays.sort(q, 1, m+1, (x, y)->{
        if (x[0]/sq == y[0]/sq){
            if (x[0]/sq % 2 == 1) return x[1]/sq-y[1]/sq;
            return y[1]/sq-x[1]/sq;
        }
        return x[0]/sq - y[0]/sq;
    });
    for (int i = 1;i <= m;i++){
        int s = q[i][0], t = q[i][1], dx = q[i][2];
        while (l > s) add(--l);
        while (l < s) del(l++);
        while (r > t) del(r--);
        while (r < t) add(++r);
        ans[dx] = cur;
    }
    for (int i = 1;i <= m;i++) out.println(ans[i]);
}

线性基

性质

  1. 原数列里的任何一个数都可以通过线性基里的数异或表示出来
  2. 线性基里任意一个子集的异或和都不为0
  3. 一个数列可能有多个线性基，但是线性基里数的数量一定唯一，而且是满足性质一的基础上最少的
  4. 线性基中元素互相异或，异或集合不变。

用处

  1. 快速查询一个数是否可以被一堆数异或出来
  2. 快速查询一堆数可以异或出来的最大/最小值
  3. 快速查询一堆数可以异或出来的第k大值
  • 线性基序列构造
1
2
3
4
5
6
7
8
9
10
11
12
static long[] d = new long[63]; //大小 = Log2(X) x是原序列中最大的数
static void add(long x) {
    for (int i = 62;i >= 0;i--){
        if ((x >> i & 1) == 0) continue;
        // x第i位是1  d[i]没有插入数,则d[i] = x;否则x与插入的数异或,继续循环.
        if (d[i] == 0){ 
            d[i] = x; break;
        }
        x ^= d[i];
    }
    if (x != 0) ++cnt; // cnt表示原序列的数插入线性基序列中的数量 就是线性基序列有效长度
}
  • 查询一个元素是否可以被原序列中的数异或出来
1
2
3
4
5
Boolean ask(long x) {
	for(R int i=62;i>=0;i--) 
		if((x >> i & 1) == 1) x ^= d[i];
	return x==0;
}

前置知识：a ^ b ^ c = 0 ⇒ a ^ b = c且a ^ c = b且b ^ c = a

对于一个数x不能成功插入线性基。显然就是它在尝试插入时异或若干个数之后变成了0。

则有：x∧d[a]∧d[b]∧d[c]∧… = 0 即：d[a]∧d[b]∧d[c]∧… = x

说明x肯定能由原序列中数异或得到。

  • 求原序列异或最大值
1
2
3
4
5
static long getMax() {
    long ans = 0;
    for (int i = 62;i >= 0;i--) ans = Math.max(ans, ans^d[i]);
    return ans;
}
  • 求原序列异或最小值
1
2
3
4
5
6
7
8
9
static long getMax() {
 //如果插入的数量和原序列数量不等 那么说明肯定存在一个数能由其他数表示出,于是这些数异或肯定等于0。
    if (cnt != n) return 0;
    long ans = 0;
    for (int i = 0;i <= 63 && ans == 0;i++){
        if (d[i] != 0) ans = d[i]; //直接找一个最小的数就行 因为 a^x >= a; x为任意正整数
    }
    return ans;
}
  • 求原序列异或第k小值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
static void rebuild() {
    for(int i = 62;i >= 0;i--) {
        for (int j = i - 1; j >= 0; j--) {
            if ((d[i]>>j & 1) == 1) d[i] ^= d[j];
        }
    }
    for(int i = 0;i <= 62;i++) if(d[i]!=0) p[m++]=d[i];
    // m为线性基的个数
}
static long Kmin(int k){
    //m与n不同 说明原序列中存在异或和为0的序列
    //下面求第k小是不包含0的 所以要把0排除 即要求的第k小其实是k-1小
    if (m != n) --k; 
    if (k == 0) return 0; //k等于0 说明求的第1小且最小值为0
    //m个线性基都有两个状态 选或不选 但全不选是不合题意的要减去1 总共有2^m-1个可能的异或值
    if (k >= (1L << m)) return -1; 
    long res = 0;
    for (int i = 0;i <= 62;i++) if ((k>>i & 1) == 1) res ^= p[i];
    return res;
}
Data Structure Algorithm
2022/12/31/Data-Structure-Algorithm/
Author
Zhongjun Qiu
Published
2022-12-31 20:48
License
 REWARD AUTHOR
 Comments
Comment plugin failed to load
Loading comment plugin
  1. 并查集
  2. 树状数组
    1. 单点修改 区间查询
    2. 区间修改 单点查询
    3. 区间修改 区间查询
    4. 最值问题
  3. 线段树
  4. ST表(离线区间查询)
  5. 分块
  6. 莫队
  7. 线性基
  1. 并查集
  2. 树状数组
    1. 单点修改 区间查询
    2. 区间修改 单点查询
    3. 区间修改 区间查询
    4. 最值问题
  3. 线段树
  4. ST表(离线区间查询)
  5. 分块
  6. 莫队
  7. 线性基