跳转至

大纲详解

1、C++ 程序设计

1.1【 8 】 面向对象的程序设计思想（OOP）

​ 面向对象的程序设计思想是一种编程范式，它将计算机程序看作是由对象组成的，每个对象都有自己的数据和操作。面向对象的程序设计思想将数据和操作封装在一起，使得程序更加清晰、简洁、可维护、可扩展。面向对象的程序设计思想是现代编程语言的核心，如 C++、Java、Python 等都是面向对象的编程语言。

面向对象的程序设计思想包含以下几个核心概念：

  1. 对象（Object）：对象是现实世界中某个实体的模型。在程序中，一个对象通常包含一些数据和方法，数据用于描述对象的属性，方法用于描述对象的行为。
  2. 类（Class）：类是对象的模板或蓝图，它定义了对象的数据和方法。类是面向对象的程序设计中最重要的概念之一。
  3. 继承（Inheritance）：继承是面向对象程序设计中实现代码重用的机制之一。子类（派生类）可以继承父类（基类）的属性和方法，并且可以在此基础上添加新的属性和方法。
  4. 多态（Polymorphism）：多态是面向对象程序设计中的一个重要特性，它允许同一个操作在不同的对象上有不同的行为。多态可以通过继承和接口实现。
  5. 封装（Encapsulation）：封装是一种保护数据的机制，它将数据和操作封装在一起，只向外部提供必要的接口，从而防止数据被误用或修改。

​ 使用面向对象的程序设计思想，可以将问题分解为一个个独立的对象，每个对象负责自己的任务，然后通过对象之间的协作和交互来完成整个程序的功能。面向对象的程序设计思想使得程序结构更加清晰、可读性更高，能够提高程序的可维护性和可扩展性，有助于提高程序开发的效率和质量。

2、 数据结构

2.1 线性结构

2.1.1 块状链表

​ 块状链表（Block Linked List）是一种用于解决链表与数组各自优缺点的数据结构，也称为分块链表。它结合了链表的动态性和数组的高效查询能力，以获得更好的性能。块状链表把数据分成若干个大小相等的块，每个块内的数据采用数组存储，块之间采用链表连接。

块状链表的主要特点：

  1. 数据分块：把原始数据分为多个大小相等的块，每个块包含连续的数据。一般情况下，每个块的大小为 sqrt(n)，其中 n 为数据总量。
  2. 块内数据：每个块内的数据使用数组存储。这样可以方便地访问和操作数据，同时保持连续性，提高空间和时间效率。
  3. 块间连接：每个块包含一个指针，指向下一个块。这样可以灵活地添加、删除和移动数据块，实现动态数据结构。

块状链表的优点：

  1. 提高查询效率：由于每个块内部是数组存储，可以利用二分查找等高效算法，加快查找速度。同时，由于块大小为 sqrt(n)，查询时间复杂度为 O(sqrt(n))。
  2. 动态性：与数组相比，块状链表可以更灵活地处理数据的插入、删除操作。插入和删除的时间复杂度为 O(sqrt(n))。
  3. 空间利用率：与链表相比，块状链表可以更好地利用内存空间，因为每个块内的数据是连续存储的，减少了指针的使用。

块状链表的应用场景：

  1. 适用于数据量较大、需要高效查询和动态操作的场景。例如：区间查询、区间修改等问题。
  2. 可以作为一种高效的索引结构，用于数据库、文件系统等应用。

块状链表的操作主要包括以下几种：

  1. 初始化：创建一个空的块状链表，分配一个固定大小的块，将其作为链表的头部。
  2. 插入：将一个元素插入到块状链表中的指定位置，需要找到对应的块，并在块内部的链表中插入元素。
  3. 删除：从块状链表中删除指定位置的元素，需要找到对应的块，并在块内部的链表中删除元素。
  4. 查找：根据下标或者元素的值，在块状链表中查找对应的元素。

块状链表的实现需要注意以下几点：

  1. 块的大小应该根据具体的应用场景进行调整，过大会导致内存浪费，过小会增加块之间的指针开销。
  2. 需要考虑块之间的指针连接方式，可以采用链表、数组或者其他方式。
  3. 在插入和删除元素时，需要判断块是否已经满，如果满了需要申请新的块，并将新的块插入到链表中。

块状链表是一种非常实用的数据结构，在实际的应用中被广泛使用，如数据库、文件系统等领域。

以下是块状链表的简单 C++ 实现代码：

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
 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
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
#include <iostream>
#include <vector>

using namespace std;

const int BLOCK_SIZE = 10;  // 每个块的大小

// 块状链表节点
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// 块状链表块
struct Block {
    vector<ListNode*> nodes;
    Block* next;
    Block() : next(nullptr) {}
    ~Block() {
        for (auto node : nodes) {
            delete node;
        }
    }
};

// 块状链表
class BlockList {
    public:
        BlockList() {
            head_ = tail_ = new Block();
        }

