algorithm - 难以理解解决Spoj DQuery的方法

Question

我正在尝试解决SPOJ上的此问题:
http://www.spoj.com/problems/DQUERY/

但是在尝试解决了几个小时后，我用谷歌搜索了一个可能的提示。我发现这里描述了一种方法:http://apps.topcoder.com/forums/;jsessionid=5A69961AF7DF7FBB00FDFE13B80B5D2E?module=Thread&threadID=627423&start=0&mc=13

但是我无法正确理解它。谁能帮助我理解这种方法。

Answer 1

The result of a query [a, b] is number of integers whose last occurrence in [1, b] is >= a.

假设我们从示例[1，1，2，1，3]中查询(2; 4)的序列。
要从多集[1、2、1]中建立一个集合，我们可以计算数字从1到b的最后位置，并仅选择> = a的那些位置。因此，在此示例中，这些事件是:4(对于1)和3(对于2)。它们都> = 2 = a，所以结果是2。

如何有效地存储所有最近出现的事件并能够快速找到所有> = a？在树中(间隔树或分段树)。我将使用 here描述的BIT(二叉索引树，也称为Fenwick树)。

但是首先我们必须将事件整理好。什么事事件可以是某个位置上的数字(因此，对(x; y)，其中x是数字，y是位置)-NumberEvent-或间隔(对(a; b))-QueryEvent。
我们必须对查询进行排序。首先，我们应该考虑数字，因为不将其添加到树查询中是没有意义的。因此，我们要从第一个位置开始(因此，我们按位置-y对NumberEvents进行排序)。在第一个位置上有1。我们记住last_position 1 = 1，并将位置1添加到树中。接下来，我们在位置2上有1。我们检查last_position 1，它不为空，因此我们从树中删除位置1，将位置2添加到树中，并更新last_position 1 =2。接下来我们在位置3上有2。我们检查last_position 2它是空的，所以我们有last_position 2 = 3，然后将3加到树上。接下来，我们在位置4上有1。我们从树中删除位置2，添加4并更新last_position 1 =4。现在有所不同。我们看到我们有一个b = 4的查询，并且考虑了位置[1; b]中的所有数字。剩下的唯一事情就是我们计算树中> = a = 2的位置。其中有2个:3、4。我们记得对于(2; 4)，结果是2(我们必须以良好的顺序打印它，所以我会记住查询不是((2; 4)，而是(2) ; 4; 2)，因为它是第二个查询，最后我将打印从1到q的所有查询。就是这样。因此，排序的查询是:

1 1 NumberEvent [number;position]
1 2 NumberEvent
2 3 NumberEvent
1 4 NumberEvent
2 4 QueryEvent [a;b] or [i;j] from the task - sorted by b
3 5 NumberEvent
1 5 QueryEvent
3 5 QuertEvent

对所有q + n查询进行排序和联接需要(q + n)log(q + n)时间。然后，对于每个q + n个查询，我们使用log(n)时间(因为树中最多有n个数字)。那么总复杂度为O((q + n)log(q + n))。

至于对树的操作。

我的描述将基于 this波兰语站点。有好的图像和代码。

索引:如果我们要为范围为0..x的数字创建间隔树，我们必须首先将x向上舍入为2的幂并减去1。因此对于x = 5，我们将x更改为2 ^ 3-1 = 7间隔类似于链接上的图像。例如。对于范围0..7和间隔4..5，它的索引是6(我们从1开始计数，而不是0)。

加/减值:假设我们要添加到范围为0..7的数字5的树中。间隔的5..5索引为5 + 2 ^ 3 = 13(因为我们有范围为0..2的值) ^ 3-1)。因此，我们更新tree [13] + = 1(第一棵tree []全部为0)。我们向上移动到包含5..5的间隔，该间隔为4..5，索引下限为(13/2)= 6(从链接上的图片中进行检查)。我们也必须更新它，所以我们要做tree [6] = tree [2 * 6 = 12] + tree [2 * 6 + 1 = 13]。然后:tree [6/2 = 3] = 1，tree [3/2 = 1] = 1，然后我们有1/2 = 0，所以我们停止了(正如我所说-我们从1开始计算索引，所以当我们有0时我们跳出循环)。添加数字的时间是对数的(每次我们将数字除以2)。我们可以用相同的方法从树中减去一个数字。只需减去1而不是相加即可。

查询:我们还可以检查对数时间中a..b区间中有多少个数字。我们对数字> = a感兴趣，因此结果为query(max)-query(a-1)。在我们的情况下，Max等于n，因为我们在树中保持位置，并且它们的范围是1..n。因此，我们对query(n，a-1)感兴趣。如何计算查询？首先将n和a-1的数字2 ^ 3相加(对于范围1..x)以得到间隔n..n和a-1..a-1。然后，当a!= b时，将tree [a](其中a = a-1)或tree [b](其中b = n)添加到结果中。如果a％2 = 0，则a是合适的 child ，我们将其添加。同样，b％2 = 1时，b是左 child 。我们对b的左子项感兴趣，因为否则它们将大于b，因此它们将超出范围。同一个。 a的左子项超出范围。

您可以查看查询代码并将其插入链接。

如果您有任何疑问，请询问。