首页 > 其他分享 >【笔记/模板】二叉搜索树-平衡树

【笔记/模板】二叉搜索树-平衡树

时间：2024-11-04 10:45:15浏览次数：1  
标签：return val int tr 笔记 二叉 rank 节点 模板

二叉搜索树

www.luogu.com.cn

定义

二叉搜索树（\(\text{Binary Search Tree}\)）是一种形状如二叉树的数据结构，用于快速查找和增加删除操作，它有如下几个特殊性质：

  1. 空树是二叉搜索树。
  2. 若二叉搜索树的左子树不为空，则其左子树上所有点的附加权值均小于其根节点的值。
  3. 若二叉搜索树的右子树不为空，则其右子树上所有点的附加权值均大于其根节点的值。
  4. 二叉搜索树的左右子树均为二叉搜索树。

对于一个二叉搜索树，进行操作所花费的平均时间和这个二叉树的高度成正比。对于一个有 \(n\) 个结点的二叉搜索树中，这些操作的最优时间复杂度为 \(O(\log n)\)，最坏为 \(O(n)\)。

操作过程

定义

对于一个二叉搜索树的每一个节点，都要存储以下几样东西：

  1. 左子树节点和右子树节点：l 和 r
  2. 这一个节点上存储的权值：val
  3. 表示这个节点权值出现次数的计数器：cnt
  4. 代表这个树上的大小（即子树和自己大小之和）：size
struct BST
{
    int l, r;       // 左右子树节点
    int val;        // 这一个节点上存储的权值
    int cnt, size;  // 节点权值出现次数的计数器和这个树的大小
}tr[N];

与此同时，由于操作中需要不断插入新的数，因此还需要两个变量分别储存树的下标和当前的下标，我们用 root 和 idx 表示：

int root, idx;        // root表示这个树的根的下标，idx记录着当前的下标

创建新节点

创建一个新的节点就是将这个节点全部初始化，同时返回原来的下标值：

int new_node(int k)                    // 创建新节点
{
    tr[idx].val = k;                // 将权值修改
    tr[idx].size = tr[idx].cnt = 1; // 默认的子树的大小以及出现的次数肯定为1
    return idx;                     // 返回用过的下标（以后会用）
}

上传信息

像线段树一样，二叉搜索树同样也有需要维护的信息：每个子树的本身大小，有二叉树的性质可得出：

\[\text{tr[u].size = tr[tr[u].l].size + tr[tr[u].r].size + tr[u].cnt} \]

void pushup(int u)    // 上传信息
{
    tr[u].size = tr[tr[u].l].size + tr[tr[u].r].size + tr[u].cnt;
}

初始化

为了防止有时候询问的二叉搜索树为空，我们可以先在树中加入两个哨兵：\(\text{-INF}\) 和 \(\text{INF}\)，在不断的插入中，他们会始终在树的左右两端，从而有效防止查询越界。

void build()
{
    new_node(-INF), new_node(INF);  // 添加两个哨兵以防止越界RE
    root = 1, tr[1].r = 2;          // 让根节点为1，右子树节点为2
    pushup(root);                   // 上传更新节点大小
}

插入

根据二叉搜索树的性质可得，对于每个节点 \(u\) 以及要插入的权值 \(k\)，可以分为四种情况：

  1. \(u = k\) 时，直接在该节点的计数变量上 cnt ++。
  2. \(u < k\) 时，递归到该节点的右子树节点继续插入。
  3. \(u > k\) 时，递归到该节点的左子树节点继续插入。
  4. \(u = 0\) 时，则说明没有这个节点，直接利用 idx 创建一个。

\(\bold tips\)：在递归完之后要 pushup 一遍，从而维护每个子树的大小。

void insert(int &u, int k)
{
    if (u == 0) u = new_node(k);            // 如果节点为0，则直接新建一个
    else
    {
        if (tr[u].val == k) tr[u].cnt ++;   // 如果相等，则在计数器上加一个
        else
        {
            if (tr[u].val > k) insert(tr[u].l, k);  // 向左递归
            else insert(tr[u].r, k);                // 向右递归
        }
    }
    pushup(u);                              // 上传信息
}

