logo标签列表

如何适应树状数组解决区间最小值查询问题

algorithmdata-structuresfenwick-treermq
23

Fenwick树是一种数据结构，提供了一种有效的方式来回答主要查询：

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

这两个操作都在O(log(n))时间内完成，我理解逻辑和实现。实现一堆其他操作（如查找从N到M的总和）并不难。

我想了解如何将Fenwick树用于RMQ。显然可以更改前两个操作的Fenwick树。但我无法弄清楚如何在范围从N到M的情况下找到最小值。

在寻找解决方案后，大多数人认为这是不可能的，只有少数人声称它实际上是可以做到的（方法1, 方法2）。

第一个方法（用俄语编写，基于我的谷歌翻译，没有任何解释，只有两个函数）依赖于三个数组（初始、左和右），在我的测试中并不能正确地处理所有可能的测试案例。

第二种方法只需要一个数组，并且根据声明在 O(log^2(n)) 运行，几乎没有解释为什么以及如何工作。我没有尝试过测试它。

针对有争议的说法，我想了解是否可以增强Fenwick树来回答update(index, value)和findMin(from, to)。

如果可能的话，我很乐意听听它是如何工作的。

在第一种方法中，有一个明确的声明，即如果您正在寻找最大值，则可以增加单元格中的值，但不能减少，否则返回的值将不匹配数组。由于您正在寻找最小值，因此如果使用此方法，禁止增加存储的值。原因是，如果您将数组值移向所寻求的极值，您只需更新存储的数据，这需要O(log n)，但如果您从极值减少，则最坏情况是重新计算整个数组，这太昂贵且未实现。 - Vesper
3个回答
28

是的，你可以将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

我们挥动魔杖，以下树形结构出现:

Fenwick trees for problem example

请注意，在这两棵树中，每个节点代表该子树内所有节点的最小值。例如，在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]和每个tree[child_of_node]之间找到新的最小值，更改tree[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可能会在向上移动树时多次重新赋值。
二进制索引
在我的实验中，范围最小查询（RQM）的速度约为段树实现的两倍，更新略快。这主要原因是使用超级高效的位运算在节点之间移动。它们在这里非常好地解释了。段树的代码非常简单，因此请考虑性能优势是否真的值得。我Fenwick RMQ的更新方法有40行代码，并花了一些时间来调试。如果有人想要我的代码，我可以将其放在github上。我还编写了测试生成器来确保一切正常。
我从芬兰算法社区获得了理解这个主题和实现它的帮助。图片的来源是http://ioinformatics.org/oi/pdf/v9_2015_39_44.pdf，但他们归功于Fenwick的1994年论文。
有趣的是，是否可以在这里实现范围更新（实际上是范围递减）：“RangeUpdate（_index_，delta）”，它会在区间[0..index]（即从数组开头到_index_元素）上快速递减数组中所有值，而不是O（index * log n）？ - Nikki Chumakov
嗯，我认为这个数据结构无法实现。 - Atte Juvonen
所以这基本上与线段树相同。您正在以不同的格式存储相同的区间。 - timg
线段树是完全不同的数据结构。两种数据结构都可以用来解决相同的问题，时间复杂度大致相同。 - Atte Juvonen
2
没错，但如果你看一下被线段树和双树状数组覆盖的那些区间，你会发现它们是相同的。 - timg
1
Fenwick树结构适用于加法，因为加法是可逆的。它不适用于最小值，因为一旦您有一个单元格应该是两个或多个输入的最小值，您可能会丢失信息。
如果您愿意将存储要求翻倍，可以使用隐式构造的段树支持RMQ，就像二叉堆一样。对于具有n个值的RMQ，请在数组的位置[n，2n)中存储n个值。位置[1，n)是聚合，其公式为A(k) = min(A(2k)，A(2k+1))。位置2n是无限哨兵。更新例程应该如下所示。
def update(n, a, i, x):  # value[i] = x
    i += n
    a[i] = x
    # update the aggregates
    while i > 1:
        i //= 2
        a[i] = min(a[2*i], a[2*i+1])

这里的乘和除可以用移位来提高效率。
RMQ伪代码更加精细。这是另一个未经测试和未经优化的例程。
def rmq(n, a, i, j):  # min(value[i:j])
    i += n
    j += n
    x = inf
    while i < j:
        if i%2 == 0:
            i //= 2
        else:
            x = min(x, a[i])
            i = i//2 + 1
        if j%2 == 0:
            j //= 2
        else:
            x = min(x, a[j-1])
            j //= 2
    return x
你看过我链接中的方法1了吗？根据我的测试，它适用于大多数情况。 - Salvador Dali
@SalvadorDali 我没有。 - David Eisenstat
谢谢，@DavidEisenstat。虽然这并没有回答问题，但我认为这是RMQ的最简单解决方案。我在https://gist.github.com/tuanchauict/e2c873fdceb7fb3018ebd47f395cbf32中实现了你的想法。 - Tuan Chau
0
我刚刚实现了@atte-juvonen的方法的代码。我强烈建议你自己尝试实现它，但如果对某些人来说有点困难，这里是代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define maxn 200002
vector<int>t1(maxn, INT_MAX), t2(maxn,INT_MAX),vec(maxn, INT_MAX);

void update(int k, int v, int old){
    int node=k;
    int vv=v;
    while(node<maxn){
        if(vv>t1[node]){
            vv=min(vv, vec[node]);
            int lsb=(node & -node);
            int child=node-lsb;
            while(lsb/2>0){
                child+=lsb/2;
                lsb/=2;
                vv=min(vv,t1[child]);
            }
        }
        if(vv==t1[node])break;
        t1[node]=vv;
        node+=(node & -node);
    }
    node=k;
    while(node>0){
        if(v > t2[node]) {
            v = min(v,vec[node]);
            int ax=1;
            while(ax!=(node & -node)){
                int child=node+ax;
                ax<<=1;
                v=min(v, t2[child]);
            }
        }
        if(v == t2[node])break;
        t2[node] = v;
        node -= (node & -node);
    }
}
int query(int a, int b){
    // traversing BIT1, yet looking up values in BIT2
    int node=a;
    int val=INT_MAX;
    while(node+(node&-node)<=b){
        val=min(val, t2[node]);
        node+=(node&-node);
    }
    // traversing BIT2, yet looking up values in BIT1
    node=b;
    while(node-(node&-node)>=a){
        val=min(val, t1[node]);
        node-=(node&-node);
    }
    val=min(val, vec[node]);
    return val;
}

int32_t main(){
    int n,q,x,a,b; 
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>vec[i];
        update(i,vec[i], INT_MAX);
    }
    while(q--){
        cin>>x>>a>>b;
        if(x==1){
            int old=vec[a];
            vec[a]=b;
            update(a,b, old);
        }
        else
            cout<<query(a,b)<<endl;
    }
}
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接