From 63cac75d59311c55ba86b8d531493364ae637517 Mon Sep 17 00:00:00 2001
From: FFjet <Leoleepaytser@hotmail.com>
Date: Sat, 13 Jul 2019 20:39:35 +0800
Subject: [PATCH] Update leftist-tree.md
MIME-Version: 1.0
Content-Type: text/plain; charset=utf8
Content-Transfer-Encoding: 8bit

修了一下格式
---
 docs/ds/leftist-tree.md | 34 +++++++++++++++++-----------------
 1 file changed, 17 insertions(+), 17 deletions(-)

diff --git a/docs/ds/leftist-tree.md b/docs/ds/leftist-tree.md
index 8917010a..8889ad5e 100644
--- a/docs/ds/leftist-tree.md
+++ b/docs/ds/leftist-tree.md
@@ -4,23 +4,23 @@
 
 ## dist 的定义和性质
 
-对于一棵二叉树，我们定义 **外节点** 为左儿子或右儿子为空的节点，定义一个外节点的 $dist​$ 为 $1​$，一个不是外节点的节点 $dist​$ 为其到子树中最近的外节点的距离加一。空节点的 $dist​$ 为 $0​$。
+对于一棵二叉树，我们定义 **外节点** 为左儿子或右儿子为空的节点，定义一个外节点的 $\mathrm{dist}$ 为 $1$，一个不是外节点的节点 $\mathrm{dist}$ 为其到子树中最近的外节点的距离加一。空节点的 $\mathrm{dist}$ 为 $0$。
 
-> 注：很多其它教程中定义的 $dist$ 都是本文中的 $dist$ 减去 $1$，本文这样定义是因为代码写起来方便。
+> 注：很多其它教程中定义的 $\mathrm{dist}$ 都是本文中的 $\mathrm{dist}$ 减去 $1$，本文这样定义是因为代码写起来方便。
 
-一棵有 $n$ 个节点的二叉树，根的 $dist$ 不超过 $\left\lceil\log (n+1)\right\rceil$，因为一棵根的 $dist$ 为 $x$ 的二叉树至少有 $x-1$ 层是满二叉树，那么就至少有 $2^x-1​$ 个节点。注意这个性质是所有二叉树都具有的，并不是左偏树所特有的。
+一棵有 $n$ 个节点的二叉树，根的 $\mathrm{dist}$ 不超过 $\left\lceil\log (n+1)\right\rceil$，因为一棵根的 $\mathrm{dist}$ 为 $x$ 的二叉树至少有 $x-1$ 层是满二叉树，那么就至少有 $2^x-1$ 个节点。注意这个性质是所有二叉树都具有的，并不是左偏树所特有的。
 
 ## 左偏树的定义和性质
 
-左偏树是一棵二叉树，它不仅具有堆的性质，并且是 “左偏” 的：每个节点左儿子的 $dist$ 都大于等于右儿子的 $dist$。
+左偏树是一棵二叉树，它不仅具有堆的性质，并且是「左偏」 的：每个节点左儿子的 $\mathrm{dist}$ 都大于等于右儿子的 $\mathrm{dist}$。
 
-因此，左偏树每个节点的 $dist​$ 都等于其右儿子的 $dist​$ 加一。
+因此，左偏树每个节点的 $\mathrm{dist}$ 都等于其右儿子的 $\mathrm{dist}$ 加一。
 
-需要注意的是，$dist​$ 不是深度，**左偏树的深度没有保证**，一条向左的链也是左偏树。
+需要注意的是，$\mathrm{dist}$ 不是深度，**左偏树的深度没有保证**，一条向左的链也是左偏树。
 
-## 左偏树的核心操作：合并（merge）
+## 核心操作：合并(merge)
 
-合并两个堆时，由于要满足堆性质，先取值较小（为了方便，本文讨论小根堆）的那个根作为合并后堆的根节点，然后将这个根的左儿子作为合并后堆的左儿子，递归地合并其右儿子与另一个堆，作为合并后的堆的右儿子。为了满足左偏性质，合并后若左儿子的 $dist$ 小于右儿子的 $dist​$，就交换两个儿子。
+合并两个堆时，由于要满足堆性质，先取值较小（为了方便，本文讨论小根堆）的那个根作为合并后堆的根节点，然后将这个根的左儿子作为合并后堆的左儿子，递归地合并其右儿子与另一个堆，作为合并后的堆的右儿子。为了满足左偏性质，合并后若左儿子的 $\mathrm{dist}$ 小于右儿子的 $\mathrm{dist}$，就交换两个儿子。
 
 参考代码：
 
@@ -36,9 +36,9 @@ int merge(int x, int y)
 }
 ```
 
-由于左偏性质，每递归一层，其中一个堆根节点的 $dist$ 就会减小 $1$，而 “一棵有 $n$ 个节点的二叉树，根的 $dist$ 不超过 $\left\lceil\log (n+1)\right\rceil$”，所以合并两个大小分别为 ​$n$ 和 ​$m$ 的堆复杂度是 ​$\mathcal O(\log n+\log m)$。
+由于左偏性质，每递归一层，其中一个堆根节点的 $\mathrm{dist}$ 就会减小 $1$，而 “一棵有 $n$ 个节点的二叉树，根的 $\mathrm{dist}$ 不超过 $\left\lceil\log (n+1)\right\rceil$”，所以合并两个大小分别为 $n$ 和 $m$ 的堆复杂度是 $\mathcal O(\log n+\log m)$。
 
-左偏树还有一种无需交换左右儿子的写法：将 $dist​$ 较大的儿子视作左儿子，$dist​$ 较小的儿子视作右儿子：
+左偏树还有一种无需交换左右儿子的写法：将 $\mathrm{dist}$ 较大的儿子视作左儿子，$\mathrm{dist}$ 较小的儿子视作右儿子：
 
 ```cpp
 int& rs(int x)
