- 博客(191)
- 收藏
- 关注
RSS订阅原创 二叉搜索树 & 平衡树
二叉搜索树是一种二叉树的树形数据结构，其定义如下：空树是二叉搜索树。若二叉搜索树的左子树不为空，则其左子树上所有点的附加权值均小于其根节点的值。若二叉搜索树的右子树不为空，则其右子树上所有点的附加权值均大于其根节点的值。二叉搜索树的左右子树均为二叉搜索树。二叉搜索树上的基本操作所花费的时间与这棵树的高度成正比。对于一个有个结点的二叉搜索树中，这些操作的最优时间复杂度为，最坏为。随机构造这样一棵二叉搜索树的期望高度为。实现1234567891011int key;
2025-05-04 17:44:54
653
原创 划分树——详解
对于每一个划分树中的节点，我们称他为右节点当且仅当他在下一层会被划分到右孩子，即原数组中位置比较靠后的那些数，相似的可以定义左节点。如果在建树的过程中将最顶层排为有序的，类似于归并排序求逆序对，可以发现一个数组的逆序对个数就是在每个左节点之前的右节点的个树和。删除一个左节点会将整个数组的逆序对减少在他之前右结点的个数，而删除一个右节点会减少在他之后的左节点个数。需要注意的是，按这一方法实现的树状数组会访问到的最大下标是距离 n 最近的 2 的整次幂，因此数组下标不能开 n。而向下跳则是完全不同的处理方式。
2025-05-04 17:25:33
740
原创 猫树——详解
众所周知线段树可以支持高速查询某一段区间的信息和，比如区间最大子段和，区间和，区间矩阵的连乘积等等。次合并操作，询问区间和这种东西的时候还可以忍受，但是当我们需要询问区间线性基这种合并复杂度高达。此时我们发现线段树上两个节点的 LCA 编号，就是两个节点二进制编号的最长公共前缀 LCP。具体来讲我们建树的时候对于线段树树上的一个节点，设它代表的区间为。这段区间的节点在线段树上的 LCA 求出来，设这个节点。在处理线性基这样特殊的信息的时候甚至可以将复杂度降至。这段区间的信息和的时候，将线段树树上代表。
2025-05-03 23:23:39
654
原创 线段树基础
每次执行修改时，我们通过打标记的方法表明该节点对应的区间在某一次操作中被更改，但不更新该节点的子节点的信息。实质性的修改则在下一次访问带有标记的节点时才进行。在建图连边的过程中，我们有时会碰到这种题目，一个点向一段连续的区间中的点连边或者一个连续的区间向一个点连边，如果我们真的一条一条连过去，那一旦点的数量多了复杂度就爆炸了，这里就需要用线段树的区间性质来优化我们的建图了。不过不用担心，虽然修改目前还没进行，但当我们要查询这两个子节点的信息时，我们会利用标记修改这两个子节点的信息，使查询的结果依旧准确。
2025-05-03 22:43:11
817
原创 ST 表——详解
ST 表（Sparse Table，稀疏表）是用于解决可重复贡献问题的数据结构。什么是可重复贡献问题？可重复贡献问题是指对于运算，满足，则对应的区间询问就是一个可重复贡献问题。例如，最大值有，gcd 有，所以 RMQ 和区间 GCD 就是一个可重复贡献问题。像区间和就不具有这个性质，如果求区间和的时候采用的预处理区间重叠了，则会导致重叠部分被计算两次，这是我们所不愿意看到的。另外，还必须满足结合律才能使用 ST 表求解。什么是 RMQ？
2025-03-29 19:23:45
284
原创 单调队列——详解
顾名思义，单调队列的重点分为「单调」和「队列」。「单调」指的是元素的「规律」——递增（或递减）。「队列」指的是元素只能从队头和队尾进行操作。Ps. 单调队列中的 "队列" 与正常的队列有一定的区别，稍后会提到。
2025-03-29 19:18:22
874
原创 栈——详解
栈的修改与访问是按照后进先出的原则进行的，因此栈通常被称为是后进先出（last in first out）表，简称 LIFO 表。栈是 OI 中常用的一种线性数据结构。请注意，本文主要讲的是栈这种数据结构，而非程序运行时的系统栈/栈空间。为用于存储元素的底层容器类型。还提供了一些运算符。较为常用的是使用赋值运算符。C++ 中的 STL 也提供了一个容器。如果不指定，则默认使用。为 stack 中要存储的数据类型。
2025-02-16 21:25:49
419
原创 线性规划简介
研究线性约束条件下线性目标函数极值问题的方法总称，是运筹学的一个分支，在多方面均有应用。线性规划的某些特殊情况，如网络流、多商品流量等问题都有可能在 OI 题目中出现。
2025-02-12 08:17:07
541
原创 Jordan标准型
观察三种初等变换，由于唯一被改写的倍加变换不改变行列式，事实上三种初等变换仅对行列式的结果多项式改变常数倍，因此不改变行列式的结果多项式的因式分解与次数。在一个矩阵对应的 Jordan 标准型里面，主对角线上的元素构成的对角阵是这个矩阵对应的 Jordan 标准型的可对角化部分，把主对角线上的元素换成。相似于它的 Jordan 标准型，因此两者的特征矩阵也等价，将 Jordan 标准型的特征矩阵化为 Smith 标准型即可看出。，行列式就是主对角线全体不变因子的乘积，也等于全体初等因子的乘积。
2025-02-05 22:41:11
917
原创 对角化——详解
也就是说，特征子空间的维数是几何重数，「特征子空间」经过最小多项式 次幂后到达一个「不变子空间」，不变子空间的维数到达了特征多项式的代数重数。只考虑 在不变子空间 上的作用，就得到子空间 本身的线性变换，称为 在子空间 上的限制，记作。矩阵 的属于 的全部特征向量，再添上零向量，构成一个线性空间，称为矩阵 的一个特征子空间，记为。显然，一个 循环子空间 在 作用下不变，并且对于循环子空间 中的任意向量 ，均有 ，这里 为循环子空间的维数。设 是空间 的一个线性变换。
2025-02-05 19:39:22
821
原创 特征多项式
对于 的矩阵 和 ，当存在 的可逆矩阵 满足则矩阵 和 相似，记变换 为相似变换。且 和 有相同的特征多项式。考虑得证，对于 也是一样的。另外 ，因为 故。定理：相似矩阵有相同的特征多项式及特征值，反之不然。定理表明，线性变换的矩阵的特征多项式与基的选取无关，而直接由线性变换决定，故可称之为线性变换的特征多项式。矩阵 的特征多项式 是一个首一的多项式。根据韦达定理，它的 次系数为：其中 称为 的迹，为 的主对角线元素之和。
2025-02-05 19:38:16
978
原创 线性基——详解
称线性空间的一个极大线性无关组为的一组Hamel 基或线性基，简称基。规定线性空间的基为空集。可以证明任意线性空间均存在线性基1，我们定义线性空间的维数为线性基的元素个数（或势），记作。
2025-02-05 19:36:51
911
原创 线性空间——详解
线性空间（向量空间）是线性代数的基本概念与重要研究对象。线性空间是由向量集合、域、加法运算和标量乘法（数乘）组成的模类代数结构。具体来说，设是一个阿贝尔群，是一个域。定义中的数与中元素的一种代数运算，称为数乘，记为或，其中在域中，在阿贝尔群中。要求该数乘运算是封闭的，运算结果始终有意义，也在群中。数乘对向量加法分配律：对于数乘对标量加法分配律：对于数乘结合律（一致于域乘法）：对于标量乘法单位元：令是的乘法单位元，则对于则称代数系统是关于构成上的一个。
2025-02-02 19:06:05
924
原创 行列式——详解
置换逆序数。手动计算较低阶的行列式可以采用这种方法，它的时间复杂度为阶乘量级。使用记号 表示排列 的逆序数， 为全体长度为 的排列构成的集合。记号：表示的 阶行列式是指 项的代数和，这些项是一切可能的取自方阵 中不同的行与不同的列上的 个元素的乘积。项 前面的符号是 ，也就是说，当 是偶排列时，符号为正，当 是奇排列时，符号为负。对于二三阶行列式的对角线法则，事实上就是采用了全排列定义。四阶以上行列式不再适用于对角线法则，也是同样的原因。特别地，一阶行列式就是元素本身。
2025-02-02 19:02:08
959
原创 初等变换——详解
由于有定理，在恒等变换视为零个对换的乘积的情形下，任何置换都可以拆为对换的乘积，因此任何置换矩阵也可以拆分为对换矩阵的乘积。由于方阵乘积的行列式等于方阵行列式的乘积，初等矩阵的行列式便于计算，以及初等变换等价于初等矩阵的乘法，在行列式计算中也会使用初等变换。左乘一个置换矩阵等价于对原矩阵的行进行置换，右乘一个置换矩阵等价于对原矩阵的列进行置换，相应置换的方法和对于单位阵。由于方阵乘法的行列式等于行列式的乘法，借助下文初等变换与矩阵乘法的等价性，初等矩阵的这个性质可以用于行列式的计算。
2025-02-02 18:57:27
966
原创 内积和外积
内积有不同但等价的定义方法，下面介绍其中一些。在 维欧氏空间 下，已知两个向量 ，它们的夹角为 ，那么：就是这两个向量的内积，也叫点积或数量积。其中称 为 在 方向上的投影。内积的几何意义即为：内积 等于 的模与 在 方向上的投影的乘积。在 维欧氏空间 下，已知两个向量 ，那么：就是这两个向量的内积，也叫点积或数量积。内积的几何定义与代数定义在欧氏空间下是等价的，而后者更方便使用。在不引起混淆的情况下，内积的点号可以省略不写。
2025-02-02 11:49:02
770
原创 向量——详解
向量：既有大小又有方向的量称为向量。数学上研究的向量为自由向量，即只要不改变它的大小和方向，起点和终点可以任意平行移动的向量。记作 或。有向线段：带有方向的线段称为有向线段。起点，方向，长度，知道了三要素，终点就唯一确定。一般使用有向线段表示向量。向量的模：有向线段 的长度称为向量的模，即为这个向量的大小。记为： 或。零向量：模为 的向量。零向量的方向任意。记为： 或。单位向量：模为 的向量称为该方向上的单位向量。一般记为 或。平行向量：方向相同或相反的两个非零向量。记作：。
2025-02-02 11:46:52
841
原创 线性代数简介
线性代数把这些性质从具体对象中抽象出来，作为一个独立的学科来研究。在 OI 中，线性代数的知识可以直接用来解决问题，也可以用于优化算法、数据结构等。早在几千年前，就有古人应用线性方程组解决问题，而如今，线性代数仍然应用广泛。线性代数源于人们的观察。利用矩阵树定理把图的生成树计数问题转化为求矩阵的行列式。用树剖维护线性基求链上最大异或和。对于任意的 ， 可以分解成。这些性质与所描述对象的。力可以被分解、合成。用矩阵快速幂优化递推。
2025-02-02 09:29:59
186
原创 图论计数——详解
在组合数学中，图论计数（Graph Enumeration）是研究满足特定性质的图的计数问题的分支。与和是解决这类问题时最重要的数学工具。图论计数可分为有标号和无标号两大类问题，大多数情况下有标号版本的问题都比其对应的无标号问题更加简单，因此我们将先考察有标号问题的计数。
2025-02-02 09:29:16
1010
原创 Pólya 计数
故而，所有本质不同的染色的数目，就等价于不同轨道的数目。给某个结构选择一种染色方案，用数学语言表示，就是选择一个从这个结构的可以染色的对象（比如项链中的珠子、立方体的面等）的集合 到颜色集合 的映射。比如说，正方体的空间对称群对于它的顶点、棱、面的作用就分别对应着正方体的顶点置换群、棱置换群和面置换群，顶点、棱、面的个数互不相同，故而这些置换群以及对应的轮换指标当然也各不相同。对于正方体的各种对称操作，它的不动点集合的大小都是 的形式，这里 是颜色的数目， 是在操作 下可以独立染色的区域数目。
2025-02-01 23:34:35
681
原创 范德蒙德卷积
在一个大小为 的集合中取出 个数，可以等于把大小为 的集合拆成两个集合，大小分别为 与 ，然后从 中取出 个数，从 中取出 个数的方案数。由于我们有了对于 的枚举，于是只需要考虑一种拆法，因为不同的拆法之间是等价的。换个视角，我们将 步拆成两部分走，先走 步，再走 步，那么 步中若有 步向右，则 步中就有 步向右，故得证。规定 位于网格图左上角，其中向下走了 步，向右走了 步，方案数为。范德蒙德卷积是一种合并组合数的式子，主要应用于组合数学的公式推导。
2025-02-01 18:44:41
281
原创 Entringer Number
这里再给出一种配对的方法：将 zigzag 置换分为交替置换（alternating permutation）和反交替置换（reverse alternating permutation）。因此，交替置换与反交替置换的个数相等，恰好为 zigzag 置换的一半。，每个 zigzag 置换翻转过来仍旧为 zigzag 置换，可以两两配对，所以必然为偶数。正切函数是奇函数，正割函数是偶函数，两者之和构成 zigzag 数的生成函数。按照这种方式排列的恩特林格数的优势是，与它的递推关系。
2025-02-01 16:49:33
1012
原创 贝尔数——详解
贝尔数以埃里克·坦普尔·贝尔命名，是组合数学中的一组整数数列，开首是（）：是基数为的集合的划分方法的数目。集合的一个划分是定义为的两两不相交的非空子集的族，它们的并是。例如因为 3 个元素的集合有 5 种不同的划分方法：是 1 因为空集正好有 1 种划分方法。
2025-02-01 16:37:29
513
原创 卡特兰数——详解
对于这里面任意一条接触了 的路径，可以把它最后离开这条线的点到 之间的部分关于 对称变换，就得到从 到 的一条非降路径。从而 下方的非降路径数是。但注意到它的分母不是斐波那契数列那样的多项式形式，因此不方便套用等比数列的展开形式。，我们得到的是 的常数项，也就是。而另一个解会出现分母为 的情况（不收敛），舍弃。的非降路径数等于 个 和 个 的排列数，即。到 ，可以看做是 到 不接触 的非降路径数。这样我们就得到了卡特兰数的通项公式。非降路径是指只能向上或向右走的路径。
2025-02-01 16:18:36
976
原创 错位排列——详解
错位排列（derangement）是没有任何元素出现在其有序位置的排列。即，对于的排列，如果满足，则称是的错位排列。例如，三元错位排列有和。四元错位排列有和。错位排列是没有不动点的排列，即没有长度为 1 的循环。
2025-02-01 16:13:47
938
原创 斐波那契数列
波那契数列（The Fibonacci sequence，OEIS A000045）的定义如下：该数列的前几项如下：卢卡斯数列（The Lucas sequence，OEIS A000032）的定义如下：该数列的前几项如下：研究斐波那契数列，很多时候需要借助卢卡斯数列为工具。第 个斐波那契数可以在 的时间内使用递推公式计算。但我们仍有更快速的方法计算。解析解即公式解。我们有斐波那契数列的通项公式（Binet's Formula）：这个公式可以很容易地用归纳法证明，当然也可以通过生成函数的概念推导，或者解
2025-02-01 16:05:57
1085
原创 排列组合——详解
组合则是指从给定个数的元素中仅仅取出指定个数的元素，不考虑排序。排列组合的中心问题是研究给定要求的排列和组合可能出现的情况总数。插板法（Stars and bars）是用于求一类给相同元素分组的方案数的一种技巧，也可以用于求一类线性不定方程的解的组数。因为元素是相同的，所以转化过的情况和转化前的情况可以一一对应，答案也就是相等的。显然此时没法直接插板了，因为有可能出现很多块板子插到一个空里面的情况，非常不好计算。考虑其中已经排好的一圈，从不同位置断开，又变成不同的队列。的集合（转化为上面插板法的问题三）。
2025-01-29 21:39:37
1523
原创 狄利克雷生成函数
对于两个数论函数 和 ，则它们的狄利克雷卷积得到的结果 定义为：上式可以简记为：狄利克雷卷积是数论函数的重要运算，数论函数的许多性质都是通过这个运算挖掘出来的。狄利克雷卷积与狄利克雷生成函数（DGF）密切相关。
2025-01-29 21:37:34
903
原创 普通生成函数
序列 的普通生成函数（ordinary generating function，OGF）定义为形式幂级数：既可以是有穷序列，也可以是无穷序列。换句话说，如果序列 有通项公式，那么它的普通生成函数的系数就是通项公式。
2025-01-29 21:32:02
917
原创 形式幂级数复合|复合逆
形式幂级数的复合和复合逆也是常见的形式幂级数操作，对于没有特殊性质的之前我们一直使用的多是的算法来计算其中，但是因为效率较低应用较少。我们介绍 Kinoshita–Li 的的算法，其中为两个次数为的多项式相乘的时间。
2025-01-29 21:30:16
987
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人