当前位置: 首页 > news >正文

平衡树相关笔记

引入

二叉查找树

二叉查找树(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;
}

相关文章:

平衡树相关笔记

引入 二叉查找树 二叉查找树&#xff08;Binary Search Tree&#xff09;&#xff0c;又名二叉搜索树。满足以下性质&#xff1a; 对于非空的左子树&#xff0c;左子树点权值小于根节点。对于非空的右子树&#xff0c;左子树点权值大于根节点。二叉查找树的左右子树均是二叉…...

ASP.net C# 用Aspose.pdf实现pdf合并

直接上代码&#xff0c;供参考&#xff0c;备忘&#xff01; 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语言实现原码一位除

具体代码如下&#xff0c;直接运行即可。 #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三大块&#xff0c;其中场景又包含模型和光源。WebGL渲染器的主要作用就是把相机对应场景渲染出来&#xff0c;显示在网页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客户端&#xff08;兼容mysql&#xff09; 八、用户配置文件.bash_profile…...

服务器端编程/数据库驱动程序/RESTful API:介绍

目录 服务器端编程数据库驱动程序RESTful API &#x1f44d; 点赞&#xff0c;你的认可是我创作的动力&#xff01; ⭐️ 收藏&#xff0c;你的青睐是我努力的方向&#xff01; ✏️ 评论&#xff0c;你的意见是我进步的财富&#xff01; 服务器端编程 服务器端编程是一种计…...

Qwt QwtThermo绘制温度计

1.简介 QwtThermo 是一个基于 Qt 框架的类库&#xff0c;用于创建温度计控件。它提供了一些方便的功能来展示和处理温度计相关的数据。 QwtThermo 添加了特定于温度计的功能。 使用 QwtThermo&#xff0c;可以实现以下功能&#xff1a; 设置温度范围&#xff1a;可以通过设置…...

U_boot介绍

系统移植之前的了解的&#xff1a; 首先需要移植一个 bootloader 代码&#xff0c;这个 bootloader 代码用于启动 Linux 内核&#xff0c;bootloader 有很多&#xff0c;常用的就是 U-Boot;移植好 U-Boot 以后再移植 Linux 内核&#xff0c;移植完 Linux 内核以后 Linux 还不能…...

Flink -- window(窗口)

1、窗口主要分成三大种&#xff1a; 1、Time Window &#xff08;时间窗口&#xff09;&#xff1a;固定时间触发一次窗口 a、SlidingEventTimeWindows: 滑动的事件时间窗口 public class Demo1TImeWindow {public static void main(String[] args) throws Exception {/*** 时…...

原语:串并转换器

串并转换器OSERDESE2 可被Select IO IP核调用。 OSERDESE2允许DDR功能 参考&#xff1a; FPGA原语学习与整理第二弹&#xff0c;OSERDESE2串并转换器 - 知乎 (zhihu.com) 正点原子。 ISERDESE2原语和OSERDESE2原语是串并转换器&#xff0c;他的的功能都是实现串行数据和并行…...

没网络也能安装.Net 3.5!如何脱机安装.NET Framework 3.5

.NET框架是由微软制定的一个软件框架。它有助于在Windows上运行控制台、Web或移动应用程序。此有用的工具适用于Windows设备。 如何脱机安装.NET Framework 3.5 如果你拥有Windows 10、8、8.1或7,有时第三方软件可能会导致问题。你可能会在图片中看到这样的问题。 看这张照片…...

JVM运行时数据区-虚拟机栈

目录 一、内存中的栈 二、基本内容 三、优点 四、栈的存储单位 五、栈运行原理 六、栈的内部结构 &#xff08;一&#xff09;局部变量表 &#xff08;二&#xff09;操作数栈 &#xff08;三&#xff09;动态链接 &#xff08;四&#xff09;方法返回地址 &#xf…...

Java中介者模式

目录 定义 结构 案例 优点 缺点 使用场景 定义 又叫调停模式&#xff0c;定义一个中介角色来封装一系列对象之间的交互&#xff0c;使原有对象之间的耦合松散&#xff0c;且可以独立地改变它们之间的交互。 结构 中介者模式包含以下主要角色&#xff1a; 抽象中介者角…...

前端框架Vue学习 ——(五)前端工程化Vue-cli脚手架

