平衡树相关笔记
引入
二叉查找树
二叉查找树(Binary Search Tree),又名二叉搜索树。满足以下性质:
- 对于非空的左子树,左子树点权值小于根节点。
- 对于非空的右子树,左子树点权值大于根节点。
- 二叉查找树的左右子树均是二叉查找树。
平衡树
在维持二叉查找树性质的基础上,通过改变其形态,控制深度在 log n \log n logn 级别。
平衡树左右两个子树高度差不大于 1 1 1,否则需要进行左旋 / 右旋操作。

pb_ds
在 C++ 的 pb_ds 中有封装好的平衡树。
tree 类型的平衡树常数稍大,速度略慢。
声明方式
有以下声明(来源于官方文档):
template<typename Key,typename Mapped,typename Cmp_Fn = std::less<Key>,typename Tag = rb_tree_tag,template<typename Const_Node_Iterator,typename Node_Iterator,typename Cmp_Fn_,typename Allocator_>class Node_Update = null_tree_node_update,typename Allocator = std::allocator<char> >
class tree;
常用的定义方式为 tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>。
- 第一个参数表示存储元素(Key)的类型;
- 第二个参数表示映射规则(Mapped-Policy)的类型,常用的是
null_type,表示无映射; - 第三个参数表示比较规则(
Cmp_Fn); - 第四个参数表示平衡树的类型(
Tag),有rb_tree_tag(红黑树)、splay_tree_tag等; - 第五个参数表示更新节点的策略(
Node_Update),默认为null_node_update,如果要使用查询排名相关操作,需要使用tree_order_statisitics_node_update。
常用操作
其中 x 表示存储元素的类型。
insert(x):插入元素 x x x。erase(x):删除元素 x x x。order_of_key(x):查询元素 x x x 的排名(前面有多少数比 x x x 小),返回值为整数。find_by_order(x):查询排名为 x x x 的元素对应的迭代器。lower_bound(x)、upper_bound(x):返回迭代器。join(x):将 x x x 树并入当前树,要求两树值域不能重叠。合并后 x x x 树被清空。split(x,b):小于等于 x x x 的属于当前树,其余的属于 b b b 树。size():返回大小。
以下是 P3369 【模板】普通平衡树 的代码。
注意用 pb_ds 实现的 tree 类似于一个 set,元素是不可重的。所以我们把元素以 pair 的形式存储,再记录一个元素被插入到 tree 的时间。
prev(it) 函数可以求迭代器 it 的前驱(即前一个位置)。注意求 x x x 的后继时,用 upper_bound() 操作的键值对应该是 pair<x,INT_MAX>,避免查找到和 x x x 相等但插入时间比 x x x 晚的元素。
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;tree<pair<int,int>,null_type,less<pair<int,int> >,rb_tree_tag,tree_order_statistics_node_update> t;int main()
{int n;cin>>n;for(int i=1;i<=n;i++){int op,x;cin>>op>>x;if(op==1) t.insert({x,i});if(op==2) t.erase(t.upper_bound({x,0}));if(op==3) cout<<t.order_of_key({x,0})+1<<endl;if(op==4){auto it=t.find_by_order(x-1);cout<<(*it).first<<endl;}if(op==5){auto it=prev(t.lower_bound({x,0}));cout<<(*it).first<<endl;}if(op==6){auto it=t.upper_bound({x,INT_MAX});cout<<(*it).first<<endl;}}return 0;
}
相关文章:
平衡树相关笔记
引入 二叉查找树 二叉查找树(Binary Search Tree),又名二叉搜索树。满足以下性质: 对于非空的左子树,左子树点权值小于根节点。对于非空的右子树,左子树点权值大于根节点。二叉查找树的左右子树均是二叉…...
ASP.net C# 用Aspose.pdf实现pdf合并
直接上代码,供参考,备忘! using System; using System.Collections.Generic; using System.Web; using System.Web.UI; using System.Web.UI.WebControls; using System.Data; using System.Data.SqlClient; using System.Xml; using System…...
C语言实现原码一位除
具体代码如下,直接运行即可。 #include <stdio.h> int main() {int i, a 0, b 0, c 0, flag 3; // flag相当于指针来指明Q的位置char x[6], y[6];int R[6], Q[6], yb[6], y1[6]; // yb是-y的补码,y1为绝对值yprintf("请输入X(带一位符号位四位数值位…...
three.js点滴yan(整理后)
场景、相机和渲染器 Three.js整个系统主要包含场景Scene、相机Camera和WebGL渲染器WebGLRenderer三大块,其中场景又包含模型和光源。WebGL渲染器的主要作用就是把相机对应场景渲染出来,显示在网页Cnavas画布上。 Three.js源码 Three.js各个构造函数对应…...
VMware安装CentOS最小化开发环境导引
目录 一、概要 二、介绍 三、下载 四、安装 4.1 创建虚拟机 4.2 安装CentOS 五、配置网卡 六、配置本地安装源 七、安装软件 7.1 gcc/g 7.2 C的atomic库 7.3 java 7.4 Cmake 7.5 MariaDB客户端(兼容mysql) 八、用户配置文件.bash_profile…...
服务器端编程/数据库驱动程序/RESTful API:介绍
目录 服务器端编程数据库驱动程序RESTful API 👍 点赞,你的认可是我创作的动力! ⭐️ 收藏,你的青睐是我努力的方向! ✏️ 评论,你的意见是我进步的财富! 服务器端编程 服务器端编程是一种计…...
Qwt QwtThermo绘制温度计
1.简介 QwtThermo 是一个基于 Qt 框架的类库,用于创建温度计控件。它提供了一些方便的功能来展示和处理温度计相关的数据。 QwtThermo 添加了特定于温度计的功能。 使用 QwtThermo,可以实现以下功能: 设置温度范围:可以通过设置…...
U_boot介绍
系统移植之前的了解的: 首先需要移植一个 bootloader 代码,这个 bootloader 代码用于启动 Linux 内核,bootloader 有很多,常用的就是 U-Boot;移植好 U-Boot 以后再移植 Linux 内核,移植完 Linux 内核以后 Linux 还不能…...
Flink -- window(窗口)
1、窗口主要分成三大种: 1、Time Window (时间窗口):固定时间触发一次窗口 a、SlidingEventTimeWindows: 滑动的事件时间窗口 public class Demo1TImeWindow {public static void main(String[] args) throws Exception {/*** 时…...
原语:串并转换器
串并转换器OSERDESE2 可被Select IO IP核调用。 OSERDESE2允许DDR功能 参考: FPGA原语学习与整理第二弹,OSERDESE2串并转换器 - 知乎 (zhihu.com) 正点原子。 ISERDESE2原语和OSERDESE2原语是串并转换器,他的的功能都是实现串行数据和并行…...
没网络也能安装.Net 3.5!如何脱机安装.NET Framework 3.5
.NET框架是由微软制定的一个软件框架。它有助于在Windows上运行控制台、Web或移动应用程序。此有用的工具适用于Windows设备。 如何脱机安装.NET Framework 3.5 如果你拥有Windows 10、8、8.1或7,有时第三方软件可能会导致问题。你可能会在图片中看到这样的问题。 看这张照片…...
JVM运行时数据区-虚拟机栈
目录 一、内存中的栈 二、基本内容 三、优点 四、栈的存储单位 五、栈运行原理 六、栈的内部结构 (一)局部变量表 (二)操作数栈 (三)动态链接 (四)方法返回地址 …...
Java中介者模式
目录 定义 结构 案例 优点 缺点 使用场景 定义 又叫调停模式,定义一个中介角色来封装一系列对象之间的交互,使原有对象之间的耦合松散,且可以独立地改变它们之间的交互。 结构 中介者模式包含以下主要角色: 抽象中介者角…...
前端框架Vue学习 ——(五)前端工程化Vue-cli脚手架
文章目录 Vue-cliVue项目-创建Vue项目-目录结构Vue项目-启动Vue项目-配置端口Vue项目开发流程 Vue-cli 介绍:Vue-cli 是 Vue 官方提供的一个脚手架,用于快速生成一个 Vue 的项目模版 安装 NodeJS安装 Vue-cli npm install -g vue/cliVue项目-创建 图…...
App备案-iOS云管理式证书 Distribution Managed 公钥及证书SHA-1指纹的获取方法
根据近日工业和信息化部发布的《工业和信息化部关于开展移动互联网应用程序备案工作的通知》,相信不少要进行IOS平台App备案的朋友遇到了一个问题,就是apple不提供云管理式证书的下载,也就无法获取公钥及证书SHA-1指纹。 已经上架的应用不想重…...
Spring -Spring之依赖注入源码解析
依赖注入底层原理流程图:Spring中Bean的依赖注入原理| ProcessOn免费在线作图,在线流程图,在线思维导图 Spring中到底有几种依赖注入的方式? 首先分两种: 手动注入自动注入 手动注入 在XML中定义Bean时,就是手动注入…...
Spire.Office for .NET 8.10.2 同步更新-Crk
Spire.Office for .NET是 E-iceblue 提供的企业级 Office .NET API 的组合。它包括Spire.Doc、Spire.XLS、Spire.Spreadsheet、Spire.Presentation、Spire.PDF、Spire.DataExport、Spire.OfficeViewer、Spire.PDFViewer、Spire.DocViewer、Spire.Barcode和Spire.Email。Spire.O…...
MFC 基础篇(一)
目录 一.SDK编程 二.为什么要学MFC? 三.MFC能做什么? 四.MFC开发环境搭建 五.MFC项目创建 六.消息映射机制 一.SDK编程 Application Programming Interface 应用程序编程接口。 Software Development Kit 软件开发工具包,一般会包括A…...
Android技术-修改SO导出符号
背景 经常在使用第三方SDK的时候会莫名其妙报错,其中最常见的一种就是SO符号冲突,比如libA.so静态链接了libC.a,而libB.so动态链接了libC.so。这样便会导致符号冲突。又或者在使用不同版本的动态库,也会造成符号冲突。 报错案例 案例1 DEB…...
flutter 打包apk
Flutter项目打包生成APK_flutter打包apk_文阿花的博客-CSDN博客 关于iconData可能出现的错误: flutter build apk 打包报错调试过程 - 掘金 (juejin.cn) 使用命令行:flutter build apk --no-tree-shake-icons...
铭豹扩展坞 USB转网口 突然无法识别解决方法
当 USB 转网口扩展坞在一台笔记本上无法识别,但在其他电脑上正常工作时,问题通常出在笔记本自身或其与扩展坞的兼容性上。以下是系统化的定位思路和排查步骤,帮助你快速找到故障原因: 背景: 一个M-pard(铭豹)扩展坞的网卡突然无法识别了,扩展出来的三个USB接口正常。…...
推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材)
推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材) 这个项目能干嘛? 使用 gemini 2.0 的 api 和 google 其他的 api 来做衍生处理 简化和优化了文生图和图生图的行为(我的最主要) 并且有一些目标检测和切割(我用不到) 视频和 imagefx 因为没 a…...
CSS | transition 和 transform的用处和区别
省流总结: transform用于变换/变形,transition是动画控制器 transform 用来对元素进行变形,常见的操作如下,它是立即生效的样式变形属性。 旋转 rotate(角度deg)、平移 translateX(像素px)、缩放 scale(倍数)、倾斜 skewX(角度…...
jmeter聚合报告中参数详解
sample、average、min、max、90%line、95%line,99%line、Error错误率、吞吐量Thoughput、KB/sec每秒传输的数据量 sample(样本数) 表示测试中发送的请求数量,即测试执行了多少次请求。 单位,以个或者次数表示。 示例:…...
【 java 虚拟机知识 第一篇 】
目录 1.内存模型 1.1.JVM内存模型的介绍 1.2.堆和栈的区别 1.3.栈的存储细节 1.4.堆的部分 1.5.程序计数器的作用 1.6.方法区的内容 1.7.字符串池 1.8.引用类型 1.9.内存泄漏与内存溢出 1.10.会出现内存溢出的结构 1.内存模型 1.1.JVM内存模型的介绍 内存模型主要分…...
android13 app的触摸问题定位分析流程
一、知识点 一般来说,触摸问题都是app层面出问题,我们可以在ViewRootImpl.java添加log的方式定位;如果是touchableRegion的计算问题,就会相对比较麻烦了,需要通过adb shell dumpsys input > input.log指令,且通过打印堆栈的方式,逐步定位问题,并找到修改方案。 问题…...
什么是VR全景技术
VR全景技术,全称为虚拟现实全景技术,是通过计算机图像模拟生成三维空间中的虚拟世界,使用户能够在该虚拟世界中进行全方位、无死角的观察和交互的技术。VR全景技术模拟人在真实空间中的视觉体验,结合图文、3D、音视频等多媒体元素…...
MFE(微前端) Module Federation:Webpack.config.js文件中每个属性的含义解释
以Module Federation 插件详为例,Webpack.config.js它可能的配置和含义如下: 前言 Module Federation 的Webpack.config.js核心配置包括: name filename(定义应用标识) remotes(引用远程模块࿰…...
STM32标准库-ADC数模转换器
文章目录 一、ADC1.1简介1. 2逐次逼近型ADC1.3ADC框图1.4ADC基本结构1.4.1 信号 “上车点”:输入模块(GPIO、温度、V_REFINT)1.4.2 信号 “调度站”:多路开关1.4.3 信号 “加工厂”:ADC 转换器(规则组 注入…...
基于 HTTP 的单向流式通信协议SSE详解
SSE(Server-Sent Events)详解 🧠 什么是 SSE? SSE(Server-Sent Events) 是 HTML5 标准中定义的一种通信机制,它允许服务器主动将事件推送给客户端(浏览器)。与传统的 H…...