删除

原理和插入相似，不多赘述，一共五种情况：

  1. \(u = k\) 时，直接在该节点的计数变量上 cnt --。
  2. \(u\) 节点为叶子节点时，直接 u = 0。
  3. \(u < k\) 时，递归到该节点的右子树节点继续删除。
  4. \(u > k\) 时，递归到该节点的左子树节点继续删除。
  5. \(u = 0\) 时，则说明没有这个节点，直接 return 掉 。

\(\bold tips\)：在递归完之后要 pushup 一遍，从而维护每个子树的大小。

void del(int &u, int k)
{
    if (u == 0) return ;                // 如果节点为0，直接return
    if (tr[u].val == k)                 // 如果权值相等，分三类讨论
    {
        if (tr[u].cnt > 1) tr[u].cnt --;        // 计数器大于1时，直接剪掉
        else 
        {
            if (tr[u].l || tr[u].r)             // 不是叶子节点时
            {
                if (!tr[u].r) del(tr[u].r, k);  // 如果有右子树，向右递归
                else del(tr[u].l, k);           // 否则向左递归
            }
            else u = 0;         // 是叶子节点直接改为0
        }
    }
    else if (tr[u].val > k) del(tr[u].l, k);    // 向左递归
    else del(tr[u].r, k);                       // 向右递归
    pushup(u);                      // 上传信息
}

找前驱

一个数 \(x\) 的前驱被定义为小于 \(x\) 的最大的数。

对于一个节点 \(u\) 的权值以及权值 \(k\)，它的查询分为以下三种情况：

  1. \(u = 0\) 时，此时说明找到了最左端，应当 return -INF。
  2. \(u \ge k\) 时，说明 $k $的前驱还可能在当前节点的左子树，向左递归。
  3. 其余的情况则说明 \(u \le k\)，此时分为两种情况，一是前驱就是 \(u\)，二是前驱在右子树当中，因此在两者中取 \(\max\)。
int get_prev(int u, int k)            // 找前驱
{
    if (u == 0) return -INF;        // 如果节点不存在，则直接返回-INF
    if (tr[u].val >= k) return get_prev(tr[u].l, k);    // k小于当前权值，向左递归
    return max(get_prev(tr[u].r, k), tr[u].val);        // 否则在两者之中取最大值
}

找后驱

一个数 \(x\) 的后驱被定义为大于 \(x\) 的最小的数。

原理同上

int get_next(int u, int k)            // 找后驱
{
    if (u == 0) return INF;         // 如果节点不存在，则直接返回INF
    if (tr[u].val <= k) return get_next(tr[u].r, k);    // k大于当前权值，向右递归
    return min(get_next(tr[u].l, k), tr[u].val);        // 否则在两者之中取最小值
}

通过排名找权值

排名定义为比当前数小的数的个数 \(+1\)。若有多个相同的数，应输出最小的排名。

对于一个节点 \(u\) 以及 \(rank\) 值，可以分为以下四种情况：

  1. \(\text{tr[u].val} = 0\) 时，说明这个权值无限大，返回 \(\text{INF}\)。
  2. \(\text{tr[tr[u].l].size } \ge \text{rank}\)，说明权值在左子树里面，向左递归。
  3. \(\text{tr[tr[u].l].size + tr[u].cnt} \ge \text{rank}\)，由于上面的限制条件，说明该节点权值即为答案。
  4. 否则向右进行递归，并且注意右子树中的 $rank $ 值是相对的。
int get_val_by_rank(int u, int rank)
{
    if (u == 0) return INF;     // 如果不存在这个节点，说明超出了最大值，返回INF
    if (tr[tr[u].l].size >= rank) return get_val_by_rank(tr[u].l, rank);    // 如果左子树的大小大于rank值，则说明权值在左子树里面，向左递归
    if (tr[tr[u].l].size + tr[u].cnt >= rank) return tr[u].val;             // 如果左子树的大小加上当前节点数大于rank值，收到前面条件的限制，说明val值为答案
    return get_val_by_rank(tr[u].r, rank - tr[tr[u].l].size - tr[u].cnt);   // 否则向右递归，并且向右递归时的rank值是相对于右子树的
}