        ~BlockList() {
            Block* curr = head_;
            while (curr) {
                Block* next = curr->next;
                delete curr;
                curr = next;
            }
        }

        // 在指定位置插入元素
        void insert(int index, int val) {
            int blockIndex = index / BLOCK_SIZE;  // 计算块的位置
            int nodeIndex = index % BLOCK_SIZE;   // 计算节点在块内的位置
            Block* block = getBlock(blockIndex);  // 获取块
            ListNode* node = new ListNode(val);   // 创建新节点
            if (nodeIndex == 0) {  // 插入到块的头部
                node->next = block->nodes.front();
                block->nodes.front() = node;
            } else {  // 插入到块的中间或尾部
                ListNode* prev = block->nodes[nodeIndex - 1];
                node->next = prev->next;
                prev->next = node;
            }
            size_++;
            if (block->nodes.size() > BLOCK_SIZE) {  // 如果块已满，需要分裂
                splitBlock(blockIndex, block);
            }
        }

        // 删除指定位置的元素
        void erase(int index) {
            int blockIndex = index / BLOCK_SIZE;  // 计算块的位置
            int nodeIndex = index % BLOCK_SIZE;   // 计算节点在块内的位置
            Block* block = getBlock(blockIndex);  // 获取块
            if (nodeIndex == 0) {  // 删除块的头部节点
                ListNode* node = block->nodes.front();
                block->nodes.front() = node->next;
                delete node;
            } else {  // 删除块的中间或尾部节点
                ListNode* prev = block->nodes[nodeIndex - 1];
                ListNode* node = prev->next;
                prev->next = node->next;
                delete node;
            }
            size_--;
            if (block->nodes.empty()) {  // 如果块为空，需要合并
                mergeBlock(blockIndex, block);
            }
        }

        // 返回指定位置的元素
        int get(int index) {
            int blockIndex = index / BLOCK_SIZE;  // 计算块的位置
            int nodeIndex = index % BLOCK_SIZE;   // 计算节点在块内的位置
            Block* block = getBlock(blockIndex);  // 获取块
            ListNode* node = block->nodes[nodeIndex];
            return node->val;
        }

        // 返回
// 元素数量
        int size() {
            return size_;
        }
    private:
        Block* head_; // 头块
        Block* tail_; // 尾块
        int size_ = 0; // 元素数量
        // 获取指定位置的块
        Block* getBlock(int index) {
            Block* block = head_;
            while (index > 0) {
                block = block->next;
                index--;
            }
            return block;
        }

// 分裂块
        void splitBlock(int blockIndex, Block* block) {
            int mid = block->nodes.size() / 2;
            Block* newBlock = new Block();
            newBlock->nodes = vector<ListNode*>(block->nodes.begin() + mid, block->nodes.end());
            block->nodes.erase(block->nodes.begin() + mid, block->nodes.end());
            if (block == tail_) {  // 如果分裂的是尾块，需要更新 tail_
                tail_ = newBlock;
            }
            newBlock->next = block->next;
            block->next = newBlock;
        }

// 合并块
        void mergeBlock(int blockIndex, Block* block) {
            if (block == head_) {  // 如果合并的是头块，需要更新 head_
                head_ = block->next;
            } else {  // 合并的是中间块
                Block* prev = getBlock(blockIndex - 1);
                prev->next = block->next;
            }
            block->next = nullptr;
            delete block;
        }
        csharp
        Copy code
// 元素数量
        int size() {
            return size_;
        }
    private:
        Block* head_; // 头块
        Block* tail_; // 尾块
        int size_ = 0; // 元素数量

        scss
        Copy code
// 获取指定位置的块
        Block* getBlock(int index) {
            Block* block = head_;
            while (index > 0) {
                block = block->next;
                index--;
            }
            return block;
        }

// 分裂块
        void splitBlock(int blockIndex, Block* block) {
            int mid = block->nodes.size() / 2;
            Block* newBlock = new Block();
            newBlock->nodes = vector<ListNode*>(block->nodes.begin() + mid, block->nodes.end());
            block->nodes.erase(block->nodes.begin() + mid, block->nodes.end());
            if (block == tail_) {  // 如果分裂的是尾块，需要更新 tail_
                tail_ = newBlock;
            }
            newBlock->next = block->next;
            block->next = newBlock;
        }

// 合并块
        void mergeBlock(int blockIndex, Block* block) {
            if (block == head_) {  // 如果合并的是头块，需要更新 head_
                head_ = block->next;
            } else {  // 合并的是中间块
                Block* prev = getBlock(blockIndex - 1);
                prev->next = block->next;
            }
            block->next = nullptr;
            delete block;
        }
};

// 测试代码
int main() {
    BlockList list;
    for (int i = 0; i < 100; i++) {
        list.insert(i, i);
    }
    for (int i = 0; i < 100; i++) {
        cout << list.get(i) << " ";
    }
    cout << endl;
    for (int i = 99; i >= 0; i--) {
        list.erase(i);
    }
    cout << list.size() << endl;
    return 0;
}

