二进制索引树的应用

Question

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

“我们的想法是对待一个_我，B _我和 Ç_{我们使用c i作为值， b i作为关键字，它们按照公司的顺序插入给我一个 i。此 方式，对于每一个我反过来，该数据结构允许对C的 最小值查询Ĵ（可能∞）对于b Ĵ在[1..b 我）和 一个 j < a i。我们有çĴ <Ç我当且仅当参赛者我不 优秀。”}

source

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

这里是我理解这个解决方案：我知道二叉索引树用于回答查询，比如在数组中找到一个区间的总和，它也支持元素中的更新，它在O（logn）时间复杂度中执行两个操作。 s解决方案表示，我们建立密钥为BIT，其密钥为c _i，并且值为b _i，基本上b _i是附加值，与每个节点一起使用。现在，我们在树中插入元素，增加值 _i，这是我失去抓地力的地方。我们插入节点的顺序以及声明在这个部分后面说的是什么，我不知道。

请帮我理解这个解决方案是什么意思。

Answer 1

让我们找到所有非优秀的参与者。另一位参与者j只有在他的a[j] < a[i]时才能比参与者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的值。这样，我们从一个三维问题转向二维问题，这个问题更容易解决（这就是为什么顺序很重要的问题，那个更大的问题从来都不会更好）。我们使用BIT来解决二维问题。