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] 范围内的所有频率差异相加即可。