@@ -70,7 +70,7 @@ int merge(int x, int y)
 
 #### 做法
 
-先将左右儿子合并，然后自底向上更新 $dist​$、不满足左偏性质时交换左右儿子，当 $dist​$ 无需更新时结束递归：
+先将左右儿子合并，然后自底向上更新 $\mathrm{dist}$、不满足左偏性质时交换左右儿子，当 $\mathrm{dist}$ 无需更新时结束递归：
 
 ```cpp
 int& rs(int x)
@@ -100,14 +100,14 @@ void pushup(int x)
 
 #### 复杂度证明
 
-我们令当前 `pushup` 的这个节点为 $x​$，其父亲为 $y​$，一个节点的 “初始 $dist​$” 为它在 `pushup` 前的 $dist​$。我们先 `pushup` 一下删除的节点，然后从其父亲开始起讨论复杂度。
+我们令当前 `pushup` 的这个节点为 $x$，其父亲为 $y$，一个节点的 “初始 $\mathrm{dist}$” 为它在 `pushup` 前的 $\mathrm{dist}$。我们先 `pushup` 一下删除的节点，然后从其父亲开始起讨论复杂度。
 
 继续递归下去有两种情况：
 
-1. $x$ 是 $y$ 的右儿子，此时 $y$ 的初始 $dist$ 为 $x$ 的初始 $dist$ 加一。
-2. $x$ 是 $y$ 的左儿子，只有 $y$ 的左右儿子初始 $dist$ 相等时（此时左儿子 $dist$ 减一会导致左右儿子互换）才会继续递归下去，因此 $y$ 的初始 $dist$ 仍然是 $x$ 的初始 $dist$ 加一。
+1. $x$ 是 $y$ 的右儿子，此时 $y$ 的初始 $\mathrm{dist}$ 为 $x$ 的初始 $\mathrm{dist}$ 加一。
+2. $x$ 是 $y$ 的左儿子，只有 $y$ 的左右儿子初始 $\mathrm{dist}$ 相等时（此时左儿子 $\mathrm{dist}$ 减一会导致左右儿子互换）才会继续递归下去，因此 $y$ 的初始 $\mathrm{dist}$ 仍然是 $x$ 的初始 $\mathrm{dist}$ 加一。
 
-所以，我们得到，除了第一次 `pushup`（因为被删除节点的父亲的初始 $dist​$ 不一定等于被删除节点左右儿子合并后的初始 $dist​$ 加一），每递归一层 $x​$ 的初始 $dist​$ 就会加一，因此最多递归 $\mathcal O(\log n)​$ 层。
+所以，我们得到，除了第一次 `pushup`（因为被删除节点的父亲的初始 $\mathrm{dist}$ 不一定等于被删除节点左右儿子合并后的初始 $\mathrm{dist}$ 加一），每递归一层 $x$ 的初始 $\mathrm{$\mathrm{dist}$}$ 就会加一，因此最多递归 $\mathcal O(\log n)$ 层。
 
 ### 整个堆加上 / 减去一个值、乘上一个正数
 
@@ -148,7 +148,7 @@ int pop(int x)
 
 1. 合并前要检查是否已经在同一堆中。
 
-2. 左偏树的深度可能达到 $\mathcal O(n)​$，因此找一个点所在的堆顶要用并查集维护，不能直接暴力跳父亲。（虽然很多题数据水，暴力跳父亲可以过..）（用并查集维护根时要保证原根指向新根，新根指向自己。）
+2. 左偏树的深度可能达到 $\mathcal O(n)$，因此找一个点所在的堆顶要用并查集维护，不能直接暴力跳父亲。（虽然很多题数据水，暴力跳父亲可以过..）（用并查集维护根时要保证原根指向新根，新根指向自己。）
 
 ??? " 罗马游戏参考代码 "
 
@@ -410,7 +410,7 @@ int pop(int x)
 
 再考虑单点查询，若用普通的方法打标记，就得查询点到根路径上的标记之和，最坏情况下可以达到 $\mathcal O(n)$ 的复杂度。如果只有堆顶有标记，就可以快速地查询了，但如何做到呢？
 
-可以用类似启发式合并的方式，每次合并的时候把较小的那个堆标记暴力下传到每个节点，然后把较大的堆的标记作为合并后的堆的标记。由于合并后有另一个堆的标记，所以较小的堆下传标记时要下传其标记减去另一个堆的标记。由于每个节点每被合并一次所在堆的大小至少乘二，所以每个节点最多被下放 $\mathcal O(\log n)​$ 次标记，暴力下放标记的总复杂度就是 $\mathcal O(n\log n)​$。
+可以用类似启发式合并的方式，每次合并的时候把较小的那个堆标记暴力下传到每个节点，然后把较大的堆的标记作为合并后的堆的标记。由于合并后有另一个堆的标记，所以较小的堆下传标记时要下传其标记减去另一个堆的标记。由于每个节点每被合并一次所在堆的大小至少乘二，所以每个节点最多被下放 $\mathcal O(\log n)$ 次标记，暴力下放标记的总复杂度就是 $\mathcal O(n\log n)$。
 
 再考虑单点加，先删除，再更新，最后插入即可。
 
-- 
2.11.0