在 O(n log n) 中计算给定二叉树的每个子树中大于根的节点
Count nodes bigger then root in each subtree of a given binary tree in O(n log n)
我们得到一棵具有 n 个节点的树，其形式为指向其根节点的指针，其中每个节点都包含一个指向其父节点、左子节点和右子节点的指针，以及一个键，它是一个整数。对于每个节点 v，我想添加额外的字段 v.bigger，它应该包含键大于 v.key 的节点数，这些节点位于以 v 为根的子树中。将这样一个字段添加到树的所有节点总共需要 O(n log n) 时间。
我正在寻找任何能让我解决这个问题的提示。我尝试了几种启发式方法——例如，当考虑以自下而上的方式解决这个问题时，对于固定节点 v、v.left 和 v.right 可以提供 v 某种形式集合（平衡 BST？）与操作 bigger(x)，对于给定的 x returns，在对数时间内该集合中的元素数量大于 x。问题是，我们需要在 O(log n) 中合并这些集合，所以这似乎是不行的，因为我不知道任何支持快速合并的有序集合，如数据结构。
我也考虑过自上而下的方法 - 一个节点 v 为某个节点 u 向一些 u.bigger 添加一个当且仅当 u 位于到根的简单路径和 u<v。所以 v 可以以某种方式更新所有此类 u，但我无法想出任何合理的方法...
那么，思考这个问题的正确方法是什么？
如果我们为每个节点保留一个单独的二叉搜索树 (BST)，它由以该节点为根的子树的节点组成。
对于级别 k 的节点 v，合并具有 O(n/2^(k+1)) 个元素的两个子树 v.left 和 v.right 是 O(n/2^k).在为该节点形成 BST 后，我们只需计算 BST 右（传统）子树中的元素，就可以在 O(n/2^(k+1)) 时间内找到 v.bigger。总而言之，我们在级别 k 对单个节点进行了 O(3*n/2^(k+1)) 操作。总共有 2^k 个 k 级节点，因此我们有 O(2^k*3*n/2^(k+1)) 简化为 O(n)（删除 3/2 常数）。 k 级别的操作。有 log(n) 个级别，因此我们总共有 O(n*log(n)) 个操作。
在给定树中执行 depth-first 搜索（从根节点开始）。
当第一次访问任何节点（来自parent节点）时，将其键添加到某个order-statistics数据结构（OSDS）。同时向OSDS查询大于当前key的key个数，并用查询的否定结果初始化v.bigger。
最后一次访问任何节点时（来自右边child），查询OSDS中大于当前key的key个数，并将结果添加到v.bigger.
您可以将此算法应用于任何有根树（不一定是二叉树）。而且它不一定需要 parent 个指针（您可以使用 DFS 堆栈代替）。
对于 OSDS，您可以使用增强 BST 或 Fenwick 树。在 Fenwick 树的情况下，您需要预处理给定的树，以便压缩键的值：只需将所有键复制到一个数组，对其进行排序，删除重复项，然后用该数组中的索引替换键。
基本思路：
使用自下而上的方法，每个节点将从两个儿子的子树中获得两个有序值列表，然后找出其中更大的。完成后向上传递组合有序列表。
详情：
- 离开：
叶子明明有v.bigger=0。它们上方的节点创建一个包含两项的值列表，更新自身并将其自己的值添加到列表中。
- 所有其他节点：
从儿子那里得到两个列表，并以有序的方式合并它们。由于它们已经排序，因此这是 O(number of nodes in subtree)。在合并期间，您还可以找到有多少节点符合条件并获得节点的 v.bigger 的值。
为什么是 O(n logn)？
树中的每个节点都通过其子树中的节点数进行计数。这意味着根计算树中的所有节点，根的子节点每个计算（组合）树中的节点数（是的，是的，-1 代表根）等等相同的高度一起计算较低的节点数。这给了我们计数的节点数是 number of nodes * height of the tree - 即 O(n logn)
我们得到一棵具有 n 个节点的树，其形式为指向其根节点的指针，其中每个节点都包含一个指向其父节点、左子节点和右子节点的指针，以及一个键，它是一个整数。对于每个节点 v，我想添加额外的字段 v.bigger，它应该包含键大于 v.key 的节点数，这些节点位于以 v 为根的子树中。将这样一个字段添加到树的所有节点总共需要 O(n log n) 时间。
我正在寻找任何能让我解决这个问题的提示。我尝试了几种启发式方法——例如，当考虑以自下而上的方式解决这个问题时，对于固定节点 v、v.left 和 v.right 可以提供 v 某种形式集合（平衡 BST？）与操作 bigger(x)，对于给定的 x returns，在对数时间内该集合中的元素数量大于 x。问题是，我们需要在 O(log n) 中合并这些集合，所以这似乎是不行的，因为我不知道任何支持快速合并的有序集合，如数据结构。
我也考虑过自上而下的方法 - 一个节点 v 为某个节点 u 向一些 u.bigger 添加一个当且仅当 u 位于到根的简单路径和 u<v。所以 v 可以以某种方式更新所有此类 u，但我无法想出任何合理的方法...
那么，思考这个问题的正确方法是什么？
如果我们为每个节点保留一个单独的二叉搜索树 (BST)，它由以该节点为根的子树的节点组成。
对于级别 k 的节点 v，合并具有 O(n/2^(k+1)) 个元素的两个子树 v.left 和 v.right 是 O(n/2^k).在为该节点形成 BST 后，我们只需计算 BST 右（传统）子树中的元素，就可以在 O(n/2^(k+1)) 时间内找到 v.bigger。总而言之，我们在级别 k 对单个节点进行了 O(3*n/2^(k+1)) 操作。总共有 2^k 个 k 级节点，因此我们有 O(2^k*3*n/2^(k+1)) 简化为 O(n)（删除 3/2 常数）。 k 级别的操作。有 log(n) 个级别，因此我们总共有 O(n*log(n)) 个操作。
在给定树中执行 depth-first 搜索（从根节点开始）。
当第一次访问任何节点（来自parent节点）时，将其键添加到某个order-statistics数据结构（OSDS）。同时向OSDS查询大于当前key的key个数，并用查询的否定结果初始化v.bigger。
最后一次访问任何节点时（来自右边child），查询OSDS中大于当前key的key个数，并将结果添加到v.bigger.
您可以将此算法应用于任何有根树（不一定是二叉树）。而且它不一定需要 parent 个指针（您可以使用 DFS 堆栈代替）。
对于 OSDS，您可以使用增强 BST 或 Fenwick 树。在 Fenwick 树的情况下，您需要预处理给定的树，以便压缩键的值：只需将所有键复制到一个数组，对其进行排序，删除重复项，然后用该数组中的索引替换键。
基本思路：
使用自下而上的方法，每个节点将从两个儿子的子树中获得两个有序值列表，然后找出其中更大的。完成后向上传递组合有序列表。
详情：
- 离开：
叶子明明有v.bigger=0。它们上方的节点创建一个包含两项的值列表，更新自身并将其自己的值添加到列表中。 - 所有其他节点：
从儿子那里得到两个列表，并以有序的方式合并它们。由于它们已经排序，因此这是O(number of nodes in subtree)。在合并期间，您还可以找到有多少节点符合条件并获得节点的v.bigger的值。
为什么是 O(n logn)？
树中的每个节点都通过其子树中的节点数进行计数。这意味着根计算树中的所有节点，根的子节点每个计算（组合）树中的节点数（是的，是的，-1 代表根）等等相同的高度一起计算较低的节点数。这给了我们计数的节点数是 number of nodes * height of the tree - 即 O(n logn)