2.2 序列

2.2.1 跳跃表

​ 跳跃表（Skip List）是一种基于概率平衡的数据结构，主要用于有序序列的查找、插入和删除操作。跳跃表的主要特点是其结构和查询算法简单，同时具有较好的时间复杂度。在很多场景下，跳跃表可以作为一种替代平衡树的高效数据结构。

​ 跳跃表的基本思想是对有序链表进行层次化，即在原有序链表的基础上增加多级索引。每一级索引都是原有序链表的一个子集，每一级索引之间的跳跃距离大约是相邻级别的 2 倍。通过这种层次化的结构，跳跃表可以在查找时快速跳过不需要查询的部分，提高查找效率。

跳跃表的性能：

  1. 查找、插入、删除操作的平均时间复杂度为 O(log n)，其中 n 为元素总数。
  2. 空间复杂度为 O(n)。

以下是一个简单的跳跃表实现：

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
 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
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <limits>

using namespace std;

const int MAX_LEVEL = 32;
const float PROBABILITY = 0.5;

struct Node {
    int key;
    int value;
    Node** forward;
    Node(int k, int v, int level) : key(k), value(v) {
        forward = new Node*[level + 1];
        for (int i = 0; i <= level; ++i) {
            forward[i] = nullptr;
        }
    }
};

class SkipList {
    private:
        Node* head;
        int maxLevel;
        int size;

    public:
        SkipList() {
            head = new Node(-1, -1, MAX_LEVEL);
            maxLevel = 0;
            size = 0;
        }

        ~SkipList() {
            Node* current = head;
            while (current) {
                Node* toDelete = current;
                current = current->forward[0];
                delete[] toDelete->forward;
                delete toDelete;
            }
        }

        int randomLevel() {
            int level = 1;
            while ((rand() / (float)RAND_MAX) < PROBABILITY && level < MAX_LEVEL) {
                level++;
            }
            return level;
        }

        // 在跳跃表中查找元素
        Node* find(int key) {
            Node* current = head;
            for (int i = maxLevel; i >= 0; --i) {
                while (current->forward[i] && current->forward[i]->key < key) {
                    current = current->forward[i];
                }
            }
            current = current->forward[0];
            if (current && current->key == key) {
                return current;
            } else {
                return nullptr;
            }
        }

        // 在跳跃表中插入元素
        void insert(int key, int value) {
            Node* update[MAX_LEVEL + 1];
            Node* current = head;
            for (int i = maxLevel; i >= 0; --i) {
                while (current->orward[i] && current->forward[i]->key < key) {
                    current = current->forward[i];
                }
                update[i] = current;
            }
            current = current->forward[0];
            if (current == nullptr || current->key != key) {
                int newLevel = randomLevel();
                if (newLevel > maxLevel) {
                    for (int i = maxLevel + 1; i <= newLevel; ++i) {
                        update[i] = head;
                    }
                    maxLevel = newLevel;
                }
                Node* newNode = new Node(key, value, newLevel);
                for (int i = 0; i <= newLevel; ++i) {
                    newNode->forward[i] = update[i]->forward[i];
                    update[i]->forward[i] = newNode;
                }
                size++;
            }
        }

        // 从跳跃表中删除元素
        void remove(int key) {
            Node* update[MAX_LEVEL + 1];
            Node* current = head;
            for (int i = maxLevel; i >= 0; --i) {
                while (current->forward[i] && current->forward[i]->key < key) {
                    current = current->forward[i];
                }
                update[i] = current;
            }
            current = current->forward[0];

            if (current && current->key == key) {
                for (int i = 0; i <= maxLevel; ++i) {
                    if (update[i]->forward[i] != current) {
                        break;
                    }
                    update[i]->forward[i] = current->forward[i];
                }
                delete[] current->forward;
                delete current;

                while (maxLevel > 0 && head->forward[maxLevel] == nullptr) {
                    maxLevel--;
                }
                size--;
            }
        }
};

int main() {
    srand(time(nullptr));
    SkipList skipList;
// 对跳跃表进行插入、查找、删除操作
}

​ 上面的代码实现了一个简单的跳跃表，包括查找、插入、删除等基本操作。在实际应用中，可以根据需求对跳跃表进行优化，例如调整层级概率、增加缓存优化等。跳跃表广泛应用于各种场景，如数据库、缓存系统、路由等。

2.3 复杂树

2.3.1 树链剖分

​ 树链剖分（Heavy-Light Decomposition, HLD）是一种用于优化对树型结构操作的方法。在处理树结构相关问题时，树链剖分可以将一些复杂度较高的操作转化为较低复杂度的操作，从而提高算法的效率。树链剖分常用于解决路径查询、子树查询等问题。

