数据结构-1#

并查集#

普通并查集#

1
class UnionFind {
2
public:
3
    vector<int> f;
4
    vector<int> sz;
5
    int cc;
6

7
    UnionFind(int n) : f(n), sz(n), cc(n) {
8
        iota(f.begin(), f.end(), 0);
9
    }
10

11
    int find(int x) {
12
        if (f[x] != x) f[x] = find(f[x]);
13
        return f[x];
14
    }
15

16
    bool merge(int from, int to) {
17
        int x = find(from), y = find(to);
18
        if (x == y) return 0;
19
        f[x] = y;
20
        sz[y] += sz[x];
21
        --cc;
22
        return 1;
23
    }
24
};

带权并查集#

1
//TODO

普通Trie树#

1
int son[N][26], cnt[N], idx = 0;
2

3
void insert(char *str) {
4
    int p = 0;
5
    for (int i = 0; str[i]; ++i) {
6
        int e = str[i] - 'a';
7
        if (!son[p][e]) son[p][e] = ++idx;
8
        p = son[p][e];
9
    }
10
    ++cnt[p];
11
}
12

13
int search(char *str) {
14
    int p = 0;
15
    for (int i = 0; str[i]; ++i) {
16
        int e = str[i] - 'a';
17
        if (!son[p][e]) return 0;
18
        p = son[p][e];
19
    }
20

21
    return cnt[p];
22
}

0-1 Trie树#

1
class Trie {
2
public:
3
    static const int MAXN = 1e4;
4
  int tr[MAXN][2];
5
    int ptr = 0;
6

7
    void insert(int x) {
8
        int p = 0;
9
        for (int i = 31; i >= 0; --i) {
10
      bool c = x >> i & 1;
11
            if (!tr[p][c]) tr[p][c] = ++ptr;
12
            p = tr[p][c];
13
        }
14
    }
15

16
    int find(int x) {
17
        int p = 0, ans = 0;
18
        for (int i = 31; i >= 0; --i) {
19
            bool c = x >> i & 1;
20
            bool b = !c;
21
            if (tr[p][b]) {
22
                ans |= 1 << i;
23
                p = son[p][b];
24
            } else {
25
                p = son[p][c];
26
            }
27
        }
28
        return ans;
29
    }
30
};

线段树#

是个完全二叉树，只适用于聚合函数，例如

f(a, b) = g(f(a), f(b))

其中a,b为区间

普通线段树#

原数组0-base，tree 1- base

取中点为左

设数组元素数量为 $m$ ，树最后一层数量要满足 $2^{n-1} \ge m$ ， $n \ge \lceil \log{m} \rceil + 1 = \lfloor \log_2{(m - 1)} \rfloor + 2 = bit\_width(m-1) + 1$ 需要的结点个数需要满足 $2^{n-1}-1<k\le 2^n - 1$ ，由于1-base完全二叉树有多少结点开多大数组，则取上界开 $(2<<bit\_width(m-1)) - 1$ 大小的数组，实际再+1书写方便

