Actualización de rango + consulta de rango con árboles indexados binarios

10

Estoy tratando de entender cómo se pueden modificar los árboles indexados binarios (árboles fenwick) para manejar tanto las consultas de rango como las actualizaciones de rango.

Encontré las siguientes fuentes:

http://kartikkukreja.wordpress.com/2013/12/02/range-updates-with-bit-fenwick-tree/ http://programmingcontests.quora.com/Tutorial-Range-Updates-in-Fenwick-Tree http : //apps.topcoder.com/forums/? module = Thread & threadID = 756271 & start = 0 & mc = 4 # 1579597

Pero incluso después de leerlos todos, no pude entender cuál es el propósito del segundo árbol indexado binario o qué hace.

¿Podría alguien explicarme cómo se modifica el árbol indexado binario para manejar esto?

data-structures binary-trees search-trees 1110101001
fuente

Respuestas:

9

Suponga que tiene una matriz vacía:

0  0  0  0  0  0  0  0  0  0  (array)
0  0  0  0  0  0  0  0  0  0  (cumulative sums)

Y quería hacer una actualización de rango de +5 a [3..7]:

0  0  0  5  5  5  5  5  0  0  (array)
0  0  0  5 10 15 20 25 25 25  (desired cumulative sums)

¿Cómo podría almacenar las sumas acumulativas deseadas utilizando 2 árboles indexados binarios?

El truco consiste en utilizar dos árboles indexados binarios, BIT1 y BIT2, donde la suma acumulativa se calcula a partir de su contenido. En este ejemplo, esto es lo que almacenaríamos en los dos árboles:

0   0   0   5   5   5   5   5   0   0  (BIT1)
0   0   0  10  10  10  10  10 -25 -25  (BIT2)

Para encontrar sum[i], calcula esto:

sum[i] = BIT1[i] * i - BIT2[i]

Por ejemplo:

sum[2] = 0*2 - 0 = 0
sum[3] = 5*3 - 10 = 5
sum[4] = 5*4 - 10 = 10
...
sum[7] = 5*7 - 10 = 25
sum[8] = 0*8 - (-25) = 25
sum[9] = 0*9 - (-25) = 25

Para lograr los valores deseados de BIT1 y BIT2 para la actualización de rango anterior, realizamos 3 actualizaciones de rango:

  • Necesitamos hacer una actualización de rango de +5 a los índices 3..7 para BIT1.

  • Necesitamos hacer una actualización de rango de +10 a los índices 3..7 para BIT2.

  • Necesitamos hacer una actualización de rango de -25 a los índices 8..9 para BIT2.

Ahora hagamos una transformación más. En lugar de almacenar los valores mostrados anteriormente para BIT1 y BIT2, en realidad almacenamos sus sumas acumulativas. Esto nos permite hacer las 3 actualizaciones de rango anteriores al hacer 4 actualizaciones a las sumas acumulativas:

BIT1sum[3] += 5
BIT1sum[8] -= 5
BIT2sum[3] += 10
BIT2sum[8] -= 35

En general, el algoritmo para agregar un valor v a un rango [i..j] sería:

BIT1sum[i]   += v
BIT1sum[j+1] -= v
BIT2sum[i]   += v * (i-1)
BIT2sum[j+1] -= v * j

donde la sintaxis + = y - = simplemente significa actualizar la estructura de datos de suma acumulativa BIT con un valor positivo o negativo en ese índice. Tenga en cuenta que cuando actualiza la suma acumulativa BIT en un índice, afecta implícitamente todos los índices a la derecha de ese índice. Por ejemplo:

0 0 0 0 0 0 0 0 0 0 (original)

BITsum[3] += 5

0 0 0 5 5 5 5 5 5 5 (after updating [3])

BITsum[8] -= 5

0 0 0 5 5 5 5 5 0 0 (after updating [8])

Los árboles de Fenwick almacenan sumas en un árbol binario. Es fácil hacer las actualizaciones que se muestran arriba en un árbol Fenwick, en tiempo .O(log⁡n)

JS1
fuente
¿Cuál fue su motivación inicial para crear BIT2 y luego tenerlo sum[i] = BIT1[i] * i - BIT2[i]? Parece que funciona, pero parece tan arbitrario ... ¿qué idea le permite llegar a esto?
1110101001
3
Bueno, no inventé este algoritmo. Lo leí como lo hiciste tú. Pero una cosa a tener en cuenta es que cuando agrega una actualización de rango, sus sumas acumulativas se convierten en una secuencia creciente (5, 10, 15, 20, ...). Los BIT no almacenan secuencias crecientes como esa. Pero si almacena una constante (5) en el BIT y multiplica el valor del BIT por el índice, obtendrá una secuencia creciente como la que desea. Sin embargo, debe arreglar el comienzo y el final de la secuencia. Para eso es el segundo árbol.
JS1
Bueno en general, pero me pareció confuso que escribieras "En lugar de almacenar los valores mostrados anteriormente para BIT1 y BIT2, en realidad almacenamos sus sumas acumulativas". Diría que en realidad estás haciendo lo contrario, es decir, almacenando los deltas .
j_random_hacker