文章目录 Vue-cliVue项目-创建Vue项目-目录结构Vue项目-启动Vue项目-配置端口Vue项目开发流程 Vue-cli 介绍&#xff1a;Vue-cli 是 Vue 官方提供的一个脚手架&#xff0c;用于快速生成一个 Vue 的项目模版 安装 NodeJS安装 Vue-cli npm install -g vue/cliVue项目-创建 图…...

App备案-iOS云管理式证书 Distribution Managed 公钥及证书SHA-1指纹的获取方法

根据近日工业和信息化部发布的《工业和信息化部关于开展移动互联网应用程序备案工作的通知》&#xff0c;相信不少要进行IOS平台App备案的朋友遇到了一个问题&#xff0c;就是apple不提供云管理式证书的下载&#xff0c;也就无法获取公钥及证书SHA-1指纹。 已经上架的应用不想重…...

Spring -Spring之依赖注入源码解析

依赖注入底层原理流程图&#xff1a;Spring中Bean的依赖注入原理| ProcessOn免费在线作图,在线流程图,在线思维导图 Spring中到底有几种依赖注入的方式&#xff1f; 首先分两种&#xff1a; 手动注入自动注入 手动注入 在XML中定义Bean时&#xff0c;就是手动注入&#xf…...

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&#xff1f; 三.MFC能做什么&#xff1f; 四.MFC开发环境搭建 五.MFC项目创建 六.消息映射机制 一.SDK编程 Application Programming Interface 应用程序编程接口。 Software Development Kit 软件开发工具包&#xff0c;一般会包括A…...

Android技术-修改SO导出符号

背景 经常在使用第三方SDK的时候会莫名其妙报错&#xff0c;其中最常见的一种就是SO符号冲突&#xff0c;比如libA.so静态链接了libC.a,而libB.so动态链接了libC.so。这样便会导致符号冲突。又或者在使用不同版本的动态库&#xff0c;也会造成符号冲突。 报错案例 案例1 DEB…...

flutter 打包apk

Flutter项目打包生成APK_flutter打包apk_文阿花的博客-CSDN博客 关于iconData可能出现的错误&#xff1a; flutter build apk 打包报错调试过程 - 掘金 (juejin.cn) 使用命令行&#xff1a;flutter build apk --no-tree-shake-icons...

使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式

一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明&#xff1a;假设每台服务器已…...

R语言AI模型部署方案:精准离线运行详解

R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...

JVM垃圾回收机制全解析

Java虚拟机&#xff08;JVM&#xff09;中的垃圾收集器&#xff08;Garbage Collector&#xff0c;简称GC&#xff09;是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象&#xff0c;从而释放内存空间&#xff0c;避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...

django filter 统计数量 按属性去重

在Django中&#xff0c;如果你想要根据某个属性对查询集进行去重并统计数量&#xff0c;你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求&#xff1a; 方法1&#xff1a;使用annotate()和Count 假设你有一个模型Item&#xff0c;并且你想…...

剑指offer20_链表中环的入口节点

链表中环的入口节点 给定一个链表&#xff0c;若其中包含环&#xff0c;则输出环的入口节点。 若其中不包含环&#xff0c;则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...

Java-41 深入浅出 Spring - 声明式事务的支持 事务配置 XML模式 XML+注解模式

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

从零实现STL哈希容器:unordered_map/unordered_set封装详解

本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说&#xff0c;直接开始吧&#xff01; 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...

微信小程序云开发平台MySQL的连接方式

注&#xff1a;微信小程序云开发平台指的是腾讯云开发 先给结论&#xff1a;微信小程序云开发平台的MySQL&#xff0c;无法通过获取数据库连接信息的方式进行连接&#xff0c;连接只能通过云开发的SDK连接&#xff0c;具体要参考官方文档&#xff1a; 为什么&#xff1f; 因为…...

DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”

目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...

【JVM面试篇】高频八股汇总——类加载和类加载器

目录 1. 讲一下类加载过程&#xff1f; 2. Java创建对象的过程&#xff1f; 3. 对象的生命周期&#xff1f; 4. 类加载器有哪些&#xff1f; 5. 双亲委派模型的作用&#xff08;好处&#xff09;&#xff1f; 6. 讲一下类的加载和双亲委派原则&#xff1f; 7. 双亲委派模…...