Songbirds


春

算法模板

  • ~33.92K 字
  1. 1. 1.树状数组
    1. 1.1. 1.单点修改-区间求和
    2. 1.2. 2.区间修改-单点求值
    3. 1.3. 3.逆序对问题
  2. 2. 2.线段树
    1. 2.1. 1.区间修改-区间查询
    2. 2.2. 2.乘法-加法操作
  3. 3. 3.最小生成树
    1. 3.1. 1.kruskal算法
    2. 3.2. 2.prim算法
  4. 4. 4.N叉树的最近公共祖先
    1. 4.1. 1.倍增
    2. 4.2. 2.TarjanLCA

承接自经典算法的笔记。

1.树状数组

又名fenwickTree，国内又名BinaryIndexTree（名称很形象，与二进制有关）。树状数组无法解决RMQ问题，因为区间不可重复贡献，能解决的问题有：单点修改-区间求和、区间修改-区间求和、逆序对问题。

树状数组中每一个位置都是保存的一段区间的和。对原数组某一个下标x加上一个值，会影响到树状数组中该下标x，以及该下标x+lowbit(x)的位置，一直到最后一位。如图，红色值为树状数组的下标，例如下标8处的值，等于其所有子类的相加的和：preSum[8]=preSum[4]+preSum[6]+preSum[7]+nums[8]preSum[8] = preSum[4] + preSum[6] + preSum[7] + nums[8]（注意红色的连线）。下标5的值的变更会影响到下标5、下标6、下标8处的值（注意红色的连线），即子节点值变更会影响到父节点的变更。这些下标都是根据lowbit得来

如果对原数组下标为5加上1，则如下二叉树部分，对下标为5的加上1，再对5+lowbit(5) = 6下标加上1，再对6 + lowbit(6) = 8下标加上1，接下来会超过数组边界，所以停止操作。

如果求区间[x, y]的值，则可以转化为求区间[1, y] - [1, x - 1]的值。我们从树状数组上往下查，假设要查[1, 6]的值，先查树状数组中6的值，在查6-lowbit(6) = 4 的值，接着4-lowbit(4) = 0，超出操作范围，停止操作。将这两者值相加的到区间[1, 6]的值。

fenwickTree

1.单点修改-区间求和

模板题：P3374 【模板】树状数组 1 - 洛谷

如题，已知一个数列，你需要进行下面两种操作：

  • 将某一个数加上x
  • 求出某区间每一个数的和
单点修改-区间求和
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
import java.io.*;
import java.util.StringTokenizer;

public class Main {
	
    // 用来存储树状数组
    private static int[] prevSumArr;

    public static void main(String[] args) throws IOException {
        // Scanner sc = new Scanner(new BufferedInputStream(System.in));
        PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));

        int n = rd.nextInt(); // 数列长度为n
        int m = rd.nextInt(); // m次操作（m行）
        // int[] arr = new int[n];
        prevSumArr = new int[n + 1];
        // 初始化树状数组，下标从1开始
        for (int i = 1; i <= n; i++) {
            int v = rd.nextInt();
            add(i, v);
        }

        for (int i = 0; i < m; i++) {
            int a = rd.nextInt();
            int x = rd.nextInt();
            int y = rd.nextInt();

            // 1 add
            // 2 query
            if (a == 1) {
                add(x, y);
            } else {
                pw.println(ask(x, y));
            }
        }
        pw.flush(); 
    }

    // bitree的实际下标是从1开始的
    public static void add(int x, int v) {
        for (; x <= prevSumArr.length - 1; x += (x & -x)) {
            prevSumArr[x] += v;
        }
    }

    public static int ask(int x) {
        int ans = 0;
        for (; x > 0; x -= (x & -x)) {
            ans += prevSumArr[x];
        }
        return ans;
    }
	
    // ask(y) 表示下标y到1的和，ask(x - 1) 表示下标x-1到下标1的和，差值即为区间[x, y]和
    public static int ask(int x, int y) {
        return ask(y) - ask(x - 1);
    }


    static class rd {
        static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        static StringTokenizer tokenizer = new StringTokenizer("");

        // nextLine()读取字符串
        static String nextLine() throws IOException {
            return reader.readLine();
        }

        // next()读取字符串
        static String next() throws IOException {
            while (!tokenizer.hasMoreTokens()) {
                tokenizer = new StringTokenizer(reader.readLine());
            }
            return tokenizer.nextToken();
        }

        // 读取一个int型数值
        static int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        // 读取一个double型数值
        static double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }

        // 读取一个long型数值
        static long nextLong() throws IOException {
            return Long.parseLong(next());
        }
        
    }
}