通过权值找排名

原理和上面反过来差不多

int get_rank_by_val(int u, int k)
{
    if (u == 0) return 0;       // 如果不存在这个节点，则直接返回0
    if (tr[u].val == k) return tr[tr[u].l].size + 1;        // 如果节点权值等于k，返回这个排名的大小+1
    if (tr[u].val > k) return get_rank_by_val(tr[u].l, k);  // 如果节点权值大于k，则向左侧递归查找
    return tr[tr[u].l].size + tr[u].cnt + get_rank_by_val(tr[u].r, k);  // 否则应该向右递归，并且加上左子树和节点的大小之和
}

模板代码

// Problem: P5076 【深基16.例7】普通二叉树（简化版）
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5076
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
// #define int long long

const int N = 1e5 + 9;
const int INF = 2147483647;

struct BST
{
    int l, r;       // 左右子树节点
    int val;        // 这一个节点上存储的权值
    int cnt, size;  // 节点权值出现次数的计数器和这个树的大小
}tr[N];
int root, idx;        // root表示这个树的根的下标，idx记录着当前的下标

void pushup(int u)    // 上传信息
{
    tr[u].size = tr[tr[u].l].size + tr[tr[u].r].size + tr[u].cnt;
}

int new_node(int k)                    // 创建新节点
{
    tr[++ idx].val = k;             // 将权值修改
    tr[idx].size = tr[idx].cnt = 1; // 默认的子树的大小以及出现的次数肯定为1
    return idx;                     // 返回用过的下标（以后会用）
}

void build()
{
    new_node(-INF), new_node(INF);  // 添加两个哨兵以防止越界RE
    root = 1, tr[1].r = 2;          // 让根节点为1，右子树节点为2
    pushup(root);                   // 上传更新节点大小
}

void insert(int &u, int k)
{
    if (u == 0) u = new_node(k);            // 如果节点为0，则直接新建一个
    else
    {
        if (tr[u].val == k) tr[u].cnt ++;   // 如果相等，则在计数器上加一个
        else
        {
            if (tr[u].val > k) insert(tr[u].l, k);  // 向左递归
            else insert(tr[u].r, k);                // 向右递归
        }
    }
    pushup(u);                              // 上传信息
}

void del(int &u, int k)
{
    if (u == 0) return ;                // 如果节点为0，直接return
    if (tr[u].val == k)                 // 如果权值相等，分三类讨论
    {
        if (tr[u].cnt > 1) tr[u].cnt --;        // 计数器大于1时，直接剪掉
        else 
        {
            if (tr[u].l || tr[u].r)             // 不是叶子节点时
            {
                if (!tr[u].r) del(tr[u].r, k);  // 如果有右子树，向右递归
                else del(tr[u].l, k);           // 否则向左递归
            }
            else u = 0;         // 是叶子节点直接改为0
        }
    }
    else if (tr[u].val > k) del(tr[u].l, k);    // 向左递归
    else del(tr[u].r, k);                       // 向右递归
    pushup(u);                      // 上传信息
}

int get_rank_by_val(int u, int k)
{
    if (u == 0) return 0;       // 如果不存在这个节点，则直接返回0
    if (tr[u].val == k) return tr[tr[u].l].size + 1;        // 如果节点权值等于k，返回这个排名的大小+1
    if (tr[u].val > k) return get_rank_by_val(tr[u].l, k);  // 如果节点权值大于k，则向左侧递归查找
    return tr[tr[u].l].size + tr[u].cnt + get_rank_by_val(tr[u].r, k);  // 否则应该向右递归，并且加上左子树和节点的大小之和
}

int get_val_by_rank(int u, int rank)
{
    if (u == 0) return INF;     // 如果不存在这个节点，说明超出了最大值，返回INF
    if (tr[tr[u].l].size >= rank) return get_val_by_rank(tr[u].l, rank);    // 如果左子树的大小大于rank值，则说明权值在左子树里面，向左递归
    if (tr[tr[u].l].size + tr[u].cnt >= rank) return tr[u].val;             // 如果左子树的大小加上当前节点数大于rank值，收到前面条件的限制，说明val值为答案
    return get_val_by_rank(tr[u].r, rank - tr[tr[u].l].size - tr[u].cnt);   // 否则向右递归，并且向右递归时的rank值是相对于右子树的
}