​ 树链剖分的基本思想是将树划分为若干条链，每条链上的节点个数不超过 log(n)。在这种划分下，任意两个节点之间的路径最多需要经过 2 * log(n) 个链。通过这种划分方法，我们可以将一些在原始树上的操作转化为对链上的操作，从而减小操作的复杂度。

以下是树链剖分的基本步骤：

  1. 选择重儿子：对于树中的每个节点，选择其子树大小最大的子节点作为重儿子。其他子节点称为轻儿子。
  2. 构建重链：将所有重儿子连接起来，构成一条重链。轻儿子与其父节点之间的边称为轻边。
  3. 构建链：从树的根节点开始，沿着轻边进行 DFS 遍历。每次遍历到一个新节点时，将其与前一个节点连接成一条链。这样，整棵树被划分为多条链。
  4. 标记链：给每条链分配一个唯一的编号，同时记录每个节点所在的链编号和在链上的位置。
  5. 操作转化：将原始树上的操作转化为对链上的操作。例如，查询路径上的最大值可以转化为查询若干条链上的最大值。

下面是一个简单的树链剖分实现：

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
53
54
55
56
57
58
59
60
61
62
63
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 100005;
vector<int> tree[MAXN];
int parent[MAXN], depth[MAXN], size[MAXN], chain[MAXN], chainIndex[MAXN], heavy[MAXN];

void dfs(int u, int p) {
    parent[u] = p;
    depth[u] = p == -1 ? 0 : depth[p] + 1;
    size[u] = 1;
    heavy[u] = -1;

    for (int v : tree[u]) {
        if (v != p) {
            dfs(v, u);
            size[u] += size[v];
            if (heavy[u] == -1 || size[v] > size[heavy[u]]) {
                heavy[u] = v;
            }
        }
    }
}

int currentChain = 0;
void hld(int u, int p) {
    chain[u] = currentChain;
    chainIndex[u] = p == -1 ? 0 : chainIndex[p] + 1;

    if (heavy[u] != -1) {
        hld(heavy[u], u);
    }

    for (int v : tree[u]) {
        if (v != p && v != heavy[u]) {
            currentChain++;
            hld(v, u);
        }
    }
}

// 树链剖分完成后，可以根据需要实现相关操作，例如查询路径、更新子树等。

int main() {
    int n; // 树的节点数
    cin >> n;
    // 读入树的边
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }

// 进行树链剖分
    dfs(1, -1);
    hld(1, -1);

// 根据需求进行相关操作
}

​ 以上代码实现了树链剖分的基本框架。在实际应用中，可以根据需求在树链剖分的基础上实现各种操作，例如查询路径和、查询子树最大值等。树链剖分在很多场景下都可以大幅提高算法效率，是解决树型问题的重要方法。

2.3.2 动态树：LCT

​ Link-Cut Tree（LCT）是一种动态树数据结构，主要用于维护动态图中的有根树。LCT 支持对树进行一系列动态操作，例如访问、连接、断开等，同时具有较好的时间复杂度。LCT 的实现基于Splay Tree（伸展树），在很多场景下可以替代其他树形数据结构，如并查集、树链剖分等。

LCT 支持以下基本操作：

  1. 访问（Access）：将指定节点与根节点的路径转换为一条首尾相连的链。
  2. 连接（Link）：将两棵树通过一条边连接起来，生成一棵新的树。
  3. 断开（Cut）：将一棵树分割成两棵子树。
  4. 查询（Find）：查找某个节点的根节点。
  5. 路径聚合（Path Aggregate）：在路径上执行一些聚合操作，如查询最大值、求和等。

以下是一个简单的 LCT 实现：

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
 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
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 100005;
struct Node {
    int parent, ch[2];
    bool flip;
} nodes[MAXN];

inline bool is_root(int x) {
    return nodes[nodes[x].parent].ch[0] != x && nodes[nodes[x].parent].ch[1] != x;
}

inline void push_flip(int x) {
    if (!x) return;
    swap(nodes[x].ch[0], nodes[x].ch[1]);
    nodes[x].flip ^= 1;
}

inline void push_down(int x) {
    if (nodes[x].flip) {
        push_flip(nodes[x].ch[0]);
        push_flip(nodes[x].ch[1]);
        nodes[x].flip = 0;
    }
}

void rotate(int x) {
    int y = nodes[x].parent, z = nodes[y].parent, k = nodes[y].ch[1] == x;
    if (!is_root(y)) nodes[z].ch[nodes[z].ch[1] == y] = x;
    nodes[x].parent = z;
    nodes[y].parent = x;
    nodes[y].ch[k] = nodes[x].ch[!k];
    nodes[x].ch[!k] = y;
    if (nodes[y].ch[k]) nodes[nodes[y].ch[k]].parent = y;
}

