首页 > 其他分享 >洛谷题单指南-字符串-P3369 【模板】普通平衡树

洛谷题单指南-字符串-P3369 【模板】普通平衡树

时间:2024-11-01 14:58:14浏览次数:1  
标签:val int 洛谷题 tr else trie P3369 siz 模板

原题链接:https://www.luogu.com.cn/problem/P3369

题意解读:平衡树的基本操作,模版题。

解题思路:

1、二叉搜索树-BST

二叉搜索树满足这样的性质:每一个节点的权值大于它的左儿子,小于它的右儿子。

对BST进行中序遍历,将得到一个从小到大的有序序列,因此BST是为了维护一个有序序列的动态添加、删除、查找。

随机情况下,对树进行插入、查找、删除等操作的时间复杂度都是O(logN),

但是如果插入顺序是一个已经有序的序列,将退化成一条链,时间复杂度变成O(N)。

2、平衡树

平衡树就是为了解决BST中高度不均衡导致时间复杂度上升的问题,

为了使某个节点左右子树高度尽可能差距小,需要进行两个重要的操作:左旋、右旋

左旋:将以E为根的子树左旋,先令S = E->right,再E->right = S->left,然后S->left = E

右旋:将以S为根的子树右旋,先令E = S->left,再S->left = E->right,然后E->right = S

平衡树的具体实现方式有多种,如AVL、红黑树、Treap、Splay、Trie等等,本文主要介绍最好写的两种:Trie、Treap。

3、用01-Trie平替平衡树

为什么01-Trie可以平替平衡树?

首先,01-Trie高度是固定的,显然满足平衡的特点。

其次,01-Trie也满足左子树对应的值更小,右子树对应的值更大,能够维护序列的有序性。

最后,01-Trie实现平衡树,需要记录一些额外的信息:每个结点所在子树一共有有多个元素

但是,01-Trie作为平衡树也有一些缺点,比如:

占用空间较大,每个整数都拆成二进制作为树的节点。

不能处理负数,但是可以加上一个较大的数将负数转正。

在数据量不太大的情况下,还是可以使用的。

Trie实现平衡树的基本操作:

本题元素大小|x|<=10^7

设int trie[N * 26][2], idx表示Trie树,int siz[N * 26]记录每个节点所在子树的元素个数。

a、插入

void add(int val)
{
    int u = 0;
    for(int i = 25; i >= 0; i--)
    {
        int v = val >> i & 1;
        if(!trie[u][v]) trie[u][v] = ++idx;
        u = trie[u][v];
        siz[u]++;
    }
}

b、删除

void del(int val)
{
    int u = 0;
    for(int i = 25; i >= 0; i--)
    {
        int v = val >> i & 1;
        if(!trie[u][v]) return;
        u = trie[u][v];
        siz[u]--;
    }
}

c、查找小于x的元素个数

int get_less(int val)
{
    int res = 0;
    int u = 0;
    for(int i = 25; i >= 0; i--)
    {
        int v = val >> i & 1;
        if(v == 1) res += siz[trie[u][0]]; //如果val在右子树,则左子树所有数都是小于val的,要累加
        u = trie[u][v];
        if(!u) break; //如果val不存在,到这里就可以结束
    }
    return res;
}

d、查找第k个数

int get_kth(int k)
{
    int res = 0;
    int u = 0;
    for(int i = 25; i >= 0; i--)
    {
        if(siz[trie[u][0]] < k) //左子树数量不足k,在右子树找
        {
            k -= siz[trie[u][0]]; //k要减去左子树的数量
            u = trie[u][1];
            res = res * 2 + 1;
        } 
        else 
        {
            u = trie[u][0];
            res = res * 2;
        }
        if(!u) break;
    }
    return res - INF;
}

100分代码:

#include <bits/stdc++.h>
using namespace std;

const int N = 100005, INF = 1e7;

int trie[N * 26][2], idx;
int siz[N * 26]; //siz[i]表示节点i所在子树中数的个数,根节点不需要记录

