第 13 页

二叉搜索树的插入、查找、删除等操作的效率与树高成正比，因此在创建二叉搜索树时要尽可能地通过调平衡压缩树高。平衡树有很多种，例如AVL树、Treap、伸展树（Splay）、SBT、红黑树等。Treap简介特点与作用Treap，即Tree+Heap，又叫做树堆，它同时满足了二叉搜索树和堆两种性质。二叉搜索树满足中序有序性，输入的序列不同，创建的二叉搜索树也不同，在最坏的情况下（比如只有左子树或者只有右子树），会退化为线性。若一个二叉搜索树插入的节点顺序时随机的，则得到的二叉搜索树在大多情况下是平衡的，即使存在一些极端的情况但这种情况发生的概率很小，因此以随机…

[card title="主席树" color="info"]主席树，又叫可持久化权值线段树，也叫函数式线段树，是可持久化线段树的子集。在本文中，我们可以认为主席树等于可持久化线段树[/card]可持久化线段树简介基本结构、特点、作用在这篇文章中已经提到过：线段树扩展：权值线段树总的来说就是每次修改或插入一个值，就新建一个根节点，并且向下递归去新建其他节点。优点解释每次插入操作最多创建的节点数都为$\log n$（从根到叶子），一共执行了$n$次插入操作，可持久化线段树的节点总数为$n \log n$，而$n$棵单独的线段树的总节点数是$n^2$，很明显…

二叉堆简介二叉堆是一种基础数据结构，对于其他数据结构来说，支持的操作有限，也就插入，查询，删除这一类。二叉堆的结构从二叉堆的结构说起，它是一棵二叉树，并且是完全二叉树，每个结点中存在一个权值。堆性质：父亲的权值不小于儿子的权值（大根堆）。同样的，我们可以定义小根堆。本文以大根堆为例。由堆性质，树根存的是最大值。对于堆的每个子树，它同样也是一个堆。考虑使用一个序列h来表示堆，$h_i$的两个儿子分别是$h_{2i}$和$h_{2i+1}$，$1$是根节点：来自于：OI Wiki具体每个节点的对应关系如上图。二叉堆的基本操作插入操作插入操作是指向二叉堆中插入…

一、定义代数系统$\langle G: \circ \rangle$称为群，如果：运算封闭性。运算$\circ$满足结合律，即$\forall a,b,c\in G,a\circ(b\circ c)=(a\circ b)\circ c$$G$关于运算$\circ$存在单位元，即$\exists e\in G$，使 $\forall a\in G$，有 $a\circ e=e\circ a=a$$G$中每个元素关于$\circ$都可逆，即$\forall a\in G,\exists b\in G$使得$a\circ b=$ $b\circ a=e$（单位…