void splay(int x) {
    vector<int> ancestors;
    for (int y = x; !is_root(y); y = nodes[y].parent) {
        ancestors.push_back(y);
    }
    ancestors.push_back(x);
    reverse(ancestors.begin(), ancestors.end());
    for (int y : ancestors) {
        push_down(y);
    }
    while (!is_root(x)) {
        int y = nodes[x].parent, z = nodes[y].parent;
        if (!is_root(y)) {
            rotate((nodes[y].ch[0] == x) ^ (nodes[z].ch[0] == y) ? x : y);
        }
        rotate(x);
    }
}

void access(int x) {
    for (int y = 0; x; y = x, x = nodes[x].parent) {
        splay(x);
        nodes[x].ch[1] = y;
    }
}

void make_root(int x) {
    access(x);
    splay(x);
    push_flip(x);
}

int find_root(int x) {
    access(x);
    splay(x);
    while (nodes[x].ch[0]) {
        push_down(x);
        x = nodes[x].ch[0];
    }
    splay(x);
    return x;
}

void link(int x, int y) {
    make_root(x);
    if (find_root(y) != x) {
        nodes[x].parent = y;
    }
}

void cut(int x, int y) {
    make_root(x);
    if (find_root(y) == x && nodes[y].parent == x && !nodes[y].ch[0]) {
        nodes[y].parent = nodes[x].ch[1] = 0;
    }
}

int main() {
    int n, m; // 节点数和操作数
    cin >> n >> m;
    // 读入操作，执行相应的 LCT 操作
    for (int i = 0; i < m; ++i) {
        string op;
        int x, y;
        cin >> op >> x >> y;
        if (op == "link") {
            link(x, y);
        } else if (op == "cut") {
            cut(x, y);
        } else if (op == "find") {
            cout << (find_root(x) == find_root(y) ? "YES" : "NO") << endl;
        }
    }
}

​ 以上代码实现了一个简单的 LCT，包括访问、连接、断开、查询等基本操作。在实际应用中，可以根据需求在 LCT 的基础上实现各种路径聚合操作，如查询路径最大值、路径求和等。LCT 在很多场景下都可以大幅提高算法效率，是解决动态树问题的重要方法。

2.3.3 二维线段树

​ 二维线段树是一种高级数据结构，用于处理二维区间查询和更新问题。它是一维线段树的扩展，将一维线段树应用于二维空间。二维线段树常用于解决二维矩阵区域查询、二维点更新等问题。

以下是二维线段树的基本操作：

  1. 建树：构建二维线段树的过程与一维线段树类似，需要递归地将二维区间划分为四个子区间，然后将子区间的值聚合为当前节点的值。
  2. 查询：查询一个二维区间的聚合值，例如最大值、最小值或者和。查询操作需要遍历二维线段树，找到与查询区间相交的节点，并将这些节点的值聚合起来。
  3. 更新：更新一个二维点的值。更新操作需要沿着从根节点到叶子节点的路径更新所有相关节点的值。

以下是一个简单的二维线段树实现：

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
 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
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

const int MAXN = 1005;
int matrix[MAXN][MAXN];
int tree[4 * MAXN][4 * MAXN];

void build_y(int vx, int lx, int rx, int vy, int ly, int ry) {
    if (ly == ry) {
        if (lx == rx) {
            tree[vx][vy] = matrix[lx][ly];
        } else {
            tree[vx][vy] = tree[vx * 2][vy] + tree[vx * 2 + 1][vy];
        }
    } else {
        int my = (ly + ry) / 2;
        build_y(vx, lx, rx, vy * 2, ly, my);
        build_y(vx, lx, rx, vy * 2 + 1, my + 1, ry);
        tree[vx][vy] = tree[vx][vy * 2] + tree[vx][vy * 2 + 1];
    }
}

void build_x(int vx, int lx, int rx, int n) {
    if (lx != rx) {
        int mx = (lx + rx) / 2;
        build_x(vx * 2, lx, mx, n);
        build_x(vx * 2 + 1, mx + 1, rx, n);
    }
    build_y(vx, lx, rx, 1, 0, n - 1);
}

int query_y(int vx, int vy, int tly, int try_, int ly, int ry) {
    if (ly > ry) {
        return 0;
    }
    if (ly == tly && try_ == ry) {
        return tree[vx][vy];
    }
    int tmy = (tly + try_) / 2;
    return query_y(vx, vy * 2, tly, tmy, ly, min(ry, tmy)) +
           query_y(vx, vy * 2 + 1, tmy + 1, try_, max(ly, tmy +1), ry);
}

int query_x(int vx, int tlx, int trx, int lx, int rx, int ly, int ry) {
    if (lx > rx) {
        return 0;
    }
    if (lx == tlx && trx == rx) {
        return query_y(vx, 1, 0, trx, ly, ry);
    }
    int tmx = (tlx + trx) / 2;
    return query_x(vx * 2, tlx, tmx, lx, min(rx, tmx), ly, ry) +
           query_x(vx * 2 + 1, tmx + 1, trx, max(lx, tmx + 1), rx, ly, ry);
}

