上篇说到 RMQ 问题可以用 ST 表算法处理，但需要在线修改的时候，线段树是更好的选择。 如图，很明显线段树是个二叉搜索树 ![在这里插入图片描述](https://img-blog.csdnimg.cn/20200401162921333.png?x-oss-process=image/wate

# 一、二叉搜索树 ## 1.二叉搜索树是什么 二叉搜索树（**BST**，Binary Search Tree),又称**二叉排序树或二叉查找树**，是一棵二叉树，可以为空，当不为空时满足以下性质： - 非空**左子树**的所有**键值小于其根结点**的键值 - 非空**右子树**的所有**

## ST 表是什么 ST 表是一个用来解决区间最值问题查询的算法 它用**O(nlogn)复杂度预处理，可以实现 O(1)复杂度的查询。** **缺点：无法支持在线修改** 模板题：[ST 表-洛谷](https://www.luogu.com.cn/problem/P3865) ### 1.

## 一、什么是树 ### 1.树的定义 树（Tree）：n（n≥0）个结点构成的有限集合。 当 n=0 时，称为**空树**； 对于任一棵**非空树**（n>0）,它具备以下性质： 1. 树中有一个称为“**根（Root）**”的特殊结点，**用 r 表示**。 2. 其余结点可分为 m

## 一、队列的抽象数据类型描述 类型名：队列（Queue） 数据对象集：一个有 0 个或多个元素的有穷线性表 操作集：长度为 MaxSize 的堆栈 Q∈Queue, 队列元素 item∈ElementType > **1.生成长度为 MaxSize 的空队列 > Queue CreatQue

## 一、堆栈的抽象数据类型描述 类型名：堆栈（Stack） 数据对象集：一个有 0 个或多个元素的有穷线性表 操作集：长度为 MaxSize 的堆栈 S∈Stack, 堆栈元素 item∈ElementType > **1.生成空堆栈，其最大长度为 MaxSize; > Stack Creat

## 一、广义表 - 是线性表的推广 - 对于线性表而言，n 个元素都是基本的单元素 - 广义表中，这些元素不仅可以使单元素也可以是另一个广义表 ```cpp > typedef struct GNode *GList; struct GNode { > int Tag; //标志

## 一、线性表的抽象数据类型描述 类型名：线性表（List） 数据对象集：线性表示 n(>=0)个元素构成的有序序列(a1,a2,……,an) 操作集：线性表 L∈List, 整数 i 表示位置,元素 X∈ElementType ## 二、顺序表 ### 1.定义 ```cpp struc