1
class SegmentTree {
2
    int n;
3
    vector<int> tr;
4

5
    // 区间业务
6
    int merge_val(int a, int b) const {
7
        return max(a, b);
8
    }
9

10
    // 维护结点
11
    void maintain(int node) {
12
        tr[node] = merge_val(tr[node * 2], tr[node * 2 + 1]);
13
    }
14

15
    // 建树
16
    void build(int node, int l, int r, const vector<int>& a) {
17
        if (l == r) {
18
            tr[node] = a[l];
19
            return;
20
        }
21

22
        int m = l + r >> 1;
23
        build(node * 2, l, m, a);
24
        build(node * 2 + 1, m + 1, r, a);
25
        maintain(node);
26
    }
27

28
    // 单点更新
29
    void update(int node, int l, int r, int i, int val) {
30
        if (l == r) {
31
            tr[node] = merge_val(tr[node], val);
32
            return;
33
        }
34

35
        int m = l + r >> 1;
36
        if (i <= m) {
37
            update(node * 2, l, m, i, val);
38
        } else {
39
            update(node * 2 + 1, m + 1, r, i, val);
40
        }
41
        maintain(node);
42
    }
43

44
    // 区间查询
45
    int query(int node, int l, int r, int ql, int qr) const {
46
        if (ql <= l && r <= qr) {
47
            return tr[node];
48
        }
49

50
        int m = l + r >> 1;
51
        if (qr <= m) {
52
            return query(node * 2, l, m, ql, qr);
53
        }
54
        if (ql > m) {
55
            return query(node * 2 + 1, m + 1, r, ql, qr);
56
        }
57
        int l_res = query(node * 2, l, m, ql, qr);
58
        int r_res = query(node * 2 + 1, m + 1, r, ql, qr);
59
        return merge_val(l_res, r_res);
60
    }
61

62
    // 查找查找区间最左边的某值
63
    int find(int node, int l, int r, int ql, int qr, int val) const {
64
        if (ql > r || qr < l) return -1;
65
        // if (业务剪枝) return -1;
66
        if (l == r && tr[node] == val) return l;
67

68
        int m = l + r >> 1;
69
        int l_res = find(node * 2, l, m, ql, qr, val);
70
        if (l_res != -1) return l_res;
71
        return find(node * 2 + 1, m + 1, r, ql, qr, val);
72
    }
73

74
public:
75

76
    SegmentTree(const vector<int>& a) : n(a.size()), tr(2 << bit_width(n - 1)) {
77
        build(1, 0, n - 1, a);
78
    }
79

80
    void update(int i, int val) {
81
        update(1, 0, n - 1, i, val);
82
    }
83

84
    int query(int ql, int qr) {
85
        return query(1, 0, n - 1, ql, qr);
86
    }
87

88
    int find(int ql, int qr, int val) const {
89
        return find(1, 0, n - 1, ql, qr, val);
90
    }
91
};

懒线段树#

1
//TODO

持久化线段树#

1
//TODO

树状数组#

用于动态前缀和，+lowbit是往父结点移动，父结点范围包含指定结点范围，故最后需要一直往上到最后，-lowbit是往兄弟结点移动，兄弟结点互不相交，同时可以跨层，把[0,i]拆成了二进制

1
class FenwickTree {
2
public:
3
  int n;
4
    vector<int> tree;
5

6
    FenwickTree(const vector<int>& a) : n((int)a.size() - 1) {
7
        tree = a;
8
        for (int i = 1; i <= n; ++i) {
9
          // 更新父结点的值
10
          int j = i + (i & -i);
11
          if (j <= n) tree[j] += tree[i];
12
        }
13
    }
14

15
    // 前缀和
16
    int presum(int i) {
17
        int s = 0;
18
        while (i > 0) {
19
            s += tree[i];
20
            i &= i - 1;
21
        }
22
        return s;
23
    }
24

25
    // 单点更新
26
    void update(int i, int delta) {
27
      while (i <= n) {
28
        tree[i] += delta;
29
        i += i & -i;
30
      }
31
    }
32

33
    // 区间和
34
    int query(int l, int r) {
35
        return presum(r) - presum(l - 1);
36
    }
37
};

前缀和#

对于

\sum_{i<j} A_i \cdot B_j

可考虑用前缀和优化

因为固定右端 j 时，前面所有贡献都是：

B_j \cdot (A_1 + A_2 + \cdots + A_{j-1})

应用场景#

统计满足顺序关系的二元组、三元组、四元组#

i < j 且满足某种值关系
枚举中间点或右端点
每个点贡献来自“前面多少种选法”乘“当前能接多少种选法”

莫队#

n为数组长度，m为问题长度，S为块大小，询问区间[l, r]

普通实现#