void update_y(int vx, int lx, int rx, int vy, int ly, int ry, int y, int value) {
    if (ly == ry) {
        if (lx == rx) {
            tree[vx][vy] = value;
        } else {
            tree[vx][vy] = tree[vx * 2][vy] + tree[vx * 2 + 1][vy];
        }
    } else {
        int my = (ly + ry) / 2;
        if (y <= my) {
            update_y(vx, lx, rx, vy * 2, ly, my, y, value);
        } else {
            update_y(vx, lx, rx, vy * 2 + 1, my + 1, ry, y, value);
        }
        tree[vx][vy] = tree[vx][vy * 2] + tree[vx][vy * 2 + 1];
    }
}

void update_x(int vx, int lx, int rx, int x, int y, int value, int n) {
    if (lx != rx) {
        int mx = (lx + rx) / 2;
        if (x <= mx) {
            update_x(vx * 2, lx, mx, x, y, value, n);
        } else {
            update_x(vx * 2 + 1, mx + 1, rx, x, y, value, n);
        }
    }
    update_y(vx, lx, rx, 1, 0, n - 1, y, value);
}

int main() {
    int n; // 矩阵的大小
    cin >> n;
    // 读入矩阵
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> matrix[i][j];
        }
    }

// 建立二维线段树
    build_x(1, 0, n - 1, n);

// 根据需求进行查询或更新操作
    int q; // 查询次数
    cin >> q;
    for (int i = 0; i < q; ++i) {
        int op;
        cin >> op;
        if (op == 1) { // 查询操作
            int x1, y1, x2, y2;
            cin >> x1 >> y1 >> x2 >> y2;
            cout << query_x(1, 0, n - 1, x1, x2, y1, y2) << endl;
        } else { // 更新操作
            int x, y, value;
            cin >> x >> y >> value;
            update_x(1, 0, n - 1, x, y, value, n);
        }
    }
}

2.3.4 树套树

​ 树套树是一种高级数据结构，主要用于解决树上的区间问题。顾名思义，树套树是将一棵树嵌套在另一棵树的数据结构。常见的树套树结构包括线段树套线段树、线段树套平衡树、树状数组套树状数组等。树套树的核心思想是将问题从一个维度分解到另一个维度，通过在不同维度上的数据结构组合，解决复杂的树上问题。

​ 树套树的应用场景比较特殊，通常用于解决树上的路径问题、子树问题等。例如，查询树上某个子树内所有节点的第 k 大值、查询树上两个节点间的路径权值和等。在这些场景下，树套树可以有效地提高算法效率。

以下是一个简单的线段树套线段树实现：

Text Only
  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
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

const int MAXN = 1005;
int n; // 节点数
vector<int> adj[MAXN]; // 邻接表表示的树
int in[MAXN], out[MAXN], dfs_time; // dfs 序列
vector<int> vals[MAXN]; // 节点权值
int tree[4 * MAXN][4 * MAXN]; // 外层线段树套内层线段树

void dfs(int u, int parent) {
    in[u] = ++dfs_time;
    for (int v : adj[u]) {
        if (v != parent) {
            dfs(v, u);
        }
    }
    out[u] = dfs_time;
}

void update(int vx, int lx, int rx, int x, int vy, int ly, int ry, int y, int value) {
    if (lx == rx) {
        if (ly == ry) {
            tree[vx][vy] += value;
        } else {
            int my = (ly + ry) / 2;
            if (y <= my) {
                update(vx, lx, rx, x, vy * 2, ly, my, y, value);
            } else {
                update(vx, lx, rx, x, vy * 2 + 1, my + 1, ry, y, value);
            }
            tree[vx][vy] = tree[vx][vy * 2] + tree[vx][vy * 2 + 1];
        }
    } else {
        int mx = (lx + rx) / 2;
        if (x <= mx) {
            update(vx * 2, lx, mx, x, vy, ly, ry, y, value);
        } else {
            update(vx * 2 + 1, mx + 1, rx, x, vy, ly, ry, y, value);
        }
        tree[vx][vy] = tree[vx * 2][vy] + tree[vx * 2 + 1][vy];
    }
}

int query(int vx, int tlx, int trx, int lx, int rx, int vy, int tly, int try_, int ly, int ry) {
    if (lx > rx || ly > ry) {
        return 0;
    }
    if (lx == tlx && trx == rx && ly == tly && try_ == ry) {
        return tree[vx][vy];
    }
    int tmx = (tlx + trx) / 2;
    int tmy = (tly + try_) / 2;
    int result = 0;
    result += query(vx * 2, tlx, tmx, lx, min(rx, tmx), vy * 2, tly, tmy, ly, min(ry, tmy));
    result += query(vx * 2, tlx, tmx, lx, min(rx, tmx), vy * 2 + 1, tmy + 1, try_, max(ly, tmy + 1), ry);
    result += query(vx * 2 + 1, tmx + 1, trx, max(lx, tmx + 1), rx, vy * 2, tly, tmy, ly, min(ry, tmy));
    result += query(vx * 2 + 1, tmx + 1, trx, max(lx, tmx + 1), rx, vy * 2 + 1, tmy + 1, try_, max(ly, tmy + 1), ry);
    return result;
}