2.区间修改-单点求值

模板题：P3368 【模板】树状数组 2 - 洛谷

把原数组先进行差分，再以此创建树状数组。则对原数组[x, y] 处加1，则变成对差分数组下标x处加1，下标y+1处-1。（若y=n，y+1则会超过树状数组最大下标n越界，会有问题吗？不会，因为add的时候限制了小于n，不会导致越界，丢弃掉差分数组越界那一部分，对差分数组还原无影响）

如题，已知一个数列，你需要进行下面两种操作：

  1. 将某区间每一个数加上x；
  2. 求出某一个数的值。
区间修改-区间求和
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
import java.io.*;
import java.util.StringTokenizer;

public class Main {

    private static int[] prevSumArr;

    public static void main(String[] args) throws IOException {
        // Scanner sc = new Scanner(new BufferedInputStream(System.in));
        PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));

        int n = Rd.nextInt(); // 数列长度为n
        int m = Rd.nextInt(); // m次操作（m行）
        // int[] arr = new int[n];
        prevSumArr = new int[n + 1];

        // 区间修改的树状数组，维护的是一个差分（即对差分后的数组构建树状数组）
        // 初始化树状数组
        int last = 0;
        for (int i = 1; i <= n; i++) {
            int v = Rd.nextInt();
            // v - last 差分
            add(i, v - last);
            last = v;
        }

        for (int i = 0; i < m; i++) {
            int a = Rd.nextInt();
            if (a == 1) {
                // 区间加值
                int x = Rd.nextInt();
                int y = Rd.nextInt();
                int v = Rd.nextInt();
                add(x, y, v);
            } else {
                // 区间求值
                int x = Rd.nextInt();
                pw.println(ask(x));
            }
        }
        pw.flush();
    }

    // bitree的实际下标是从1开始的
    public static void add(int x, int v) {
        for (; x <= prevSumArr.length - 1; x += (x & -x)) {
            prevSumArr[x] += v;
        }
    }

    // 对差分数组加，等于x加上v，y + 1减去v
    public static void add(int x, int y, int v) {
        // 对下标x处，加上v
        add(x, v);
        // 对下标y+1处，减去v
        add(y + 1, -v);
    }

    // x是第x个，表示原数组中下标x-1
    public static int ask(int x) {
        int ans = 0;
        for (; x > 0; x -= (x & -x)) {
            ans += prevSumArr[x];
        }
        return ans;
    }

    public static int ask(int x, int y) {
        return ask(y) - ask(x - 1);
    }

    static class Rd {
        static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        static StringTokenizer tokenizer = new StringTokenizer("");

        // nextLine()读取字符串
        static String nextLine() throws IOException {
            return reader.readLine();
        }

        // next()读取字符串
        static String next() throws IOException {
            while (!tokenizer.hasMoreTokens()) {
                tokenizer = new StringTokenizer(reader.readLine());
            }
            return tokenizer.nextToken();
        }

        // 读取一个int型数值
        static int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        // 读取一个double型数值
        static double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }

        // 读取一个long型数值
        static long nextLong() throws IOException {
            return Long.parseLong(next());
        }
        
    }
}

3.逆序对问题

模板题：LCR 170. 交易逆序对的总数 - 力扣（LeetCode）

在股票交易中，如果前一天的股价高于后一天的股价，则可以认为存在一个「交易逆序对」。请设计一个程序，输入一段时间内的股票交易记录 record，返回其中存在的「交易逆序对」总数。

此题目，除了使用分治算法外，还可以使用树状数组求解。

首先，对原数组nums进行离散化，这里使用排序，排序后得到数组sortArr，就知道每个数离散后的下标。然后按照从左到右的顺序遍历原数组nums，遍历到数num的时候，查找数num在sortArr中最小的下标left和最大right的下标，查找树装数组中比num大的数（即大于right计数）即为答案。然后在left+1计数1，表示添加了一个数num。

逆序对问题
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
class Solution {
    // 树状数组
    private int[] tree;