//插入元素到trie
void add(int val)
{
    int u = 0;
    for(int i = 25; i >= 0; i--)
    {
        int v = val >> i & 1;
        if(!trie[u][v]) trie[u][v] = ++idx;
        u = trie[u][v];
        siz[u]++;
    }
}

//从trie中删除元素
void del(int val)
{
    int u = 0;
    for(int i = 25; i >= 0; i--)
    {
        int v = val >> i & 1;
        if(!trie[u][v]) return;
        u = trie[u][v];
        siz[u]--;
    }
}

//获取小于val的元素数量
int get_less(int val)
{
    int res = 0;
    int u = 0;
    for(int i = 25; i >= 0; i--)
    {
        int v = val >> i & 1;
        if(v == 1) res += siz[trie[u][0]];
        u = trie[u][v];
        if(!u) break; //如果val不存在,到这里就可以结束
    }
    return res;
}

//获取排名第k的元素
int get_kth(int k)
{
    int res = 0;
    int u = 0;
    for(int i = 25; i >= 0; i--)
    {
        if(siz[trie[u][0]] < k) //左子树数量不足k,在右子树找
        {
            k -= siz[trie[u][0]];
            u = trie[u][1];
            res = res * 2 + 1;
        } 
        else 
        {
            u = trie[u][0];
            res = res * 2;
        }
        if(!u) break;
    }
    return res - INF;
}

int main()
{
    int n;
    cin >> n;
    int opt, x;
    while(n--)
    {
        cin >> opt >> x;
        if(opt == 1) x += INF, add(x); //元素值+INF,使得必然为非负数,才能加入01trie
        else if(opt == 2) x += INF, del(x);
        else if(opt == 3) x += INF, cout << get_less(x) + 1 << endl;
        else if(opt == 4) cout << get_kth(x) << endl;
        else if(opt == 5) x += INF, cout << get_kth(get_less(x)) << endl;
        else x += INF, cout << get_kth(get_less(x + 1) + 1) << endl;
    }
    return 0;
}

4、Treap平衡树

Treap是Tree+Heap,也就是树+堆,通过树来维护BST结构,通过堆的性质来保证尽可能平衡。

具体来说,树的节点定义为:

struct Node
{
    int l, r; //l左子树,r右子树
    int val, pri; //val是节点权值,pri是随机数用来维护堆的性质
    int siz, cnt; //siz是节点为根的子树大小,cnt是节点重复元素的个数
} tr[N];
int idx; //树节点编号
int root; //根节点

通过val来维护BST的性质,如果val严格有序将导致树退化成链,因此引入一个随机数pri,并强制父节点的pri大于子节点pri(大根堆性质),通过维护此性质即可保持树的平衡。

通过siz,cnt这些附加信息,就可以实现查元素排名、查第k个元素、找前驱、找后继等操作。

Treap维护树的平衡只需要在插入元素的时候判断,如果插入元素后,导致子节点的pri大于父节点的pri,则进行相应的旋转操作(左旋or右旋)。

100分代码:

#include <bits/stdc++.h>
using namespace std;

const int N = 100005, INF = 1e8;

struct Node
{
    int l, r; //l左子树,r右子树
    int val, pri; //val是节点权值,pri是随机数用来维护堆的性质
    int siz, cnt; //siz是节点为根的子树大小,cnt是节点重复元素的个数
} tr[N];
int idx; //树节点编号
int root; //根节点

//生成一个新节点
int get_node(int val)
{
    tr[++idx].val = val;
    tr[idx].pri = rand(); //随机值,通过维护大根堆特性确保尽量平衡
    tr[idx].siz = tr[idx].cnt = 1;
    return idx;
}

//计算子树siz
void pushup(int &p)
{
    tr[p].siz = tr[tr[p].l].siz + tr[tr[p].r].siz + tr[p].cnt;
}

//右旋
void rotate_to_r(int &p)
{
    int t = tr[p].l; 
    tr[p].l = tr[t].r;
    tr[t].r = p;
    p = t;
    pushup(tr[p].r);
    pushup(p);
}