int main() {
    cin >> n;
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1, 0); // 计算 dfs 序列

// 读入节点权值，并建立线段树套线段树
    for (int i = 1; i <= n; ++i) {
        int val;
        cin >> val;
        vals[val].push_back(in[i]);
        update(1, 1, n, in[i], 1, 1, n, val, 1);
    }

    int q; // 查询次数
    cin >> q;
    for (int i = 0; i < q; ++i) {
        int op;
        cin >> op;
        if (op == 1) { // 查询操作
            int u, k;
            cin >> u >> k;
            cout << query(1, 1, n, in[u], out[u], 1, 1, n, 1, k) << endl;
        } else { // 更新操作
            int u, k;
            cin >> u >> k;
            int old_val = vals[k][lower_bound(vals[k].begin(), vals[k].end(), in[u]) - vals[k].begin()];
            update(1, 1, n, in[u], 1, 1, n, old_val, -1);
            update(1, 1, n, in[u], 1, 1, n, k, 1);
            vals[old_val].erase(lower_bound(vals[old_val].begin(), vals[old_val].end(), in[u]));
            vals[k].push_back(in[u]);
        }
    }
}

2.3.5 k-d 树

​ k-d树，即k维树（k-dimensional tree），是一种用于在k维空间中存储点集的数据结构。k-d树是一种二叉搜索树，将每个维度看作一个关键字。它可以用于处理多维空间中的范围查询、最近邻查询等问题，具有较高的查询效率。

​ k-d树的基本思想是递归地将k维空间划分为两个子空间，每个节点表示一个空间划分的轴（axis-aligned hyperplane）。在构建k-d树时，每一层采用轮流选择坐标轴的策略，选定坐标轴后根据中位数将点集划分为左右两部分，左子树代表轴左侧的子空间，右子树代表轴右侧的子空间。

下面是一个简单的k-d树实现：

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
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
#include <algorithm>
#include <vector>
#include <iostream>
#include <cmath>
#include <limits>

using namespace std;

const int K = 2; // 维数
typedef vector<double> Point;

struct Node {
    Point point;
    int axis; // 划分轴
    Node* left;
    Node* right;
};

// 按照指定的轴排序点集
bool compare_axis(const Point& a, const Point& b, int axis) {
    return a[axis] < b[axis];
}

// 构建 k-d 树
Node* build_kd_tree(vector<Point>& points, int depth = 0) {
    if (points.empty()) {
        return nullptr;
    }

    int axis = depth % K;
    size_t median = points.size() / 2;
    nth_element(points.begin(), points.begin() + median, points.end(),
    [axis](const Point& a, const Point& b) {
        return compare_axis(a, b, axis);
    });

    Node* node = new Node;
    node->point = points[median];
    node->axis = axis;

    vector<Point> left_points(points.begin(), points.begin() + median);
    vector<Point> right_points(points.begin() + median + 1, points.end());
    node->left = build_kd_tree(left_points, depth + 1);
    node->right = build_kd_tree(right_points, depth + 1);

    return node;
}

// 计算两点之间的欧几里得距离
double euclidean_distance(const Point& a, const Point& b) {
    double sum = 0;
    for (int i = 0; i < K; ++i) {
        sum += (a[i] - b[i]) * (a[i] - b[i]);
    }
    return sqrt(sum);
}

// 查询 k-d 树中距离目标点最近的点
void nearest_neighbor_search(Node* node, const Point& target, Point& best, double& best_distance) {
    if (!node) {
        return;
    }

    double distance = euclidean_distance(node->point, target);
    if (distance < best_distance) {
        best_distance = distance;
        best = node->point;
    }

    double diff = target[node->axis] - node->point[node->axis];
    Node *first = diff <= 0 ? node->left : node->right;
    Node *second = diff <= 0 ? node->right : node->left;
    nearest_neighbor_search(first, target, best, best_distance);

// 如果目标点与划分轴的距离小于当前最优距离，需要在另一个子空间中继续搜索
    if (fabs(diff) < best_distance) {
        nearest_neighbor_search(second, target, best, best_distance);
    }
}

int main() {
    vector<Point> points = {
        {2, 3}, {5, 4}, {9, 6}, {4, 7}, {8, 1}, {7, 2}
    };
    Node *root = build_kd_tree(points);

    Point target = {9, 2};
    Point best;
    double best_distance = numeric_limits<double>::max();

    nearest_neighbor_search(root, target, best, best_distance);

    cout << "Nearest point to (" << target[0] << ", " << target[1] << "): ("
         << best[0] << ", " << best[1] << ")\n";
    cout << "Distance: " << best_distance << endl;

    return 0;
}