int get_prev(int u, int k)            // 找前驱
{
    if (u == 0) return -INF;        // 如果节点不存在，则直接返回-INF
    if (tr[u].val >= k) return get_prev(tr[u].l, k);    // k小于当前权值，向左递归
    return max(get_prev(tr[u].r, k), tr[u].val);        // 否则在两者之中取最大值
}

int get_next(int u, int k)            // 找后驱
{
    if (u == 0) return INF;         // 如果节点不存在，则直接返回INF
    if (tr[u].val <= k) return get_next(tr[u].r, k);    // k大于当前权值，向右递归
    return min(get_next(tr[u].l, k), tr[u].val);        // 否则在两者之中取最小值
}

signed main()
{
    // ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    build();
    int n; cin >> n;
    while (n --)
    {
        int op, k; cin >> op >> k;
        if (op == 5) insert(root, k);
        else if (op == 1)
        {
            insert(root, k);
            cout << get_rank_by_val(root, k) - 1<< '\n';
            del(root, k);
        }
        else if (op == 2) cout << get_val_by_rank(root, k + 1) << '\n';
        else if (op == 3) cout << get_prev(root, k) << '\n';
        else cout << get_next(root, k) << '\n';
    }
    return 0;
}

平衡树

www.luogu.com.cn

www.luogu.com.cn

定义

平衡树简介

使用搜索树的目的之一是 缩短插入、删除、修改和查找（插入、删除、修改都包括查找操作）节点的时间。 关于查找效率，如果一棵树的高度为 \(h\)，在最坏的情况，查找一个关键字需要对比 \(h\) 次，查找时间复杂度（也为平均查找长度 \(\text{ASL，Average Search Length}\)）不超过 \(O(h)\)。一棵理想的二叉搜索树所有操作的时间可以缩短到 \(O(\log n)\)（\(n\) 是节点总数）。 然而 \(O(h)\) 的时间复杂度仅为理想情况。在最坏情况下，搜索树有可能退化为链表。想象一棵每个结点只有右孩子的二叉搜索树，那么它的性质就和链表一样，所有操作（增删改查）的时间是 \(O(n)\)。 可以发现操作的复杂度与树的高度 \(h\) 有关。由此引出了平衡树，通过一定操作维持树的高度（平衡性）来降低操作的复杂度。

一个平衡树有如下几个定义：

  1. 它是一个二叉搜索树
  2. 对于任意一个节点的子树，每一个节点的左子树和右子树的高度差最多为 \(1\)。

旋转Treap

简介

\(\text{Treap}\)（树堆）是一种 弱平衡 的 二叉搜索树。它同时符合二叉搜索树和堆的性质，名字也因此为 \(\text{tree}\)（树）和 \(\text{heap}\)（堆）的组合。

其中对于堆的性质是：

  • 子节点值（\(\textit{priority}\)）比父节点大或小（取决于是小根堆还是大根堆）。

https://oi-wiki.org/ds/images/treap-treap-example.svg

操作过程

旋转

旋转 \(\text{Treap}\)通过 左旋 和 右旋 的方式维护平衡树的平衡，通过调整堆的优先级从而达到平衡操作。

旋转操作的含义：

  • 在不影响搜索树性质的前提下，把和旋转方向相反的子树变成根节点（如左旋，就是把右子树变成根节点）
  • 不影响性质，并且在旋转过后，跟旋转方向相同的子节点变成了原来的根节点（如左旋，旋转完之后的左子节点是旋转前的根节点）

https://oi-wiki.org/ds/images/treap-rotate.svg

代码思路需要慢慢悟出来

void zig(int &u)                            // 右旋
{
    int v = tr[u].l;                        // v是节点u的左子节点
    tr[u].l = tr[v].r, tr[v].r = u, u = v;  // 依次更新节点
    pushup(tr[u].r), pushup(u);             // 上传标记
}