    public int reversePairs(int[] record) {
        // 第0位不使用，加1
        this.tree = new int[record.length + 1];
        // 离散化
        int[] sortArr = Arrays.copyOf(record, record.length);
        Arrays.sort(sortArr);

        int ans = 0;
        for (int i = 0; i < record.length; i++) {
            int v = record[i];
            // 查找到num（v）的左端映射、右端映射
            int left = binLeftSearch(sortArr, v);
            int right = binRightSearch(sortArr, v);
            // 在树状数组中查找比离散后right大的数量（right+1为树状数组加1后映射，再加1就是比right大的）
            ans += ask(right + 2, tree.length - 1);
            // 将left计数1（left+1是树状数组映射加1）
            add(left + 1, 1);
        }
        return ans;
    }

    private int binRightSearch(int[] sortArr, int v) {
        int left = 0;
        int right = sortArr.length - 1;
        while (left < right) {
            int mid = left + right + 1 >> 1;
            if (sortArr[mid] <= v) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }

    private int binLeftSearch(int[] sortArr, int v) {
        int left = 0;
        int right = sortArr.length - 1;
        while (left < right) {
            int mid = left + right >> 1;
            if (check(sortArr, mid, v)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    private boolean check(int[] sortArr, int mid, int v) {
        return sortArr[mid] >= v;
    }

    // 在第x位加上v
    public void add(int x, int v) {
        for (; x < tree.length; x += x & (-x)) {
            tree[x] += v;
        }
    }

    public int ask(int x) {
        int ans = 0;
        for (; x >= 1; x -= x & (-x)) {
            ans += tree[x];
        }
        return ans;
    }

    public int ask(int x, int y) {
        return ask(y) - ask(x - 1);
    }
}

2.线段树

之前在经典算法中写过线段树的笔记，所以你知道我拖延了多久了吧（懒癌晚期实锤），那段笔记只记叙了单点修改，区间查询。

1.区间修改-区间查询

模板题目：P3372 【模板】线段树 1 - 洛谷

如题，已知一个数列，你需要进行下面两种操作：

  1. 将某区间每一个数加上 k。
  2. 求出某区间每一个数的和。

如果区间修改时，逐个去修改，单独的修改部分就会O(N2lgN)O(N^2lgN)的，所以采用懒标记法，节点类多了一个lazy标记，在修改、查询的时候，将标记下传，这样就均摊了时间。同时区间修改-区间查询可以完全替代单点修改-区间查询，因为单点修改，等于修改的区间的左右相同。

区间修改-区间查询
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
import java.io.*;
import java.math.BigInteger;
import java.util.StringTokenizer;

public class Main {

    private static long[] nums;
    private static TreeNode[] tree;
    private static int n;

    public static void main(String[] args) throws IOException {
        Fr sc = new Fr();
        PrintWriter pw = new PrintWriter(new BufferedOutputStream(System.out));

        int n = sc.nextInt();
        int m = sc.nextInt();
        tree = new TreeNode[n * 4];
        nums = new long[n];
        // 初始化
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }
        build(0, n - 1, 1);
        for (int i = 0; i < m; i++) {
            int op = sc.nextInt();
            // 题目的下标从1开始
            int x = sc.nextInt() - 1;
            int y = sc.nextInt() - 1;
            if (op == 1) {
                int k = sc.nextInt();
                change(x, y, k, 1);
            } else {
                long ans = ask(x, y, 1);
                pw.println(ans);
            }
        }
        pw.flush();
    }

    private static long ask(int left, int right, int p) {
        if (left <= tree[p].left && tree[p].right <= right) {
            return tree[p].sum;
        }
        // 标记下传
        pushDown(p);
        int mid = tree[p].left + tree[p].right >> 1;
        long ans = 0;
        if (left <= mid) {
            ans += ask(left, right, p * 2);
        }
        if (right > mid) {
            ans += ask(left, right, p * 2 + 1);
        }
        return ans;
    }

    private static void change(int left, int right, int val, int p) {
        if (left <= tree[p].left && tree[p].right <= right) {
            tree[p].sum += (long) val * (tree[p].right - tree[p].left + 1);
            tree[p].lazy += val;
            return;
        }
        // 标记下传
        pushDown(p);
        int mid = tree[p].left + tree[p].right >> 1;
        if (left <= mid) {
            change(left, right, val, p * 2);
        }
        if (right > mid) {
            change(left, right, val, p * 2 + 1);
        }
        pushUp(p);
    }

    private static void build(int left, int right, int p) {
        tree[p] = new TreeNode(left, right);
        if (left == right) {
            tree[p].sum = nums[left];
            return;
        }
        int mid = left + right >> 1;
        build(left, mid, p * 2);
        build(mid + 1, right, p * 2 + 1);
        pushUp(p);
    }

    private static void pushDown(int p) {
        if (tree[p].lazy != 0) {
            tree[p * 2].sum += tree[p].lazy * (tree[p * 2].right - tree[p * 2].left + 1);
            tree[p * 2 + 1].sum += tree[p].lazy * (tree[p * 2 + 1].right - tree[p * 2 + 1].left + 1);
            // 标记下传
            tree[p * 2].lazy += tree[p].lazy;
            tree[p * 2 + 1].lazy += tree[p].lazy;
            // 清除标记
            tree[p].lazy = 0;
        }
    }

    private static void pushUp(int p) {
        tree[p].sum = tree[p * 2].sum + tree[p * 2 + 1].sum;
    }


    static class TreeNode {
        public int left;
        public int right;
        public long sum;
        public long lazy = 0;

        public TreeNode() {
        }

        public TreeNode(int left, int right) {
            this.left = left;
            this.right = right;
        }

        public TreeNode(int left, int right, int sum) {
            this.left = left;
            this.right = right;
            this.sum = sum;
        }
    }


    static class Fr {
        static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        static StringTokenizer tokenizer = new StringTokenizer("");

        // nextLine()读取字符串
        static String nextLine() throws IOException {
            return reader.readLine();
        }

        // next()读取字符串
        static String next() throws IOException {
            while (!tokenizer.hasMoreTokens()) {
                tokenizer = new StringTokenizer(reader.readLine());
            }
            return tokenizer.nextToken();
        }

        // 读取一个int型数值
        static int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        // 读取一个double型数值
        static double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }

        // 读取一个long型数值
        static long nextLong() throws IOException {
            return Long.parseLong(next());
        }

        // 读取一个BigInteger
        static BigInteger nextBigInteger() throws IOException {
            return new BigInteger(Fr.nextLine());
        }
    }
}

2.乘法-加法操作

模板题：P3373 【模板】线段树 2 - 洛谷

如题，已知一个数列，你需要进行下面三种操作：

  • 将某区间每一个数乘上 x；
  • 将某区间每一个数加上 x；
  • 求出某区间每一个数的和。

同时包含多个操作时，会有优先级关系，具体的我也不懂，先把模板记着。区间修改的lazy是代表的加法懒标记，现在懒标记具体为加法add，乘法mul。add初始化为0，mul初始化为1。（0加任何数等于其本身，1乘以任何数等于其本身）。乘法的优先级高于加法，所以下移操作，先乘法计算，后加法计算。同时乘法操作（mul方法）时，要把加法计算补上

区间修改-区间查询
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
import java.io.*;
import java.util.StringTokenizer;

public class Main {

    private static long[] nums;

    private static TreeNode[] trees;

    private static long m;

    public static void main(String[] args) throws IOException {
        Fr sc = new Fr();
        PrintWriter pw = new PrintWriter(new BufferedOutputStream(System.out));
        int n = sc.nextInt(); // arr len
        int q = sc.nextInt(); // q query
        m = sc.nextInt(); // mod

        nums = new long[n];
        trees = new TreeNode[n << 2];
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }
        build(0, nums.length - 1, 1);
        for (int i = 0; i < q; i++) {
            int type = sc.nextInt();
            // 题目下标从1开始
            int x = sc.nextInt() - 1;
            int y = sc.nextInt() - 1;
            if (type == 2) {
                int k = sc.nextInt();
                add(x, y, k, 1);
            } else if (type == 1) {
                int k = sc.nextInt();
                mul(x, y, k, 1);
            } else {
                pw.println(ask(x, y, 1) % m);
            }
        }
        pw.flush();
    }

    // 线段树2
    public static void build(int left, int right, int p) {
        trees[p] = new TreeNode(left, right);
        if (left == right) {
            trees[p].sum = nums[left] % m;
            return;
        }
        int mid = left + right >> 1;
        build(left, mid, p * 2);
        build(mid + 1, right, p * 2 + 1);
        pushUp(p);
    }

    public static void add(int left, int right, int val, int p) {
        if (left <= trees[p].left && trees[p].right <= right) {
            trees[p].sum = (trees[p].sum + (long) (trees[p].right - trees[p].left + 1) * val) % m;
            trees[p].add = (trees[p].add + val) % m;
            return;
        }
        pushDown(p);

        int mid = trees[p].left + trees[p].right >> 1;
        if (left <= mid) {
            add(left, right, val, p * 2);
        }
        if (right > mid) {
            add(left, right, val, p * 2 + 1);
        }
        pushUp(p);
    }

    public static void mul(int left, int rihgt, int val, int p) {
        if (left <= trees[p].left && trees[p].right <= rihgt) {
            trees[p].sum = (trees[p].sum * val) % m;
            trees[p].mul = (trees[p].mul * val) % m;
            // 乘法的时候，要把之前的没有加的也要加了
            trees[p].add = (trees[p].add * val) % m;
            return;
        }
        pushDown(p);

        int mid = trees[p].left + trees[p].right >> 1;
        if (left <= mid) {
            mul(left, rihgt, val, p * 2);
        }
        if (rihgt > mid) {
            mul(left, rihgt, val, p * 2 + 1);
        }
        pushUp(p);
    }

    public static long ask(int left, int right, int p) {
        if (left <= trees[p].left && trees[p].right <= right) {
            return trees[p].sum;
        }
        pushDown(p);
        long ans = 0;
        int mid = trees[p].left + trees[p].right >> 1;
        if (left <= mid) {
            ans = (ans + ask(left, right, p * 2)) % m;
        }
        if (mid < right) {
            ans = (ans + ask(left, right, p * 2 + 1) % m);
        }
        return ans;
    }
	
    // 下移操作时，求和后，先乘后加
    private static void pushDown(int p) {
        trees[p * 2].sum = (trees[p * 2].sum * trees[p].mul + trees[p].add * (trees[p * 2].right - trees[p * 2].left + 1)) % m;
        trees[p * 2].mul = (trees[p * 2].mul * trees[p].mul) % m;
        trees[p * 2].add = (trees[p * 2].add * trees[p].mul + trees[p].add) % m;

        trees[p * 2 + 1].sum = (trees[p * 2 + 1].sum * trees[p].mul + trees[p].add * (trees[p * 2 + 1].right - trees[p * 2 + 1].left + 1)) % m;
        trees[p * 2 + 1].mul = (trees[p * 2 + 1].mul * trees[p].mul) % m;
        trees[p * 2 + 1].add = (trees[p * 2 + 1].add * trees[p].mul + trees[p].add) % m;

        trees[p].mul = 1;
        trees[p].add = 0;
    }

    private static void pushUp(int p) {
        trees[p].sum = (trees[p * 2].sum + trees[p * 2 + 1].sum) % m;
    }

    public static class TreeNode {
        public int left;
        public int right;
        public long sum;
        public long add = 0;
        public long mul = 1;

        public TreeNode(int left, int right) {
            this.left = left;
            this.right = right;
        }
    }

    public static class Fr {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokenizer = new StringTokenizer("");

        // nextLine()读取字符串
        String nextLine() throws IOException {
            return reader.readLine();
        }

        // next()读取字符串
        String next() throws IOException {
            while (!tokenizer.hasMoreTokens()) {
                tokenizer = new StringTokenizer(reader.readLine());
            }
            return tokenizer.nextToken();
        }

        // 读取一个int型数值
        int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        // 读取一个double型数值
        double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }

        // 读取一个long型数值
        long nextLong() throws IOException {
            return Long.parseLong(next());
        }
    }
}

