存树
结点结构：
- 左子节点
- 右子节点
- 以当前节点为根的子树大小（含权重）
- 当前节点权重（节点值出现的次数）
- 节点值
插入节点
局部问题：已知“树组”的总节点数，在当前子树中插入x
-
Case 1 - 当前为空根（即，树组为空，或是已经位于叶子节点的空儿子处）
若当前根为空，则在“树组”的末尾开一个节点作为树的根（注意特例：若是整个树组均为空，则说明没有大根，需要在
1位置新建所需的树）（0位置留给空节点标记用）。新节点的参数：左子为0（空节点），右子为0，值为
x，子树大小为1，权重为1。 -
Case 2 - 当前子树非空（有根）
-
2.1 - 若根等于
x只需将根的权重加一即可，完成任务。
-
2.2 - 若根大于
x说明要在左子树中插入
x。将当前的根设为左子树根（允许为空），继续下一次判断。
-
2.3 - 若根小于
x说明要在右子树中插入
x。将当前的根设为右子树根（允许为空），继续下一次判断。
-
在新建节点后，还需要将父节点指向新建的节点（若是新建节点存在叶子节点的话）。
因此在上面每一步挪动根节点时，都需要保留其父节点的记录。
判断新建立的叶子节点位于左子还是右子，只需将其值与父节点值进行比较即可。
查询排名
对于给定的子树根节点，查询值x在该子树中的排名等价于查询该子树中比x小的节点数量。
局部问题：查询局部子树中比x小的结点数量（含权）
-
Case 1 - 子树为空树（无节点）
若子树为空树，此时在该子树中比
x小的节点数量为0。 -
Case 2 - 子树非空
-
2.1 - 子树根节点值等于
x此时比
x小的结点即为整个左子树，因此局部问题的解为左子树大小（含权） -
2.2 - 子树根节点值大于
x此时所有“可能小于
x”的值都仅可能存在于左子树中，因此只需在左子树中寻找小于
x的节点数量即可，局部问题的解为递归“在左子树中查询小于
x的节点数量”。 -
2.3 - 子树根节点值小于
x此时左子树以及根节点的值均需要记在结果中，
且右子树中仍可能存在比
x小的结点。因此局部问题的解为：左子树大小（含权）+根节点大小（含权）+右子树中小于
x的节点数量。
-
需要注意的是，此时局部问题获得的值为“小于x的结点数量”，按照题目要求需要加1才能够获得x的排名。
按照排名查数
局部问题：在子树中查找排名为x的数
-
Case 1 - 子树为空树（无节点）
若子树为空树，此时排名为
x的数自然不存在，可以返回INF等无效值。 -
Case 2 - 子树非空
-
2.1 -
x>左子树大小 且x<左子树大小+根节点权重此时说明要找的第
x个数就是根节点的值。局部问题解：根节点值
-
2.2 -
x<=左子树大小说明第
x个数在左子树中，直接去左子树中找即可。局部问题解：在左子树中查找排名为
x的数。 -
2.3 -
x>左子树大小+根节点权重此时第
x个数在右子树中，在右子数中的排名为x-左子树大小-根权重。局部问题解：在右子树中查找排名为
x-l.size-root.count的数。
-
查找前驱
题目已经给出了提示：“若未找到则输出-2147483647”
说明可以将当前找到的“最大前驱”作为局部状态进行传递。
局部问题：已知当前子树外部的最大的x的前驱，在当前子树中查找并更新x的前驱。
-
Case 1 - 当前子树为空树（无节点）
由于已有子树外部的前驱，因此只需要将其输出即可。
-
Case 2 - 当前子树非空
-
2.1 - 当前子树根节点值等于
x说明
x的前驱可能存在于左子树中。 -
2.2 - 当前子树根节点值大于
x说明
x的前驱可能存在于左子树中。 -
2.3 - 当前子树根节点值小于
x说明
x的前驱可能存在于右子树中，或者等于根节点。注意：若是当前根节点比已有的前驱大，则需更新已有的前驱值。
对于上面的三种子情况，若左子树/右子树为空，只需输出当前已有的前驱值即可。
-
查找后驱
同查找前驱，不再赘述。
