Árbol de Fenwick

Un árbol de Fenwick o árbol binario indexado (BIT) es una estructura de datos que almacena un array de valores y puede calcular de forma eficiente las sumas de prefijos de dichos valores , además de actualizarlos. También admite una búsqueda de rango eficiente para encontrar el prefijo más largo cuya suma no supere un valor especificado. Su uso principal consiste en trabajar con la función de distribución acumulativa de una tabla de frecuencias estadísticas que se actualiza con frecuencia.

Esta estructura fue propuesta por Boris Ryabko en 1989 ^{[ 1 ]} con una modificación posterior publicada en 1992. ^{[ 2 ]} Posteriormente se la conoció con el nombre de árbol de Fenwick en honor a Peter Fenwick, quien describió esta estructura en su artículo de 1994. ^{[ 3 ]}

Una matriz simple de valores es trivial (tiempo constante) de actualizar pero requiere $O(n)$ tiempo para calcular una suma de prefijos o buscar una longitud de prefijo.

Una matriz de sumas de prefijos puede devolver una suma de prefijos en tiempo constante y buscar una longitud de prefijo en $O(\log n)$ tiempo, pero requiere $O(n)$ Es hora de actualizar uno de los valores.

Un árbol Fenwick permite realizar las tres operaciones en $O(\log n)$ tiempo. Esto se logra representando los valores como un árbol con $n+1$ nodos donde cada nodo en el árbol almacena la suma de los valores desde el índice de su padre (exclusivo) hasta el índice del nodo (inclusivo). El árbol en sí es implícito y puede almacenarse como una matriz de $n$ valores, con el nodo raíz implícito omitido del array. La estructura de árbol permite realizar operaciones de recuperación de valor, actualización de valor, suma de prefijo y suma de rango utilizando únicamente $O(\log n)$ accesos a nodos.

Motivación

Dado un conjunto de valores, a veces resulta conveniente calcular la suma acumulada de los valores hasta cada índice mediante alguna operación binaria asociativa (la suma de enteros es, con diferencia, la más común). Los árboles de Fenwick proporcionan un método para consultar la suma acumulada en cualquier índice, o suma de prefijo, permitiendo además modificar el conjunto de valores subyacente y que todas las consultas posteriores reflejen dichos cambios.

Los árboles de Fenwick están diseñados específicamente para implementar la codificación aritmética adaptativa , que mantiene un recuento de cada símbolo producido y necesita convertirlo en la probabilidad acumulada de que un símbolo sea menor que un símbolo dado. El desarrollo de las operaciones que admite se motivó principalmente por su uso en ese caso.

Descripción

Un árbol de Fenwick es un árbol implícito donde los nodos se numeran consecutivamente y las relaciones padre-hijo se determinan mediante operaciones aritméticas sobre los índices de los nodos.

Una función importante en esta aritmética de índices es el bit menos significativo activado . Este es la mayor potencia de dos que divide un índice. $i$ . Esta es la potencia de dos (1, 2, 4, 8, ...) y no el exponente (0, 1, 2, 3, ...). Se puede calcular eficientemente en aritmética de complemento a dos como $\operatorname {lsb} (i)=i\mathbin {\&} -i$ (donde & denota AND bit a bit ).

Un árbol de Fenwick se entiende más fácilmente utilizando una matriz de base 1. $A[n]$ con $n$ valores. Usando la sintaxis de intervalo semiabierto , deje $A(i,j]=\{A[k]\}_{k=i+1}^{j},$ el rango de $i$ (exclusivo) a $j$ (inclusive). El conjunto Fenwick correspondiente $F[n]$ almacena las sumas de rango $\textstyle F[i]=\sum A(i-\operatorname {lsb} (i),i]$ . Es decir, la suma de $\operatorname {lsb} (i)$ valores que terminan con e incluyen $A[i]$ .

En algunas descripciones se utiliza un nodo ficticio, el nodo 0, pero nunca se accede a él y no es necesario almacenarlo explícitamente. $\operatorname {lsb} (0)=\infty ,$ pero ese valor nunca es realmente necesario. $F[0]$ puede considerarse que contiene la suma del rango vacío $A(0,0]=\{\}$ con valor 0.