3.最小生成树

介绍参见：最小生成树_百度百科

n个点，这些点之间有一些有权边，请通过这些有权边，将这n个点连接起来，使得所有点都被连接在一起（即能任意一点到达其他所有的点）。其中满足条件的边权和的最小值的情况，就是最小生成树。

假设有n个点，m条边。最小生成树一点只有n-1条连接边。且不会成环。

1.kruskal算法

该算法的思想是选边，每次都选之前未被选择的最小的边。查看该边是与之前选择的边构成环，如果成环则丢弃该边。否则选择这条边。直到选择了n-1条边，就构成了最小生成树。这里采用排序后，使用并查集的方式查询是否成环。

  1. 排序所有边。
  2. 选择最小的未被选择的边。如果不与之前选择的边成环，则选择，否则丢弃
  3. 重复2步骤直到选择了n-1条边。

时间复杂度：O(mlogm)，m条边，并查集logm（只采用了路径压缩），适用于稀疏图。

另外如果先选最大的，就是最大生成树了，

模板题：1584. 连接所有点的最小费用 - 力扣

kruskal
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
class Solution {
    public int minCostConnectPoints(int[][] points) {
        int n = points.length;
        List<Edge> edges = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i != j) {
                    int dis = Math.abs(points[i][0] - points[j][0]) + Math.abs(points[i][1] - points[j][1]);
                    edges.add(new Edge(i, j, dis));
                }
            }
        }

        kruskals(edges, n);
        return ans;
    }

    private List<Edge> minDisList;
    private int ans = 0;

    public void kruskals(List<Edge> edges, int n) {
        this.minDisList = new ArrayList<>();
        
        // 排序
        Collections.sort(edges, (a, b) -> a.w - b.w);
        DSU dsu = new DSU(n);
        // 这里并没有控制加入了n-1条边，因为一旦要加入第n条边，则必定成环，判环的同时顺便控制了
        for (Edge edge : edges) {
            int u = edge.u;
            int v = edge.v;
            int w = edge.w;
            // 若这条边不会产生环，则加入 mst
            if (!dsu.isUnion(u, v)) {
                dsu.union(u, v);
                // 打印出路径最小生成树，u到v的距离为w
                // System.out.println(u + " --> " + v + "  " + w);
                ans += w;
                minDisList.add(new Edge(u, v, w));
            }
        }

        // System.out.println(minDisList);
    }


    static class Edge {
        public int u;
        public int v;
        public int w;

        public Edge(int u, int v, int w) {
            this.u = u;
            this.v = v;
            this.w = w;
        }

        @Override
        public String toString() {
            return "Edge{" +
                    "u=" + u +
                    ", v=" + v +
                    ", w=" + w +
                    '}';
        }
    }


    public static class DSU {
        // 联通分量,用来判断环的数量，有setCount个环
        public int setCount;
        public int[] fa;

        public DSU(int n) {
            this.fa = new int[n];
            this.setCount = n;
            for (int i = 0; i < fa.length; i++) {
                fa[i] = i;
            }
        }
		
        // 是否成环
        public boolean isUnion(int x, int y) {
            return findFa(x) == findFa(y);
        }

        public int findFa(int x) {
            if (fa[x] == x) {
                return x;
            }
            int rootFa = findFa(this.fa[x]);
            fa[x] = rootFa;
            return rootFa;
        }

        public void union(int x, int y) {
            int xFa = findFa(x);
            int yFa = findFa(y);
            // 连接两个不相连的点，联通分量减1
            if (xFa != yFa) {
                setCount--;
            }
            fa[xFa] = yFa;
        }
    }
}