​ 以上代码实现了一个简单的k-d树，并使用k-d树实现了最近邻搜索。在实际应用中，k-d树可以用于处理各种多维空间问题，如范围查询、最近邻搜索等。需要注意的是，k-d树在处理高维数据时效率会降低，此时可以考虑使用其他方法，如局部敏感哈希（LSH）等。

2.3.6 虚树

​ 虚树（Virtual Tree），也称为辅助树，是一种用于解决树上路径问题的数据结构。虚树并不是一个独立的数据结构，而是基于原始树的一种构造。虚树的主要作用是将一些点集在原始树上的关系压缩成一棵辅助的树，以便对这些点集进行更加高效的处理。

虚树的构建过程如下：

  1. 给定一个点集，找到这个点集的LCA（最近公共祖先）集合。
  2. 对LCA集合进行排序，并将其连接成一棵新的树，使得新树的节点数最小。
  3. 将原始点集的点添加到新树中，并保持新树的拓扑结构。

虚树的主要特点：

  1. 虚树上所有节点的父子关系与原树中的父子关系相同。
  2. 虚树中的任意两个点在原树中都存在一条简单路径，该路径上的所有点都属于虚树。

虚树的应用场景：

​ 虚树常用于解决树上的路径问题，例如查询树上某个子树内所有节点的第k大值、查询树上两个节点间的路径权值和等。在这些场景下，虚树可以有效地减小问题的规模，提高算法效率。

​ 需要注意的是，虚树并非适用于所有树上问题。当问题涉及到树的结构变化（如节点添加、删除、连接等）时，虚树可能无法解决。此外，在处理大规模数据时，虚树的构建过程可能成为性能瓶颈，需要考虑使用其他方法进行优化。

2.4 可合并堆

2.4.1 左偏树

左偏树（Leftist Tree），也叫做可合并堆（Mergable Heap），是一种用于实现优先队列的数据结构。左偏树同时具有堆和二叉树的性质。它的主要特点是在保持堆性质的同时，支持高效的合并操作。左偏树在合并操作上的时间复杂度为O(log N)，因此常用于解决涉及到堆合并的问题。

左偏树的定义：

  1. 每个节点的键值满足堆性质（最大堆或最小堆）。
  2. 对于每个节点，其左子树的“零距离长度”（null path length）不小于右子树的零距离长度。零距离长度定义为从当前节点到最近的一个没有两个子节点的节点的路径长度。

左偏树的基本操作：

  1. 合并（Merge）：将两个左偏树合并成一个。合并操作的时间复杂度为O(log N)。
  2. 插入（Insert）：将一个节点插入到左偏树中。插入操作可以看作是合并一个只包含一个节点的左偏树，因此时间复杂度为O(log N)。
  3. 删除（Delete）：删除左偏树中的最大（或最小）元素。删除操作实际上是将根节点的左右子树合并，因此时间复杂度为O(log N)。

下面是一个简单的左偏树实现：

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <iostream>
#include <algorithm>

using namespace std;

struct Node {
    int key;
    int dist; // 零距离长度
    Node *left, *right;
};

Node* merge(Node* a, Node* b) {
    if (!a) return b;
    if (!b) return a;

    // 确保a的键值较小（最小堆）
    if (a->key > b->key) {
        swap(a, b);
    }

    // 将较小值的右子树与较大值合并
    a->right = merge(a->right, b);

    // 如果左子树的零距离长度小于右子树，则交换左右子树
    if (!a->left || a->left->dist < a->right->dist) {
        swap(a->left, a->right);
    }

    // 更新零距离长度
    a->dist = a->right ? a->right->dist + 1 : 0;

    return a;
}

void insert(Node*& root, int key) {
    Node* node = new Node {key, 0, nullptr, nullptr};
    root = merge(root, node);
}

int delete_min(Node*& root) {
    int min_key = root->key;
    root = merge(root->left, root->right);
    return min_key;
}

int main() {
    Node* root = nullptr;

    insert(root, 5);
    insert(root, 2);
    insert(root, 8);
    insert(root, 1);
    insert(root, 9);

    cout << "Deleted min: " << delete_min(root) << endl; // 输出：1
    cout << "Deleted min: " << delete_min(root) << endl; // 输出：2
    cout << "Deleted min: " << delete_min(root) << endl; // 输出：5

    Node* another_root = nullptr;
    insert(another_root, 7);
    insert(another_root, 3);
    insert(another_root, 6);

    // 合并两个左偏树
    root = merge(root, another_root);

    cout << "Deleted min: " << delete_min(root) << endl; // 输出：3
    cout << "Deleted min: " << delete_min(root) << endl; // 输出：6
    cout << "Deleted min: " << delete_min(root) << endl; // 输出：7

    return 0;
}
本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用