Un "árbol de Fenwick" en realidad consta de tres árboles implícitos sobre el mismo arreglo: el árbol de interrogación, utilizado para traducir índices a sumas de prefijos; el árbol de actualización , utilizado para actualizar elementos; y el árbol de búsqueda, utilizado para traducir sumas de prefijos a índices (consultas de rango). ^{[ 4 ]} Los dos primeros se recorren normalmente hacia arriba, mientras que el tercero se recorre normalmente hacia abajo.

El árbol de interrogatorios

El árbol de interrogación se define de manera que el padre del nodo $i$ es $i-\operatorname {lsb} (i)=i\mathbin {\&} (i-1)$ . Por ejemplo, el padre de 6 = 110 ₂ es 4 = 100 ₂ . El nodo implícito 0 es la raíz.

Cada nivel $k$ del árbol contiene nodos con índices que corresponden a sumas de $k$ distintas potencias de 2 (con $k=0$ representando una suma vacía 0). Por ejemplo, nivel $k=1$ contiene nodos $1=2^{0},2=2^{1},4=2^{2},...$ y nivel $k=2$ contiene nodos $3=2^{1}+2^{0},5=2^{2}+2^{0},6=2^{2}+2^{1},...$

Nodo $i$ tiene $\log _{2}(\operatorname {lsb} (i))$ niños ( $i+1,i+2,i+4,...,i+\operatorname {lsb} (i)/2$ ), y $\operatorname {lsb} (i)$ descendientes totales. (Estos números incluyen nodos mayores que $n$ , que se omiten y nunca se acceden.)

El siguiente diagrama muestra la estructura del árbol de interrogación de un árbol Fenwick de 16 nodos, incluyendo la raíz, por lo que corresponde a una matriz A de 15 elementos:

Para hallar la suma del prefijo $A[1]+\cdots +A[i]$ , suma los valores en $i$ , su padre, el padre de su padre, y así sucesivamente hasta (pero sin incluir) la raíz. Para calcular una suma de rango $A[i]+\cdots +A[j]$ , restar las sumas de prefijos para $i-1$ y $j$ .

Esto se puede optimizar deteniéndose en su primer ancestro común. Un ejemplo extremo es solicitar una sola entrada. $A[j]$ En este caso, el ancestro común de $j$ y $i=j-1$ es $j-\operatorname {lsb} (j)$ , así que empieza con $F[j]$ y luego, siempre y cuando $i\neq j-\operatorname {lsb} (j)$ , restar $F[i]$ y actualizar .i := i - lsb(i)

El árbol de actualización

El árbol de actualización es la imagen especular del árbol de interrogación. El padre del nodo $i$ es $i+\operatorname {lsb} (i)=(i\mathbin {|} (i-1))+1$ (donde | denota OR bit a bit ). Por ejemplo, el padre de 6 = 110 ₂ es 8 = 1000 ₂ .

Este árbol conceptual es infinito, pero solo la parte con índices hasta $n$ se almacena o utiliza. Excluyendo los nodos ficticios con índices mayores que $n$ será un bosque de árboles disjuntos, uno por cada bit establecido en la representación binaria de $n$ .

Aquí, los ancestros de un nodo son todos los nodos cuyas sumas de rango incluyen la suya propia. Por ejemplo, $F[6]$ contiene la suma de $A(4,6]$ , $F[8]$ contiene la suma de $A(0,8]$ , etcétera.

Para modificar uno de los valores $A[i]$ , agregue el cambio a $F[i]$ , entonces $i$ el padre de, luego su abuelo, y así sucesivamente, hasta que el índice supere $n$ .

El árbol de búsqueda

A diferencia de los otros dos árboles, el árbol de búsqueda es un árbol binario , dispuesto en un orden que Knuth llama "montón lateral". ^{[ 5 ]} A cada nodo se le asigna una altura igual al número de ceros finales en la representación binaria de su índice, siendo el padre y los hijos el/los índice(s) numéricamente más cercanos de la altura adyacente. Nodos con índices impares ( $\operatorname {lsb} (i)=1$ ) son hojas. Los nodos con índices pares tienen como hijos a los dos nodos más cercanos del siguiente índice más bajo. $i\pm \operatorname {lsb} (i)/2$ Nodo $i$ El padre de en el árbol de búsqueda es $(i-\operatorname {lsb} (i))\mathbin {|} (2\cdot \operatorname {lsb} (i))$ .