2.prim算法

该算法的思想是选点，先选定一个点1（一般为编号最小的点），加入到选中集合A，未选中的点存在集合B。接着从集合B中的所有点找到距离集合A中任意点距离（权重）最近的点，假设为点3，将3加入集合A，现在集合A中有点1和3。接着再从集合B中的所有点找出一个点，距离集合A中的1或3距离（权重）最近的点。直到所有的点都被加入到集合A。

  1. 选择编号最小的点从集合B加入集合A
  2. 从B中选择一个点，该点距离集合A中的某个点是距离最近的
  3. 重复2步骤直到所有点被从集合B加入集合A

时间复杂度：O(n2)O(n^2)，如代码的prim的双重for。适合于稠密图。

模板题：1584. 连接所有点的最小费用 - 力扣

注意点编号是从1开始还是从0开始，这里题目没说，默认从0开始，但是模板是从1开始的，所以略有改动。

prim
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
class Solution {
    private int[] minDisArr;
    private int[] fa;
    private int INF = 0x3f3f3f3f;

    public int minCostConnectPoints(int[][] points) {
        int n = points.length;

        // 模板的建图编号从1开始，所以长度加1，后续同理（因为此题没有节点编号，默认第一个节点编号1）
        int[][] graphArr = new int[points.length + 1][points.length + 1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i != j) {
                    graphArr[i + 1][j + 1] = Math.abs(points[i][0] - points[j][0]) + Math.abs(points[i][1] - points[j][1]);
                }
            }
        }

        // 到点i的最近的距离,由于点的下标从1开始，这里给数组长度为n+1
        this.minDisArr = new int[n + 1];
        Arrays.fill(minDisArr, INF);
        // 节点i是否被访问
        boolean[] vis = new boolean[n + 1];
        // 节点i的父节点
        fa = new int[n + 1];

        // 设节点1为起始节点，其父亲节点为-1
        minDisArr[1] = 0;
        fa[1] = -1;

        // prim algo
        for (int i = 1; i <= n; i++) {
            // u表示最小的未被访问的距离最小的点
            int u = findMin(vis, minDisArr);
            // 接下来u被加入，标记为已访问
            vis[u] = true;
            // 使用u更新到其他点的最小距离，优化后面查找最小值的时间复杂度
            for (int v = 1; v <= n; v++) {
                if (!vis[v] && graphArr[u][v] < minDisArr[v]) {
                    // 更新到v的最小距离
                    minDisArr[v] = graphArr[u][v];
                    // 标记u的父亲节点是v（从v到所有点中，v到u距离最近）
                    fa[v] = u;
                }
            }
        }

        // 不可构成最小生成树
        for (int i = 1; i < minDisArr.length; i++) {
            if (minDisArr[i] == INF) {
                return -1;
            }
        }

        int ans = 0;
        for (int i = 1; i < minDisArr.length; i++) {
            ans += minDisArr[i];
        }
        return ans;
    }
	
    // 注意，如果minIdx不会返回-1，未访问的点一定会有minDisArr[i]小于INF（即if条件最少会成立一次）
    // 这里找最小值，是用了如下代码优化的。朴素的方法是遍历未被访问集合中的所有点，
    // 然后二重循环遍历已访问集合的所有的点，这样最终会导致n^3时间的复杂度。
    private int findMin(boolean[] vis, int[] minDisArr) {
        int minDis = INF;
        int minIdx = -1;
        // 编号从1开始
        for (int i = 1; i < minDisArr.length; i++) {
            if (!vis[i] && minDisArr[i] < minDis) {
                minDis = minDisArr[i];
                minIdx = i;
            }
        }
        return minIdx;
    }
}