void zag(int &u)                            // 左旋
{
    int v = tr[u].r;                        // v是节点u的右子节点
    tr[u].r = tr[v].l, tr[v].l = u, u = v;  // 依次更新节点
    pushup(tr[u].l), pushup(u);             // 上传标记
}

插入

和二叉搜索树差不多，只不过要在插入的过程中维护好堆的性质。

void insert(int &u, int k)
{
    if (u == 0) u = new_node(k);            // 如果节点为0，则直接新建一个
    else
    {
        if (tr[u].val == k) tr[u].cnt ++;   // 如果相等，则在计数器上加一个
        else
        {
            if (tr[u].val > k)
            {
                insert(tr[u].l, k);     // 向左递归
                if (tr[tr[u].l].key > tr[u].key) zig(u); // 如果不满足堆的性质，右旋
            }
            else
            {
                insert(tr[u].r, k);     // 向右递归
                if (tr[tr[u].r].key < tr[u].key) zag(u); // 如果不满足堆的性质，左旋
            }
        }
    }
    pushup(u);                              // 上传信息
}

删除

同样维护好堆的性质

void del(int &u, int k)
{
    if (u == 0) return ;                // 如果节点为0，直接return
    if (tr[u].val == k)                 // 如果权值相等，分三类讨论
    {
        if (tr[u].cnt > 1) tr[u].cnt --;        // 计数器大于1时，直接剪掉
        else 
        {
            if (tr[u].l || tr[u].r)             // 不是叶子节点时
            {
                if (!tr[u].r || tr[tr[u].l].key > tr[tr[u].r].key) // 有右子树或者左子树的key大于右子树的key
                {
                    zig(u);             // 右旋
                    del(tr[u].r, k);    // 向右递归
                }
                else 
                {
                    zag(u);             // 左旋
                    del(tr[u].l, k);    // 否则向左递归
                }
            }
            else u = 0;         // 是叶子节点直接改为0
        }
    }
    else if (tr[u].val > k) del(tr[u].l, k);    // 向左递归
    else del(tr[u].r, k);                       // 向右递归
    pushup(u);                      // 上传信息
}

模板代码

// Problem: P3369 【模板】普通平衡树
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3369
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
// #define int long long

const int N = 1e5 + 9;
const int INF = 0x3f3f3f3f;

struct BST
{
    int l, r;       // 左右子树节点
    int val, key;   // val: 这一个节点上存储的权值  key: 随机数以满足堆的性质
    int cnt, size;  // 节点权值出现次数的计数器和这个树的大小
}tr[N];
int root, idx;        // root表示这个树的根的下标，idx记录着当前的下标

void pushup(int u)    // 上传信息
{
    tr[u].size = tr[tr[u].l].size + tr[tr[u].r].size + tr[u].cnt;
}

int new_node(int k)                    // 创建新节点
{
    tr[++ idx].val = k;             // 将权值修改
    tr[idx].key = rand();           // 给key赋予一个随机数
    tr[idx].size = tr[idx].cnt = 1; // 默认的子树的大小以及出现的次数肯定为1
    return idx;                     // 返回用过的下标（以后会用）
}

void build()
{
    new_node(-INF), new_node(INF);  // 添加两个哨兵以防止越界RE
    root = 1, tr[1].r = 2;          // 让根节点为1，右子树节点为2
    pushup(root);                   // 上传更新节点大小
}

void zig(int &u)                            // 右旋
{
    int v = tr[u].l;                        // v是节点u的左子节点
    tr[u].l = tr[v].r, tr[v].r = u, u = v;  // 依次更新节点
    pushup(tr[u].r), pushup(u);             // 上传标记
}

void zag(int &u)                            // 左旋
{
    int v = tr[u].r;                        // v是节点u的右子节点
    tr[u].r = tr[v].l, tr[v].l = u, u = v;  // 依次更新节点
    pushup(tr[u].l), pushup(u);             // 上传标记
}