莫队对离线询问进行预处理，从左到右左端点l在同一块的放一起，然后再根据右端点r进行排序（同一块的询问右端点r的位置是任意的）要理解莫队，要把左右指针分开，要每个询问或每个分块来看，在同一块内，在左右指针移动到指定询问区间的时候，右指针大约最多移动n次，有 $\frac{n}{S}$ 块，所以右指针最多移动 $\frac{n^2}{S}$ 次；对于每次询问，左指针大约最多移动S次，左指针最多移动mS次，由于排序把同一块的询问都分一起了，所以右指针移动次数和m无关，只和块数有关。故普通莫队的时间复杂度为 $O(\cfrac{n^2}{S} + mS)$ ，由基本不等式可知，当块大小取 $\frac{n}{\sqrt(m)}$ 时时间复杂度最优。询问遍历到跨块的时候，如果不做奇偶优化右指针会大量回弹，故让奇数块和偶数块的右指针排序方向是相反的则可以减少右指针移动次数

具体移动过程细节参照普通莫队算法 - OI Wiki

莫队区间的移动过程，就相当于加入了 $[1,r]$ 的元素，并删除了 $[1,l-1]$ 的元素。因此：

对于 $l \le r$ 的情况， $[1,l-1]$ 的元素相当于被加入了一次又被删除了一次， $[l,r]$ 的元素被加入一次， $[r+1,+\infty)$ 的元素没有被加入。这个区间是合法区间。

对于 $l=r+1$ 的情况， $[1,r]$ 的元素相当于被加入了一次又被删除了一次， $[r+1,+\infty)$ 的元素没有被加入。这时这个区间表示空区间。

对于 $l>r+1$ 的情况， $[r+1,l-1]$ （这个区间非空）的元素被删除了一次但没有被加入，因此这个元素被加入的次数是负数。

因此，如果某时刻出现 $l>r+1$ 的情况，那么会存在一个元素，它的加入次数是负数。这在某些题目会出现问题，例如我们如果用一个 set 维护区间中的所有数，就会出现「需要删除 set 中不存在的元素」的问题。
代码中的四个 while 循环一共有 $4!=24$ 种排列顺序。不妨设第一个循环用于操作左端点，就有以下 $12$ 种排列（另外 $12$ 种是对称的）。下表列出了这 $12$ 种写法的正确性，还给出了错误写法的反例。

循环顺序正确性反例或注释
l--,l++,r--,r++ 错误 $l<r<l'<r'$
l--,l++,r++,r-- 错误 $l<r<l'<r'$
l--,r--,l++,r++ 错误 $l<r<l'<r'$
l--,r--,r++,l++ 正确证明较繁琐
l--,r++,l++,r-- 正确
l--,r++,r--,l++ 正确
l++,l--,r--,r++ 错误 $l<r<l'<r'$
l++,l--,r++,r-- 错误 $l<r<l'<r'$
l++,r++,l--,r-- 错误 $l<r<l'<r'$
l++,r++,r--,l-- 错误 $l<r<l'<r'$
l++,r--,l--,r++ 错误 $l<r<l'<r'$
l++,r--,r++,l-- 错误 $l<r<l'<r'$
全部 $24$ 种排列中只有 $6$ 种是正确的，其中有 $2$ 种的证明较繁琐，这里只给出其中 $4$ 种的证明。
这 $4$ 种正确写法的共同特点是，前两步先扩大区间（l-- 或 r++），后两步再缩小区间（l++ 或 r--）。这样写，前两步是扩大区间，可以保持 $l \le r+1$ ；执行完前两步后， $l \le l' \le r' \le r$ 一定成立，再执行后两步只会把区间缩小到 $[l',r']$ ，依然有 $l \le r+1$ ，因此这样写是正确的。

音乐

音乐

数据结构-1#

并查集#

普通并查集#

带权并查集#

普通Trie树#

0-1 Trie树#

线段树#

普通线段树#

懒线段树#

持久化线段树#

树状数组#

前缀和#

应用场景#

统计满足顺序关系的二元组、三元组、四元组#

莫队#

普通实现#

文章分享

评论区

音乐

目录

音乐

音乐

11-数据结构-1

数据结构-1#

并查集#

普通并查集#

带权并查集#

普通Trie树#

0-1 Trie树#

线段树#

普通线段树#

懒线段树#

持久化线段树#

树状数组#

前缀和#

应用场景#

统计满足顺序关系的二元组、三元组、四元组#

莫队#

普通实现#

文章分享

评论区

音乐

目录