使用树状数组实现区间增量

Question

我在想能否修改树状数组（或者说二叉索引树）来：

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

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

这与传统的树状数组不同，传统的树状数组是在单个元素上进行更新，而在范围内进行查询（有点像一个反向的树状数组）。

- Peter

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修改单个元素的频率，而query返回前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..无限大]内的所有频率，并递减范围[b + 1..无限大]内的所有频率。

要获取索引x处元素的频率，只需对范围[0..x]内频率的所有差异求和即可。

- user1321945