Por ejemplo, los hijos de 6 = 110 ₂ son 5 = 101 ₂ y 7 = 111 ₂ , y su padre es 4 = 100 ₂ .

Aunque este árbol es potencialmente infinito, podemos definir su raíz como el nodo existente más alto , cuyo índice es la mayor potencia de 2 menor o igual a $n$ .

Es posible que un nodo tenga un padre ficticio con un índice mayor que $n$ pero aún así tener un abuelo existente. Si el ejemplo anterior se aplicara a un árbol de 5 nodos, entonces el nodo 5 tendría un padre ficticio 6, pero un abuelo existente 4.

El árbol de búsqueda puede considerarse una combinación de los dos árboles anteriores. El subárbol izquierdo de un nodo contiene todos sus descendientes en el árbol de actualización, mientras que su subárbol derecho contiene todos sus descendientes en el árbol de interrogación. El padre de un nodo en el árbol de búsqueda es su padre de interrogación o de actualización (dependiendo de si el nodo es un hijo derecho o izquierdo, respectivamente), y el otro tipo de padre puede encontrarse mediante varios pasos ascendentes en el árbol de búsqueda.

Sin embargo, los recorridos ascendentes en el árbol de búsqueda son poco comunes; su uso principal es realizar consultas de rango: dada una suma de prefijo, ¿en qué índice aparece? Esto se realiza mediante un recorrido descendente a través del árbol de búsqueda. Durante el recorrido, se mantienen tres variables: el índice del nodo actual, el rango que se busca en el subárbol con raíz en el nodo actual y un "índice de reserva" que se devolverá si el rango buscado es mayor que el que se puede encontrar en el subárbol.

Inicialmente, el nodo actual es la raíz, el rango buscado es la consulta original y el índice de reserva es un valor especial de "desbordamiento" que indica que el rango no está en el árbol. (Dependiendo de la aplicación, $0$ o $n+1$ podría utilizarse para este fin.)

En cada paso, el nodo actual es un nodo ficticio (índice mayor que $n$ ), o debemos decidir si la posición buscada está a la izquierda o a la derecha del final del nodo actual. Si el rango buscado es menor que el valor de la matriz de Fenwick $F[i]$ Para el nodo actual, debemos buscar en su subárbol izquierdo. Si es mayor, buscamos en su subárbol derecho. Si es igual, la dirección elegida depende de cómo se deseen gestionar las búsquedas de sumas que se encuentren exactamente entre dos nodos.

Estas tres posibilidades se subdividen a su vez en función de si el nodo actual es una hoja o no:

Si el nodo actual es una hoja y:
- El objetivo está en su subárbol izquierdo (vacío), devuelva el índice actual.
- Si es ficticio o el objetivo está en su subárbol derecho, devuelva el índice de reserva.
Si el nodo actual no es una hoja y:
- Es ficticio, busque el mismo rango en su subárbol izquierdo con un índice de reserva sin cambios.
- El objetivo está en su subárbol izquierdo, busque el mismo rango en su subárbol izquierdo con el índice actual como índice de reserva.
- El objetivo está en su subárbol derecho, busque el rango del objetivo menos el valor del nodo actual en el subárbol derecho, con un índice de reserva sin cambios.

Pseudocódigo

Una implementación sencilla en pseudocódigo de las dos operaciones principales en un árbol de Fenwick —consulta y actualización— es la siguiente:

La función query(tree, index) es suma := 0 mientras índice > 0 hacer suma += árbol[índice] índice -= lsb(índice) suma de retornoLa función update(árbol, índice, valor) es mientras índice < tamaño(árbol) hacer árbol[índice] += valor índice += lsb(índice)

La función ${\text{lsb}}(n)$ calcula el bit menos significativo de la señal dada $n$ o, equivalentemente, la mayor potencia de dos que también sea divisor de $n$ . Por ejemplo, ${\text{lsb}}(20)=4$ , como se muestra en su representación binaria: ${\text{lsb}}(10{\textbf {1}}00_{2})=100_{2}=4$ Esta función se puede implementar fácilmente en código mediante una operación AND bit a bitlsb(n) = n & (-n) : , asumiendo la negación en complemento a dos . ^{[ 3 ]}

