data-structures - fenwick tree c++

Rango de incremento usando Fenwick Tree

Question

Me preguntaba si un Fenwick Tree (o árbol indexado binario) se puede modificar a:

1) Incremente la frecuencia de todos los elementos en un rango en una cierta cantidad

2) Consulta la frecuencia de un solo elemento.

Esto es opuesto al tradicional Fenwick Tree donde las actualizaciones se realizan en un solo elemento y las consultas se realizan en un rango (algo así como un Fenwick Tree inverso).

Answer 1

¡Por supuesto!

Fenwick tree le permite hacer estas operaciones en 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

Aquí hay una implementación simple de un árbol de Fenwick en 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;
}

Ahora olvídate de las partes internas del árbol de Fenwick y concéntrate en el problema. Al usar el árbol de Fenwick, imagínese que literalmente almacena una serie de frecuencias y de alguna manera mágicamente realiza ambas operaciones en O (log n). La actualización de función modifica la frecuencia de un elemento individual y la consulta devuelve la suma de frecuencias de los primeros x elementos.

Entonces en el problema ''tradicional'' tenías estas operaciones:

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

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

Ahora, en lugar de almacenar la frecuencia de cada elemento individual, almacenemos las diferencias entre las frecuencias de los elementos adyacentes.

Estas son las nuevas operaciones:

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

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

Al incrementar las frecuencias en el rango [a ... b], simplemente incremente la diferencia en el índice a y disminuya la diferencia en el índice b + 1. Esto también es como decir: incremente todas las frecuencias en el rango [a..infinity] y disminuya todas las frecuencias en el rango [b + 1..infinity].

Para obtener la frecuencia del elemento en el índice x, suma todas las diferencias de frecuencias en el rango [0..x].