如何使Fenwick树适应范围最小的查询

Question

Fenwick树是一种数据结构,可以有效地回答主要查询:

• 将元素添加到数组的特定索引 update(index, value)
• 找到从1到N的元素总和 find(n)

两个操作都O(log(n))及时完成,我理解逻辑和实现.实现一堆其他操作并不难,比如找到从N到M的总和.

我想了解如何使Fenwick树适应RMQ.很明显,改变Fenwick树的前两个操作.但我没有弄清楚如何在从N到M的范围内找到最小值.

在寻找解决方案之后,大多数人认为这是不可能的,并且少数人声称它实际上可以完成(方法1,方法2).

第一种方法(用我的谷歌翻译写的俄语有0个解释,只有两个函数)依赖于三个数组(初始,左和右),因为我的测试对所有可能的测试用例都没有正常工作.

第二种方法只需要一个阵列,并且基于声明的运行,O(log^2(n))并且几乎没有解释为什么以及如何工作.我没有试过测试它.

---

鉴于有争议的主张,我想知道是否有可能增加Fenwick树来回答update(index, value)和findMin(from, to).

如果有可能,我会很高兴听到它是如何运作的.

Answer 1

是的,你可以使Fenwick树(二元索引树)适应

• 以O(log n)更新给定索引处的值
• 以O(log n)查询范围的最小值(已摊销)

我们需要2个Fenwick树和一个保存节点实际值的附加数组.

假设我们有以下数组:

index 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
value 1  0  2  1  1  3  0  4  2  5  2  2  3  1  0

我们挥动魔杖,出现以下树木:

请注意,在两个树中,每个节点表示该子树中所有节点的最小值.例如,在BIT2中,节点12具有值0,这是节点12,13,14,15的最小值.

查询

通过计算几个子树值和一个额外的实际节点值的最小值,我们可以有效地查询任何范围的最小值.例如,范围[2,7]的最小值可以通过取BIT2_Node2(表示节点2,3)和BIT1_Node7(表示节点7),BIT1_Node6(表示节点5,6)和REAL_4的最小值来确定 - 因此覆盖[2,7]中的所有节点.但是,我们如何知道我们想要查看哪些子树？

Query(int a, int b) {
  int val = infinity // always holds the known min value for our range

  // Start traversing the first tree, BIT1, from the beginning of range, a
  int i = a
  while (parentOf(i, BIT1) <= b) {
    val = min(val, BIT2[i]) // Note: traversing BIT1, yet looking up values in BIT2
    i = parentOf(i, BIT1)
  }

  // Start traversing the second tree, BIT2, from the end of range, b
  i = b
  while (parentOf(i, BIT2) >= a) {
    val = min(val, BIT1[i]) // Note: traversing BIT2, yet looking up values in BIT1
    i = parentOf(i, BIT2)
  }

  val = min(val, REAL[i]) // Explained below
  return val
}

可以在数学上证明两个遍历都将在同一节点中结束.该节点是我们范围的一部分,但它不是我们所看到的任何子树的一部分.想象一下我们范围的(唯一)最小值在该特殊节点中的情况.如果我们没有查找它,我们的算法会给出不正确的结果.这就是我们必须对真实值数组进行一次查找的原因.

为了帮助理解算法,我建议您使用笔和纸模拟它,在上面的示例树中查找数据.例如,范围[4,14]的查询将返回值BIT2_4(代表4,5,6,7),BIT1_14(代表13,14),BIT1_12(代表9,10,11, 12)和REAL_8,因此涵盖所有可能的值[4,14].

更新

由于节点表示自身及其子节点的最小值,因此更改节点将影响其父节点,但不影响其子节点.因此,为了更新我们从我们正在修改的节点开始的树和一路向上移动到虚构根节点(0或N + 1,这取决于树).

假设我们正在更新某个树中的某个节点:

• 如果新值<旧值,我们将始终覆盖该值并向上移动
• 如果新值==旧值,我们可以停止,因为没有更多的更改级联向上

• 如果新值>旧值,事情变得有趣.

  • 如果旧值仍然存在于该子树中的某个位置,那么我们就完成了
  • 如果没有,我们必须在real [node]和每个树[child_of_node]之间找到新的最小值,更改树[node]并向上移动

对于伪代码在值v更新节点一树:

while (node <= n+1) {
  if (v > tree[node]) {
    if (oldValue == tree[node]) {
      v = min(v, real[node])
      for-each child {
        v = min(v, tree[child])
      }
    } else break
  }
  if (v == tree[node]) break
  tree[node] = v
  node = parentOf(node, tree)
}

请注意,oldValue是我们替换的原始值,而v可能会在我们向上移动树时多次重新分配.

二进制索引

在我的实验中,Range Minimum Queries的速度大约是Segment Tree实现速度的两倍,而且更新速度略快.其主要原因是使用超高效的按位运算在节点之间移动.他们在这里得到了很好的解释.Segment Tree非常简单,所以想想性能优势真的值得吗？我的Fenwick RMQ的更新方法是40行,需要一段时间来调试.如果有人想要我的代码我可以把它放在github上.我还制作了一个粗暴的测试生成器,以确保一切正常.

我帮助理解了这个主题并从芬兰算法社区实现了它.图像来源是http://ioinformatics.org/oi/pdf/v9_2015_39_44.pdf,但信贷芬威克1994年的论文吧.