4.N叉树的最近公共祖先

1.倍增

倍增法主要基于1、2两点。

  1. 任何一个10进制数能用二进制表示，进而能够被k（这里k指任意数量）个2的幂次相加得到，后面的数的下标表示进制。
    例如5105_{10}，的二进制是1012101_2，进而可以用1002+12100_2 + 1_2得到，这两个数分别是2的幂次，410、1104_{10}、1_{10}。我们可以倒着从2幂次数倒着遍历，就一定可以加到目标10进制数。且不需要撤销前面的加上数。
  2. 若memeArr[i][j]的值表示从节点i跳2^j步到的节点编号，则有memeArr[i][j]=memeArr[[memeArr[i][j−1]]][j−1]memeArr[i][j] = memeArr[[memeArr[i][j-1]]][j-1]。即从i节点跳2^j步到达的节点，等于从i节点跳2^(i-1)步到达的节点，再跳2^(i-1)步到达的节点。
    释义：memeArr[i][0]，表示从编号i的节点跳2^0步到达节点（即跳一步，到达节点i父节点）。
  3. 将两个节点跳到同一高度后，我们倍增的去跳到最近公共祖先的子节点。再往上跳一步就是最近公共祖先。

时间复杂度：预处理LCA为O(n)，对于m此询问，每次询问为O(lgn)，因此总的为O(n + mlgn)。

