From ccab5cae4d33c40d7bc684cd0018412a8f27bb8c Mon Sep 17 00:00:00 2001
From: =?utf8?q?=E9=9B=B7=E8=92=BB?=
 <34390285+hsfzLZH1@users.noreply.github.com>
Date: Sat, 19 Jan 2019 12:06:33 +0800
Subject: [PATCH] Update treap.md
MIME-Version: 1.0
Content-Type: text/plain; charset=utf8
Content-Transfer-Encoding: 8bit

添加了非旋式 treap 建树的操作
---
 docs/ds/treap.md | 30 ++++++++++++++++++++++++++++++
 1 file changed, 30 insertions(+)

diff --git a/docs/ds/treap.md b/docs/ds/treap.md
index ea46bb4e..19d4dc6a 100644
--- a/docs/ds/treap.md
+++ b/docs/ds/treap.md
@@ -49,6 +49,36 @@ node *merge(node *u, node *v) {
 }
 ```
 
+### 建树（build）
+
+将一个有 $n$ 个节点的序列 $a_i$ 转化为一棵 treap 。
+
+定义 ```Merge(x,y)``` 表示将根为 $x$ 和 $y$ 的两棵 Treap 合并成一棵，其根为该函数的返回值。需要保证 $x<y$ 。
+
+定义 ```Split(o,k,x,y)``` 表示将根为 $o$ 的 Treap 分裂成 $x,y$ 两个部分，保证 $x < y$ ，即将该 Treap 分裂成权值小于等于 $k$ 的项和其他，分别为 $x$ 和 $y$ 。
+
+可以依次暴力插入这 $n$ 个节点，每次插入一个权值为 $v$ 的节点时，将整棵 treap 按照权值分裂成权值小于等于 $v$ 的和权值大于 $v$ 的两部分，然后新建一个权值为 $v$ 的节点，将两部分和新节点按从小到大的顺序依次合并，时间复杂度 $O(n\log_2 n)$ ，单点插入时间复杂度 $O(\log_2 n)$ 。
+
+```cpp
+void build(int n,int a[])
+{
+	int x,y;
+	for(int i=1;i<=n;i++)
+	{
+		split(rt,a[i],x,y);
+		rt=merge(merge(x,newnode(a[i])),y);
+	}
+}
+```
+
+在某些题目内，可能会有多次插入一段序列的操作，这是就需要在 $O(n)$ 的时间复杂度内完成建树操作。（假设这些节点已经有序）
+
+方法一：直接将这 $n$ 个节点构造成一棵类线段树，即每次选取最中间的节点作为一段区间的树根，这样能保证树高为 $O(\log_2 n)$ 。然后对每个节点钦定优先值，保证其满足堆的性质。
+
+方法二：直接将这 $n$ 个节点构造成一棵类线段树，即每次选取最中间的节点作为一段区间的树根，这样能保证树高为 $O(\log_2 n)$ 。然后给每个节点一个随机优先级，不保证其满足堆的性质。因为非旋式 treap 的优先级不是维护堆的性质，保证树高的，而是使 ```merge``` 操作更加随机一点，所以也是正确的。
+
+方法三：观察到 treap 是一个笛卡尔树，利用笛卡尔树的 $O(n)$ 建树方法即可，用单调栈维护右脊柱即可。
+
 ## 将 treap 包装成为 `set<int>` 
 
 ### count 函数
-- 
2.11.0