From 92ac8496e1598fdca6d2d7bbee657ac4822da3aa Mon Sep 17 00:00:00 2001
From: Siej <42795424+Siej@users.noreply.github.com>
Date: Wed, 29 Aug 2018 15:02:14 +0800
Subject: [PATCH] Update scapegoat.md

---
 docs/ds/scapegoat.md | 46 ++++++++++++++++++++++++++++------------------
 1 file changed, 28 insertions(+), 18 deletions(-)

diff --git a/docs/ds/scapegoat.md b/docs/ds/scapegoat.md
index a6ae3a75..1738e7e6 100644
--- a/docs/ds/scapegoat.md
+++ b/docs/ds/scapegoat.md
@@ -1,6 +1,4 @@
-# 替罪羊树
-
-**替罪羊树**是一种依靠重构操作维持平衡的重量平衡树。替罪羊树会在插入、删除操作时，检测途经的所有节点，若发现失衡，则将以该节点为根的子树重构。
+**替罪羊树**是一种依靠重构操作维持平衡的重量平衡树。替罪羊树会在插入、删除操作时，检测途经的节点，若发现失衡，则将以该节点为根的子树重构。
 
 我们在此实现一个可重的权值平衡树。
 
@@ -12,19 +10,25 @@ int cnt, // 树中元素总数
  wn[MAXN], // 本数据出现次数（为 0 代表已删除）
   s[MAXN], // 以本节点为根的子树大小
  sd[MAXN]; // 已删除节点不计的子树大小
+ 
+void Calc(int k) {
+// 重新计算以 k 为根的子树大小
+ s[k] = s[lc[k]] + s[rc[k]] + wn[k];
+ sd[k] = sd[lc[k]] + sd[rc[k]] + wn[k];
+}
 ```
 
 ## 重构
 
-首先，如前所述，我们需要判定一个节点是否需要重构。为此我们引入一个比例常数 $\alpha$（取值在 $$(0.5,1)），如某节点的子节点大小占它本身大小的比例超过 $\alpha$，则重构。
+首先，如前所述，我们需要判定一个节点是否应重构。为此我们引入一个比例常数 $\alpha$（取值在 $(0.5,1)$，一般采用 $0.7$ 或 $0.8$），若某节点的子节点大小占它本身大小的比例超过 $\alpha$，则重构。
 
-另外由于我们采用惰性删除（删除只使用 `wn[i]--`），已删除节点过多也影响效率。因此如果未被删除的子树大小占子树总大小的比例低于 $\alpha$，则亦重构。
+另外由于我们采用惰性删除（删除只使用 `wn[k]--`），已删除节点过多也影响效率。因此若未被删除的子树大小占总大小的比例低于 $\alpha$，则亦重构。
 
 ``` cpp
 inline bool CanRbu(int k) {
 // 判断节点 k 是否需要重构
  return wn[k] && (alpha * s[k] <= (double)std::max(s[lc[k]], s[rc[k]])
-  || alpha * s[k] >= (double)sd[k]);
+  || (double)sd[k] <= alpha * s[k]);
 }
 ```
 
@@ -41,13 +45,12 @@ void Rbu_Flatten(int& ldc, int k) {
 }
 
 int Rbu_Build(int l, int r) {
-// 将数组内 [l, r) 区间重建成树
- int mid = l + r >> 1;
+// 将 ldr[] 数组内 [l, r) 区间重建成树，返回根节点
+ int mid = l + r >> 1; // 选取中间为根使其平衡
  if(l >= r) return 0;
  lc[ldr[mid]] = Rbu_Build(l, mid);
- rc[ldr[mid]] = Rbu_Build(mid + 1, r);
- if(l + 1 == r) s[ldr[mid]] = sd[ldr[mid]] = wn[ldr[mid]];
- else Calc(ldr[mid]);
+ rc[ldr[mid]] = Rbu_Build(mid + 1, r); // 建左右子树
+ Calc(ldr[mid]);
  return ldr[mid];
 }
 
@@ -61,9 +64,11 @@ void Rbu(int& k) {
 
 ## 基本操作
 
+几种操作的处理方式较为类似，都规定了**到达空结点**与**找到对应结点**的行为，之后按**小于向左、大于向右**的方式向下递归。
+
 ### 插入
 
-插入时，从根节点向下寻找插入元素位置。如没有相同元素则新建节点，如有则直接 `wn[k]++`。最后，途经的可重构节点进行重构。
+插入时，到达空结点则新建节点，找到对应结点则 `wn[k]++`。递归结束后，途经的节点可重构的要重构。
 
 ``` cpp
 void Ins(int& k, int p) {
@@ -81,7 +86,7 @@ void Ins(int& k, int p) {
 
 ### 删除
 
-惰性删除，可以采用 `wn[k]--`。在最后沿途可重构节点要重构。
+惰性删除，到达空结点则忽略，找到对应结点则 `wn[k]--`。递归结束后，可重构节点要重构。
 
 ``` cpp
 void Del(int& k, int p) {
@@ -100,7 +105,9 @@ void Del(int& k, int p) {
 
 ### upper_bound
 
-返回权值严格大于某值的最小数的名次。每到一个节点，若查找值等于该节点权值，则返回该节点之后的名次。小于则向左走，大于则向右走。
+返回权值严格大于某值的最小名次。
+
+到达空结点则返回 1，因为只有该子树左边的数均小于查找数才会递归至此。找到对应结点，则返回该节点所占据的最后一个名次 + 1。
 
 ``` cpp
 int MyUprBd(int k, int p) {
@@ -110,9 +117,12 @@ int MyUprBd(int k, int p) {
  else if(p < w[k]) return MyUprBd(lc[k], p);
  else return sd[lc[k]] + wn[k] + MyUprBd(rc[k], p);
 }
- 
+```
+
+以下是反义函数，相当于采用 `std::greater<>` 比较，即返回权值严格小于某值的最大名次。查询一个数的排名可以用 `MyUprGrt(rt, x) + 1`。
+
+``` cpp
 int MyUprGrt(int k, int p) {
-// 反义的函数，相当于采用 std::greater<> 比较
  if(!k) return 0;
  else if(w[k] == p && wn[k]) return sd[lc[k]];
  else if(w[k] < p) return sd[lc[k]] + wn[k] + MyUprGrt(rc[k], p);
@@ -122,7 +132,7 @@ int MyUprGrt(int k, int p) {
 
 ### at
 
-给定名次，返回该名次上的权值。将名次与节点左子树大小及本节点重复次数比较，同样小于向左，大于向右。
+给定名次，返回该名次上的权值。到达空结点说明无此名次，找到对应结点则返回其权值。
 
 ``` cpp
 int MyAt(int k, int p) {
@@ -136,7 +146,7 @@ int MyAt(int k, int p) {
 
 ### 前驱后继
 
-以上两种功的组合。
+以上两种功能结合即可。
 
 ``` cpp
 inline int  MyPre(int k, int p) { return MyAt(k, MyUprGrt(k, p)); }
-- 
2.11.0