模板题：P3379 【模板】最近公共祖先（LCA）

另有LC模板题目：236. 二叉树的最近公共祖先 ，此题暴力也可过，是O(N)的时间复杂度，先建立到父节点反向节点记录，然后将深度更深的那个点跳到两个节点一样深，然后一起往上一直跳，直到两个节点是同一个节点，即为答案。

倍增
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
import java.io.*;
import java.util.*;

public class Main {
    // 节点个数n
    private static int n;
    // 点最多能够跳2^h的高度(后面会计算2^h >= 节点数n)
    private static int h;
    // 记录每个编号节点跳2的幂次能够到达的节点
    private static int[][] memeArr;
    private static int[] deepArr;

    public static void main(String[] args) throws IOException {
        Fr sc = new Fr();
        PrintWriter pw = new PrintWriter(new BufferedOutputStream(System.out));

        n = sc.nextInt(); // 节点个数
        int m = sc.nextInt(); // 询问次数
        int s = sc.nextInt(); // 根节点序号

        // 创建树，节点编号从1开始（n+1）
        List<Integer>[] graphListArr = new List[n + 1];
        Arrays.setAll(graphListArr, x -> new ArrayList<>());
        // 接下来 N-1 行每行包含两个正整数x,y，表示 x 结点和 y 结点之间有一条直接连接的边
        for (int i = 1; i <= n - 1; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            graphListArr[x].add(y);
            graphListArr[y].add(x);
        }
        initLca(s, graphListArr);
        // 接下来 M 行每行包含两个正整数a,b，表示询问 a 结点和 b 结点的最近公共祖先
        for (int i = 0; i < m; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int ans = lca(a, b);
            pw.println(ans);
        }

        pw.flush();
    }

