Increment Range using Fenwick Tree

Question

I was wondering if a Fenwick Tree (or Binary Indexed Tree) can be modified to:

1) Increment the frequency all elements in a range by a certain amount

2) Query the frequency of a single element.

This is as opposed to the traditional Fenwick Tree where updates are done on a single element and queries are done over a range (kind of like an inverse Fenwick Tree).

Answer 1

Sure!

Fenwick tree allows you to do these operations in 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

Here's a simple implementation of a Fenwick tree in 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;
}

Now forget about the internals of the Fenwick tree and focus on the problem. When using Fenwick tree, just imagine it literally stores an array of frequencies and somehow magically does both operations in O(log n). Function update modifies the frequency of a single element and query returns sum of frequencies of first x elements.

So in the 'traditional' problem you had these operations:

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

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

Now, instead of storing frequency of each single element, let's store differences between frequencies of adjacent elements.

These are the new operations:

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

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

When incrementing frequencies in range [a..b], just increment difference at index a and decrement difference at index b+1. This is also like saying: increment all frequencies in range [a..infinity] and decrement all frequencies in range [b+1..infinity].

To get the frequency of the element at index x, just sum all differences of frequencies in range [0..x].