algorithm - 二叉索引树的应用

Question

我试图解决这个算法问题，我遇到了这个很好的解决方案：

“我们的想法是不对称地对待 a _i、 b _i和 c _i。BIT 支持从 1 开始的键间隔的最小查询。我们使用 c _i作为值和 b _i作为键。这些按增加 a 的顺序插入_i . 这样，对于每个 a _{i ，数据结构允许查询 c j}的最小值（可能是 ∞ ）在 [1..b _{i中的 b j}和 a _j < a _i。我们有 c _j < c _i当且仅当参赛者 i 不优秀时。”

来源

现在我很难理解这个解决方案。

这是我对这个解决方案的理解：我知道二叉索引树用于回答查询，例如在数组中查找区间的总和，它还支持元素更新。它分别以 O(logn) 时间复杂度执行这两项操作。现在这个解决方案说我们用键作为 c _i和值作为 b _i构建 BIT ，这基本上是 b _i是每个节点的附加值。现在我们在树中插入_i值增加的元素，这就是我失去控制的地方。我们插入节点的顺序以及该部分后面的语句所说的内容有什么关系，我不知道。

请帮助我了解此解决方案的含义。

Answer 1

让我们找到所有不优秀的参与者。另一个参与者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]as 键和b[j]is 值）来检查最后两个条件。很明显，j当且仅当前缀上的最小值[0, c[i])小于b[i].

总结一下，思路如下：我们对它们进行排序a[i]，然后忽略 的值a。这样，我们就从 3-D 问题转到了 2-D 问题，这更容易解决（这就是顺序很重要的原因。越大a[i]越好）。我们使用 BIT 来解决二维问题。