    public static void initLca(int s, List<Integer>[] graphListArr) {
        // 最多跳2^h次 (计算公式为log(2底数)(n) + 1)
        h = (int) (Math.log(n) / Math.log(2)) + 1;
        // 节点编号从1开始（n+1）
        deepArr = new int[n + 1];
        memeArr = new int[n + 1][h + 1];

        // 这里使用BFS，使用DFS也可以
        Deque<Integer> queue = new ArrayDeque<>();
        queue.add(s);
        // 根节点深度为1
        deepArr[s] = 1;
        // 初始化根节点的所有祖先都是其本身
        Arrays.fill(memeArr[s], s);

        while (!queue.isEmpty()) {
            int u = queue.pollFirst();
            for (Integer v : graphListArr[u]) {
                // 避免重复访问已经访问过的节点
                if (deepArr[v] != 0) {
                    continue;
                }
                // 字节点深度 = 父节点深度+1
                deepArr[v] = deepArr[u] + 1;
                // 往上跳一步是父亲u
                memeArr[v][0] = u;
                for (int i = 1; i <= h; i++) {
                    // 公式
                    memeArr[v][i] = memeArr[memeArr[v][i - 1]][i - 1];
                }
                queue.addLast(v);
            }
        }
    }

    public static int lca(int x, int y) {
        // 保证深度，y节点比x节点深，简化后续代码编写
        if (deepArr[x] > deepArr[y]) {
            int temp = x;
            x = y;
            y = temp;
        }

         // 从大到小遍历，一个10进制数能被表示为二进制，也能被k个2的幂次数相加得到，所以，y会跳到与x相同的高度
        for (int i = h; i >= 0; i--) {
            // 如果将要跳后，y深度还是大于等于x，则跳，最终y会跳到与x相同的高度
            if (deepArr[memeArr[y][i]] >= deepArr[x]) {
                y = memeArr[y][i];
            }
        }

        // x、y高度相同了，但是如果他们此刻就是同一个节点，就直接返回答案
        if (x == y) {
            return x;
        }
		
        // 从大到小遍历
        for (int i = h; i >= 0; i--) {
            // 两个节点同时向上跳，如果不会跳到同一个节点，则跳
            if (memeArr[x][i] != memeArr[y][i]) {
                x = memeArr[x][i];
                y = memeArr[y][i];
            }
        }
		// 最后他们的父节点就是公共祖先
        return memeArr[x][0];
    }

    static class Fr {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokenizer = new StringTokenizer("");

        // nextLine()读取字符串
        String nextLine() throws IOException {
            return reader.readLine();
        }

        // next()读取字符串
        String next() throws IOException {
            while (!tokenizer.hasMoreTokens()) {
                tokenizer = new StringTokenizer(reader.readLine());
            }
            return tokenizer.nextToken();
        }

        // 读取一个int型数值
        int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        // 读取一个double型数值
        double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }

        // 读取一个long型数值
        long nextLong() throws IOException {
            return Long.parseLong(next());
        }

    }

}

补充1：对于树上任意两点的距离，deepArr[x] + deepArr[y] - (2 * deepArr[lca(x, y)]);，根节点到x节点的距离deepArr[x] - 1，到y节点的距离deepArr[y]-1，此两者相加，就是（根到最近公共祖先节点 * 2 + 公共祖先节点到x节点 + 公共祖先节点到y节点），将根节点到公共祖节点的两次减去即可。根到公共祖先节点的距离deepArr[lca(x, y)] - 1。所以有

(deepArr[x]−1)+(deepArr[y]−1)−2∗(deepArr[lca(x,y)]−1)=deepArr[x]+deepArr[y]−(2∗deepArr[lca(x,y)])(deepArr[x] - 1) + (deepArr[y]-1) - 2*(deepArr[lca(x, y)] - 1) = deepArr[x] + deepArr[y] - (2 * deepArr[lca(x, y)])

因此计算任意两节点的最短距离代码为（需要initLca方法前置处理）：

1
2
3
int clac(int x, int y) { // 倍增查询两点间距离
    return deepArr[x] + deepArr[y] - (2 * deepArr[lca(x, y)]);
}

补充2：对于加权图树上任意两点距离

1

2.TarjanLCA

// TODO暂时留坑

本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可