void insert(int &u, int k)
{
    if (u == 0) u = new_node(k);            // 如果节点为0，则直接新建一个
    else
    {
        if (tr[u].val == k) tr[u].cnt ++;   // 如果相等，则在计数器上加一个
        else
        {
            if (tr[u].val > k)
            {
                insert(tr[u].l, k);     // 向左递归
                if (tr[tr[u].l].key > tr[u].key) zig(u); // 如果不满足堆的性质，右旋
            }
            else
            {
                insert(tr[u].r, k);     // 向右递归
                if (tr[tr[u].r].key < tr[u].key) zag(u); // 如果不满足堆的性质，左旋
            }
        }
    }
    pushup(u);                              // 上传信息
}

void del(int &u, int k)
{
    if (u == 0) return ;                // 如果节点为0，直接return
    if (tr[u].val == k)                 // 如果权值相等，分三类讨论
    {
        if (tr[u].cnt > 1) tr[u].cnt --;        // 计数器大于1时，直接剪掉
        else 
        {
            if (tr[u].l || tr[u].r)             // 不是叶子节点时
            {
                if (!tr[u].r || tr[tr[u].l].key > tr[tr[u].r].key) // 有右子树或者左子树的key大于右子树的key
                {
                    zig(u);             // 右旋
                    del(tr[u].r, k);    // 向右递归
                }
                else 
                {
                    zag(u);             // 左旋
                    del(tr[u].l, k);    // 否则向左递归
                }
            }
            else u = 0;         // 是叶子节点直接改为0
        }
    }
    else if (tr[u].val > k) del(tr[u].l, k);    // 向左递归
    else del(tr[u].r, k);                       // 向右递归
    pushup(u);                      // 上传信息
}

int get_rank_by_val(int u, int k)
{
    if (u == 0) return 0;       // 如果不存在这个节点，则直接返回0
    if (tr[u].val == k) return tr[tr[u].l].size + 1;        // 如果节点权值等于k，返回这个排名的大小+1
    if (tr[u].val > k) return get_rank_by_val(tr[u].l, k);  // 如果节点权值大于k，则向左侧递归查找
    return tr[tr[u].l].size + tr[u].cnt + get_rank_by_val(tr[u].r, k);  // 否则应该向右递归，并且加上左子树和节点的大小之和
}

int get_val_by_rank(int u, int rank)
{
    if (u == 0) return INF;     // 如果不存在这个节点，说明超出了最大值，返回INF
    if (tr[tr[u].l].size >= rank) return get_val_by_rank(tr[u].l, rank);    // 如果左子树的大小大于rank值，则说明权值在左子树里面，向左递归
    if (tr[tr[u].l].size + tr[u].cnt >= rank) return tr[u].val;             // 如果左子树的大小加上当前节点数大于rank值，收到前面条件的限制，说明val值为答案
    return get_val_by_rank(tr[u].r, rank - tr[tr[u].l].size - tr[u].cnt);   // 否则向右递归，并且向右递归时的rank值是相对于右子树的
}

int get_prev(int u, int k)            // 找前驱
{
    if (u == 0) return -INF;        // 如果节点不存在，则直接返回-INF
    if (tr[u].val >= k) return get_prev(tr[u].l, k);    // k小于当前权值，向左递归
    return max(get_prev(tr[u].r, k), tr[u].val);        // 否则在两者之中取最大值
}

int get_next(int u, int k)            // 找后驱
{
    if (u == 0) return INF;         // 如果节点不存在，则直接返回INF
    if (tr[u].val <= k) return get_next(tr[u].r, k);    // k大于当前权值，向右递归
    return min(get_next(tr[u].l, k), tr[u].val);        // 否则在两者之中取最小值
}

signed main()
{
    // ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    build();
    int n; cin >> n;
    while (n --)
    {
        int op, k; cin >> op >> k;
        if (op == 1) insert(root, k);
        else if (op == 2) del(root, k);
        else if (op == 3)
        {
            insert(root, k);
            cout << get_rank_by_val(root, k) - 1<< '\n';
            del(root, k);
        }
        else if (op == 4) cout << get_val_by_rank(root, k + 1) << '\n';
        else if (op == 5) cout << get_prev(root, k) << '\n';
        else cout << get_next(root, k) << '\n';
    }
    return 0;
}

标签：return,val,int,tr,笔记,二叉,rank,节点,模板
From： https://www.cnblogs.com/ThySecret/p/18524697

