二叉索引树的应用
Application of binary indexed tree
我试图解决 this 算法问题，我遇到了这个很好的解决方案：
"The idea is to treat the ai, bi and
ci asymmetrically. The BIT supports minimum
queries for key intervals starting at 1. We use ci as values and
bi as keys. Those are inserted in the order of increasing ai. This
way, for each ai in turn, the data structure allows queries for the
smallest value of cj (possibly ∞) for bj in [1..bi) and
aj < ai. We have cj < ci if and only if contestant i is not
excellent."
现在我很难理解这个解决方案。
这是我对这个解决方案的理解：我知道二叉索引树用于回答查询，例如查找数组中的区间之和，它还支持元素更新。它分别以 O(logn) 时间复杂度执行这两个操作。现在这个解决方案说我们用键 ci 和值 bi 构建 BIT，基本上是 bi 是每个节点附带的附加值。现在我们在树中插入元素，其中 ai 的值递增，这是我失去控制的地方。我们插入节点的顺序以及该部分后面的语句有什么关系，我不知道。
请帮助我理解这个解决方案的内容。
让我们找出所有非优秀的参与者。另一个参与者 j 可以比参与者 i 更好，前提是他的 a[j] < a[i]。因此，我们可以忽略所有 a[j] 值较大的参与者。这就是我们按 a.
对它们进行排序的原因
这个条件是必要的，但还不够。我们还需要检查 b 和 c。我们该怎么做？我们需要知道是否有一个人 a[j] < a[i]（即在排序顺序中排在当前人之前的那个人）使得他的 b[j] < b[i] 和 c[j] < c[i]。我们构建一个 BIT（以 c[j] 作为键，b[j] 是值）来检查最后两个条件。很明显，当且仅当前缀 [0, c[i]) 上的最小值小于 b[i].
时，这样的 j 才存在
综上所述，思路如下：我们按a[i]排序，然后忽略a的值。这样，我们就从 3-D 问题变成了 2-D 问题，解决起来更简单（这就是顺序很重要的原因。a[i] 越大的人永远不会更好）。我们使用 BIT 来解决二维问题。
我试图解决 this 算法问题，我遇到了这个很好的解决方案：
"The idea is to treat the ai, bi and ci asymmetrically. The BIT supports minimum queries for key intervals starting at 1. We use ci as values and bi as keys. Those are inserted in the order of increasing ai. This way, for each ai in turn, the data structure allows queries for the smallest value of cj (possibly ∞) for bj in [1..bi) and aj < ai. We have cj < ci if and only if contestant i is not excellent."
现在我很难理解这个解决方案。
这是我对这个解决方案的理解：我知道二叉索引树用于回答查询，例如查找数组中的区间之和，它还支持元素更新。它分别以 O(logn) 时间复杂度执行这两个操作。现在这个解决方案说我们用键 ci 和值 bi 构建 BIT，基本上是 bi 是每个节点附带的附加值。现在我们在树中插入元素，其中 ai 的值递增，这是我失去控制的地方。我们插入节点的顺序以及该部分后面的语句有什么关系，我不知道。
请帮助我理解这个解决方案的内容。
让我们找出所有非优秀的参与者。另一个参与者 j 可以比参与者 i 更好，前提是他的 a[j] < a[i]。因此，我们可以忽略所有 a[j] 值较大的参与者。这就是我们按 a.
这个条件是必要的，但还不够。我们还需要检查 b 和 c。我们该怎么做？我们需要知道是否有一个人 a[j] < a[i]（即在排序顺序中排在当前人之前的那个人）使得他的 b[j] < b[i] 和 c[j] < c[i]。我们构建一个 BIT（以 c[j] 作为键，b[j] 是值）来检查最后两个条件。很明显，当且仅当前缀 [0, c[i]) 上的最小值小于 b[i].
j 才存在
综上所述，思路如下：我们按a[i]排序，然后忽略a的值。这样，我们就从 3-D 问题变成了 2-D 问题，解决起来更简单（这就是顺序很重要的原因。a[i] 越大的人永远不会更好）。我们使用 BIT 来解决二维问题。