//左旋
void rotate_to_l(int &p)
{
    int t = tr[p].r;
    tr[p].r = tr[t].l;
    tr[t].l = p;
    p = t;
    pushup(tr[p].l);
    pushup(p);
}   

//初始化树
void build_tree()
{   
    //树中添加两个初始节点:极大值和极小值,避免出现边界问题
    get_node(-INF); 
    get_node(INF);
    root = 1;
    tr[root].r = 2;
    pushup(root);
    if(tr[1].pri < tr[2].pri) rotate_to_l(root);
}

void insert(int &p, int val)
{
    if(!p) p = get_node(val);
    else if(tr[p].val == val) tr[p].cnt++;
    else if(tr[p].val > val) 
    {
        insert(tr[p].l, val);
        if(tr[tr[p].l].pri > tr[p].pri) rotate_to_r(p); //插入左子树后对不满足堆性质进行调整
    }
    else
    {
        insert(tr[p].r, val);
        if(tr[tr[p].r].pri > tr[p].pri) rotate_to_l(p); //插入右子树后对不满足堆性质进行调整
    }
    pushup(p);
}

void erase(int &p, int val)
{
    if(!p) return;
    else if(tr[p].val == val)
    {
        if(tr[p].cnt > 1) tr[p].cnt--; //找到有多个,减一个
        else if(!tr[p].l && !tr[p].r) //叶子节点,直接删除
        {
            p = 0;
        }
        else if(!tr[p].r || tr[tr[p].l].pri > tr[tr[p].r].pri) 
        { //如果只有左子树,或者左子树pri大于右子树,则右旋,然后去右子树删除
            rotate_to_r(p);
            erase(tr[p].r, val);
        }
        else if(!tr[p].l || tr[tr[p].r].pri > tr[tr[p].l].pri)
        { //如果只有右子树,或者右子树pri大于左子树,则左旋,然后去左子树删除
            rotate_to_l(p);
            erase(tr[p].l, val);
        }
    }
    else if(tr[p].val > val) erase(tr[p].l, val);
    else erase(tr[p].r, val);
    pushup(p);
}

//查询比val小的数的个数,由于第一个节点是-INF,因此比val小的数的个数就是排名
int get_less(int p, int val)
{
    if(!p) return 0; 
    else if(tr[p].val == val) return tr[tr[p].l].siz; //p就是val,则p左子树大小就是比val小的数的个数
    else if(tr[p].val > val) return get_less(tr[p].l, val); //到左子树找
    else if(tr[p].val < val) return tr[p].cnt + tr[tr[p].l].siz + get_less(tr[p].r, val); //到右子树找,p和p的左子树都比val小,要累加
}

//查询第k个数
int get_kth(int p, int k)
{
    if(!p) return 0; //没有找到
    else if(tr[tr[p].l].siz >= k) return get_kth(tr[p].l, k); //到左子树找
    else if(tr[tr[p].l].siz + tr[p].cnt >= k) return tr[p].val; //p就是第k个
    else if(tr[tr[p].l].siz < k) return get_kth(tr[p].r, k - tr[tr[p].l].siz - tr[p].cnt); //到右子树找
}

//查找val的前驱,比val小的最大数
int get_prev(int p, int val)
{
    if(!p) return -INF;
    else if(tr[p].val >= val) return get_prev(tr[p].l, val);
    else return max(tr[p].val, get_prev(tr[p].r, val));
}

//查找val的后继,比val大的最小数
int get_next(int p, int val)
{
    if(!p) return INF;
    else if(tr[p].val <= val) return get_next(tr[p].r, val);
    else return min(tr[p].val, get_next(tr[p].l, val));
}

int main()
{
    int n;
    cin >> n;
    int opt, x;
    build_tree();
    while(n--)
    {
        cin >> opt >> x;
        if(opt == 1) insert(root, x);
        else if(opt == 2) erase(root, x);
        else if(opt == 3) cout << get_less(root, x) << endl;
        else if(opt == 4) cout << get_kth(root, x + 1) << endl;
        else if(opt == 5) cout << get_prev(root, x) << endl;
        else if(opt == 6) cout << get_next(root, x) << endl;
    }
    return 0;
}

 

