使用芬威克树的增量范围

Question

我想知道是否可以将芬威克树(或二进制索引树)修改为：

1)将范围内的所有元素的频率增加一定量

2)查询单个元素的频率。

这与传统的芬威克树不同，在这种情况下，更新是在单个元素上进行的，查询是在一个范围内完成的(有点像反向的芬威克树)。

Answer 1

好的!

芬威克树允许您在O(log )中执行这些操作：

update(x, delta)   => increases value at index x by delta
query(x)           => returns sum of values at indices 0,1,2,...,x

下面是一个在C++中实现芬威克树的简单方法：

int F[MAX];

void update( int x, int delta ) {
  for( ++x; x < MAX; x += x&-x ) F[x] += delta;
}

int query( int x ) {
  int sum = 0;
  for( ++x; x > 0; x -= x&-x ) sum += F[x];
  return sum;
}

现在，忘掉芬威克树的内部，专注于这个问题。当使用芬威克树时，想象一下它确实存储了一系列的频率，并以某种方式在O(log )中神奇地完成了这两个操作。函数更新修改单个元素的频率，查询返回前x元素的频率之和。

因此，在“传统”问题中，您有这样的操作：

void incFreqAt( int index ) {
  update( index, 1 );
}

int getFreqAt( int index ) {
  return query( index ) - query( index-1 );
}

现在，让我们来存储相邻元素的频率之间的差异，而不是存储单个元素的频率。

这些是新的行动：

void incFreqFromTo( int a, int b, int delta ) {
  update( a, delta );
  update( b+1, -delta );
}

int getFreqAt( int index ) {
  return query( index );
}

当在a.b范围内增加频率时，只需在指数a处增量差，在索引b+1处增量差，这也相当于:增加a..infinity范围内的所有频率，减少范围b+1..infinity中的所有频率。

要得到元素在索引x处的频率，只需将0..x范围内的所有频率差异之和。