使用Fenwick树增加范围

Question

我想知道Fenwick树(或二进制索引树)是否可以修改为:

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

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

这与传统的Fenwick树相反,传统的Fenwick Tree在单个元素上进行更新,并且在一个范围内完成查询(类似于反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)中执行这两个操作.函数更新修改单个元素的频率,查询返回前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]中的所有频率差加起来.