data-structures - 使用 Fenwick 树增加范围

Question

我想知道是否可以将 Fenwick 树（或二进制索引树）修改为：

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

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

这与传统的 Fenwick 树相反，传统的 Fenwick 树在单个元素上完成更新，查询在一个范围内完成（有点像逆 Fenwick 树）。

Answer 1

当然！

Fenwick 树允许您在 O(log n) 中执行这些操作：

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

这是 C++ 中 Fenwick 树的简单实现：

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;
}

现在忘记 Fenwick 树的内部结构并专注于问题。当使用 Fenwick 树时，想象一下它实际上存储了一个频率数组，并且以某种方式神奇地在 O(log n) 中完成了这两个操作。函数 update 修改单个元素的频率，查询返回前 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] 内的所有频率差相加即可。