相关文章

  • 【笔记/模板】排序算法
    【模板】快速排序-洛谷1.冒泡排序排序原理：每次将未确定部分的相邻两个值对比，设为\(a_{i},a_{i+1}\)，如果\(a_{i}>a_{i+1}\),则对这两个值进行交换，可以使用swap来快速对两个值进行交换。那么，这样一轮交换下去，第一个数就可以确定是最小的了。以此类推，直到所有值都被确定，就得出......
  • 【笔记/模板】割点和桥
    割点对于一张无向图\(G=(V,E)\)，使得H是G的连通子图，且不存在\(F\)满足\(H\subsetneqF\inG\)且\(F\)为连通图，则称\(H\)是\(G\)的一个连通块/连通分量（connectedcomponent），又叫极大连通子图。由此，我们可以对割点做出如下定义：对于一个无向图，如果把一个点删除后......
  • 【笔记/模板】线段树（改）
    线段树线段树是OI竞赛中最强大的数据结构之一，可以用来维护和、积以及最值等具有合并性质的信息。一般线段树P3372【模板】线段树1-洛谷|计算机科学教育新生态(luogu.com.cn)P3373【模板】线段树2-洛谷|计算机科学教育新生态(luogu.com.cn)以模板一为例：cla......
  • 【笔记/模板】无向图的双连通分量
    边双连通分量定义在一张联通的无向图中，对于任意两点\(u\)和\(v\)​，删去两点之间任意一条边，都无法使其不连通（即连通数不变），我们就说这两点是边双连通。对于一个无向图中的极大边双连通的子图，我们称这个子图为一个边双连通分量。根据【笔记/模板】割点和桥中可知，如果......
  • 【笔记/模板】网络流初步
    网络流简介基本定义网络（Network）在图论中指一个有向图\(G=(V,E)\)，图上的每一条边都有一个值，叫做容量（Capacity），也有两个特殊点：源点（Source）和汇点（Sink）。而对于一张网络\(G\)，流（Flow）指的是一个函数\(f\)，\(f(u,v)\)表示边\(u\tov\)经过的流量，一个点\(u\)的净流量可以表示为......
  • 【笔记/模板】拓扑排序
    www.luogu.com.cn拓扑排序定义与实现思路拓扑排序（TopologicalSorting）是一个有向无环图（DAG,DirectedAcyclicGraph）的所有顶点的线性序列。且该序列必须满足下面两个条件：每个顶点出现且只出现一次。若存在一条从顶点A到顶点B的路径，那么在序列中顶点A出现在顶点B......
  • 【笔记/模板】树状数组
    原理解释树状数组是一种通过前缀和和差分的思想所进行的维护数组，从而以\(O(\logn)\)的时间复杂度进行修改和查询。一共有四种修改和查询的方式，分别是：单点修改\(+\)区间询问区间修改\(+\)单点询问单点修改\(+\)区间询问（二维）区间修改\(+\)区间询问其中利......
  • 【笔记/模板】树链剖分
    树链剖分树链剖分的基本思想通过将树分割成链的形式，从而把树形变为线性结构，减少处理难度。树链剖分（树剖/链剖）有多种形式，如重链剖分，长链剖分和用于Link/cutTree的剖分（有时被称作「实链剖分」），大多数情况下（没有特别说明时），「树链剖分」都指「重链剖分」。树链有如下几个特......
  • 【模板】矩阵运算
    不进行没必要的解释，主要记录模板。structMatrix{intn,m,rec[N][N]; //矩阵的长，宽和二维数组Matrix(int_n,int_m){n=_n,m=_m,memset(rec,0,sizeofrec);} //初始化函数voidreset(){n=0,m=0,memset(rec,0,sizeofrec);}......
  • 【笔记/模板】最近公共祖先（LCA）
    最近公共祖先（LCA）定义最近公共祖先（LowestCommonAncestor）简称LCA。对于一个树上的两个节点的最近公共祖先，是这两个点中的公共祖先里面离根最远的一个。性质可见OIWiki。向上标记法过程在两点中取得深度较大的一个点，让它不停的向上跳，同时标记所经过的每一个点，直到根节点，接......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99