一、增广矩阵对于一个由$m\times n$个数排成$m$个横行，$n$个竖列的矩形数表称为$m\times n$矩阵。对于一个$m\times n$的矩阵$A$，我们可以在它的右边加上一个$m\times1$的列向量$\boldsymbol b$，得到一个$m\times(n+1)$的矩阵$(A,\boldsymbol b)$，这个矩阵被称为$A$的增广矩阵。$$A=\begin{pmatrix}a_{11}&a_{12}&\cdots&a_{1n}\\a_{21}&a_{22}&\cdots&a_{2n…

一、$n$元向量在研究问题过程中，有些研究对象可以用多个数组组成的有序数组来描述，例如在$n$元一次方程$a_1x_1+a_2x_2+\cdots+a_nx_n=b$中，可以用其系数和常数$b$排成有序$(n+1)$元数组$(a_1,a_2,\cdots,a_n,b)$来表示；在按照升幂排列成的一元$n$次多项式$P(x)=a_0+a_1x+a_2x^2+a_2x^3+\cdots+a_nx^n$中，可以用其系数组成的$(n+1)$元有序数组$(a_1,a_2,\cdots,a_n)$来表示。由$n$个数$a_1,a_2,\cdots,a_n$组成的有序…

一、多元线性方程组的求解与解的性质线性方程组存在三种解的情况：无解无数解唯一解判断法则：秩。判断无穷多解的情况，需要找到无穷多解的“本质”，本质便是找到个数唯一确定的有限多个解。二、二次曲线、二次曲面与二次超曲面我们在中学中学习过二次曲线包括抛物线（$y^2=2px$），椭圆（圆）（$\frac{x^2}{a^2}+\frac{y^2}{b^2}=1$），双曲线（$\frac{x^2}{a^2}-\frac{y^2}{b^2}=1$），两条直线。二次曲线的一般形式为（$Ax^2+Bxy+Cy^2+2Dx+2Ey+F=0$，其中大写字母为实数常数）。然后我…

一、均值不等式对于$n$个正数$a_1,a_2,\cdots,a_n$，有：$A_n= \frac {a_1+ a_2+ \cdots + a_n}n$ 称为算术平均值；$G_n=\sqrt[n]{a_1a_2\cdots a_n}$称为几何平均值；$H_n= \frac n{\frac 1{a_1}+ \frac 1{a_2}+ \cdots + \frac 1{a_n}}$称为调和平均值。均值不等式即为：$$H_{n}\leq G_{n}\leq A_{n}$$当且仅当 $a_1=a_2=\cdots=a_n$时，等号成立。特别地，当$n=2$时，对…

一、平移坐标轴所致的坐标变换公式设$O$是平面上的一个点，以它为原点，如图构建直角坐标系$xOy$。设$O'$是平面上的一点，其坐标是$O^{\prime}(x_0,y_0)$.平移直角坐标系$xOy$使得新的原点为$O'$.记平移后的坐标系的两个数轴分别为$x'$和$y'$、坐标系为$x'O'y'$对于平面上的任意一点$P$，如果它在$xOy$和$x'Oy'$中的坐标分别是$(x,y)$和$( x^\prime , y^\prime )$，由于在坐标系$xOy$中…

一、一元多项式函数的形式设$a_0, a_1, \cdots , a_n\in \mathbb{P} , a_n\neq 0$，我们称下述定义取值均在数域$\mathbb{P}$中的函数$$f(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots+a_1x+a_0=\sum_{i=0}^na_ix^i,\forall x\in\mathbb{P}$$为数域$\mathbb{P}$上的一个一元多项式函数。称$n$为$f(x)$的次数、$a_ix^i$为$f(x)$的第$i$次项、$a_i$为该项的系数$(i=0,1,2,\cdots,n)$.称$…

一、引言在平面直角坐标系中,我们用$(x,y)$来表示平面上的一点,其中$x,y$分别是此点在两个坐标轴上的投影坐标。但在有的情况，直角坐标表示不是最高使的例如在海平面上报告某船只的位置，确定船只的距离与方位要比根告船只在某直角坐标系中的坐标要更直接更方便确定船只的位置，以下个绍的极坐标系就是用“距离”和“方位”来表示（确定）平面上一点的坐标系，同样，用极坐标方程或参数方程来表示平面曲线有时也比直角坐标方程表方便许多。二、极坐标系1、定义在平面上取定一点$O$，称为极点，从$O$出发引一条射线$Ox$，称为极轴，对平面上任一点P，记$P$到$O$的距离为…

一、反三角函数定义1、反正弦函数由于正弦函数的单调区间为$[ - \frac \pi 2+ 2k\pi , \frac \pi 2+ 2k\pi ]$ 和 $[ \frac \pi 2+ 2k\pi , \frac {3\pi }2+ 2k\pi ],k\in \mathbb{Z}$在每个单调区间上正弦函数都有反函数。例如在以下区间中，存在：$y=\sin x,x\in[-\frac\pi2,\frac\pi2]$对于任意的 $y\in[-1,1]$，都存在唯一的$x\in [ - \frac \pi 2, \frac \pi 2] $，使得 $\sin…

一、函数的概念设$X\subset\mathbb{R}$为实数集。如果对于任一元素$x\in X$ ,都存在唯一的$y\in\mathbb{R}$按照对应法则$f$与之对应，则称$f:X\to\mathbb{R}$为一元实值函数，或一元函数、函数，记为$y=f(x)$.函数$f$的定义域：$D(f)=X$函数$f$的值域：$R(f)=f(X)$函数$f$的图像：$G(f)=\{(x,y)|y=f(x),x\in X\}$二、函数的构成/生成四则运算：$f\pm g$、$fg$、$\frac fg$复合运算：$g\circ f:=g(f(x))$反函数运算…

一、数域的概念设$\mathbb{P}$ 是一个至少含有两个不同数的数集，若数集 $\mathbb{P}$关于数的四则运算都封闭，则我们称数集$\mathbb{P}$是一个数域。比如：整数集 $\mathbb{Z}$ 不是数域，非负整数所成的集合不是数域，有限集${1,2,3,4,5}$不是数域。有理数集$\mathbb{Q}$、实数集$\mathbb{R}$和复数集$\mathbb{C}$是数域（有理数域、实数域和复数域）$\mathbb{Q}\subset\mathbb{R}\subset\mathbb{C}$.二、数域的简单性质存在异于有理数集$\…

一、复数的定义及各种表达形式1、代数定义如果量$z$能写成如下形式：$$z=a+b \mathrm{i} ,a,b\in R,$$则称$z$ 是一个复数。这里$\mathrm{i}$是一个符号，称作虚数单位。实数$a,b$分别称作复数$z$的实数部分（或简称实部）和虚数部分（或简称虚部），记为：$$\mathrm{Re}\left(z\right)=a,\mathrm{Im}\left(z\right)=b$$复数的全体所组成的集合记为$$\mathbb{C}=\left\{a+bi\mid a,b\in R\right\}.$$实数是虚部为零的复数。当…