标签:val,int,洛谷题,tr,else,trie,P3369,siz,模板
From: https://www.cnblogs.com/jcwy/p/18513114

相关文章

  • 模板初阶及STL简介
    目录一.模板初阶1.泛型函数2.函数模板1.函数模板概念2.函数模板使用格式3.函数模板的原理4.函数模板的实例化5.模板参数的匹配原则3.类模板1.类模板的定义格式2.类模板的实例化二.STL简介1.什么是STL2.STL的版本3.STL的六大组件4.如何学习STL5.STL的缺陷......
  • 在Codeigniter中使用Blade模板引擎
    使用compoer引入blade库composerrequire"philo/laravel-blade":"3.*"在helpers目录下创建view_helper.php<?phpif(!defined('BASEPATH'))exit('Nodirectscriptaccessallowed');require_once'vendor/autoload.php';......
  • 模板模式、责任链模式的使用
    背景​ 当前系统从其他业务系统的获取业务数据,再结合模板来生成票据。生成过程包含模板匹配、票据构建、票据校验、票据保存。同时需要支持三种生成方式,即定时任务自动生成、批量生成、单个生成。​ 对于不同业务类型数据,生成票据过程存在细微差异(获取业务数据、单据校验等......
  • flask模板
    模板基础使用block块操作父模板挖坑,子模板填坑{%blockxxx%}{%endblock%extends继承{%extends'xxx'%}继承后保留块中的内容{{super()}}include包含,将其他htm1包含进来{%include'xxx'%}宏的使用 宏定义:Python函数#}{%macroperson(name,ag......
  • STM32F103C8T6学习笔记1--新建工程模板
    1、简介STM32是一系列由STMicroelectronics(瑞士意法半导体)公司设计和生产的32位微控制器产品线。这些微控制器基于ARMCortex-M内核,并具有高性能、低功耗和多种外设接口的特点。STM32处理器被广泛应用于各种嵌入式系统领域,包括工业控制、消费电子、汽车电子、物联网等。STM32......
  • C++笔记---可变参数模板
    1.简单介绍与基本语法可变参数模板是指模板的类型参数列表的的参数个数可变。C++11支持可变参数模板,也就是说支持可变数量参数的函数模板和类模板,可变数目的参数被称为参数包,存在两种参数包:模板参数包:表示零或多个模板参数。函数参数包:表示零或多个函数参数。参数包的......
  • 常用算法模板
    数论组合数方法1(小数据)数据范围\(1\leqn\leq10000\),\(1\leqb\leqa\leq2000\)说明通过递推预处理组合数公式\(C^{b}_{a}=C^{b}_{a-1}+C^{b-1}_{a-1}\)LLC[N][N];voidinit(){for(inti=0;i<N;i++){for(intj=0;j<=......
  • C++泛型一:模板
    数据类型给程序设计带来的困扰及解决方案intmaxt(int,int);doublemaxt(double,double);若有一种占位符T,能够代替类型,便可以简化代码的冗余编写Tmaxt(T,T);C++模板模板声明如下template<typenameT1,...>template是C++的模板声明关键字,尖括号内为模板参数列表typ......
  • 界面控件Kendo UI for Angular 2024 Q3亮点 - 全新的页面模板
    随着最新的2024Q3版本,Progress使用户能够使用现成的页面模板和构建块更快地构建令人惊叹的应用程序,使您的Telerik和KendoUI开发体验更好。Telerik和KendoUI 2024Q3版本将焦点放在新推出的页面模板和构建块上,每个页面模板和构建块都预先配置了TelerikUIforBlazor、KendoU......
  • 管家婆工贸ERP BB067.销售订单修改BOM类型+BB068.销售单按模板导出Excel
    BB067.销售订单修改BOM类型最低适用版本:工贸系列23.0插件简要功能说明:销售订单任意状态下,支持通过应用按钮将焦点行的BOM类型修改为订单BOM更多细节描述见下方详细文档插件操作视频:进销存类定制插件--销售订单修改BOM类型插件详细功能文档:销售订单增加应......