Construcción

Un algoritmo ingenuo para construir un árbol de Fenwick consiste en inicializar el árbol con valores nulos y actualizar cada índice individualmente. Esta solución funciona en $O(n\log {n})$ tiempo, pero un $O(n)$ La construcción es posible: ^{[ 6 ]}

función construct(valores) es árbol := valores para índice desde 1 hasta tamaño(árbol) hacer índicePadre := índice + lsb(índice) si parentIndex < size(tree) entonces árbol[índicepadre] += árbol[índice] árbol de retorno

Véase también

Referencias

↑ Boris Ryabko (1989). "Un código rápido en línea" (PDF) . Soviet Math. Dokl . 39 (3): 533– 537. Archivado (PDF) del original el 17 de julio de 2019. Recuperado el 17 de julio de 2019 .
↑ Boris Ryabko (1992). "Un código adaptativo rápido en línea" (PDF) . IEEE Transactions on Information Theory . 28 (1): 1400–1404 . Archivado (PDF) del original el 14 de julio de 2019. Recuperado el 14 de julio de 2019 .
1 2 Peter M. Fenwick (1994). "Una nueva estructura de datos para tablas de frecuencia acumulativa". Software: Practice and Experience . 24 (3): 327– 336. CiteSeerX 10.1.1.14.8917 . doi : 10.1002/spe.4380240306 . S2CID 7519761 .
↑ Marchini, Stefano; Vigna, Sebastiano (14 de octubre de 2019). "Árboles Fenwick compactos para clasificación y selección dinámicas". arXiv : 1904.12370 [ cs.DS ]. Análisis exhaustivo de los detalles prácticos de la implementación.
↑ Knuth, Donald (2011). Algoritmos combinatorios, parte 1. El arte de la programación informática . Vol. 4A. Upper Saddle River, NJ: Addison-Wesley Professional. págs. 164–165 .
^ Halim, Steven; Halim, Félix; Effendy, Suhendry (3 de diciembre de 2018). Programación Competitiva 4 . vol. 1. Lulu Press, incorporada. ISBN 978-1-716-74552-2.

Enlaces externos

Tutorial sobre árboles de Fenwick en TopCoder
Un artículo sobre árboles de Fenwick en Algorithmist.
Una entrada sobre Fenwick Trees en la wiki de Polymath.
Stack Exchange

[1] Boris Ryabko (1989). "Un código rápido en línea" (PDF) . Soviet Math. Dokl . 39 (3): 533– 537. Archivado (PDF) del original el 17 de julio de 2019. Recuperado el 17 de julio de 2019 .

[2] Boris Ryabko (1992). "Un código adaptativo rápido en línea" (PDF) . IEEE Transactions on Information Theory . 28 (1): 1400–1404 . Archivado (PDF) del original el 14 de julio de 2019. Recuperado el 14 de julio de 2019 .

[:0-3] 1 2 Peter M. Fenwick (1994). "Una nueva estructura de datos para tablas de frecuencia acumulativa". Software: Practice and Experience . 24 (3): 327– 336. CiteSeerX 10.1.1.14.8917 . doi : 10.1002/spe.4380240306 . S2CID 7519761 .

[4] Marchini, Stefano; Vigna, Sebastiano (14 de octubre de 2019). "Árboles Fenwick compactos para clasificación y selección dinámicas". arXiv : 1904.12370 [ cs.DS ]. Análisis exhaustivo de los detalles prácticos de la implementación.

[5] Knuth, Donald (2011). Algoritmos combinatorios, parte 1. El arte de la programación informática . Vol. 4A. Upper Saddle River, NJ: Addison-Wesley Professional. págs. 164–165 .

[cp4-6] Halim, Steven; Halim, Félix; Effendy, Suhendry (3 de diciembre de 2018). Programación Competitiva 4 . vol. 1. Lulu Press, incorporada. ISBN 978-1-716-74552-2.

[ 1 ]

[ 2 ]

[ 4 ]

[ 5 ]

[ 6 ]