árbol fenwick

Estructura de datos

Un árbol Fenwick o árbol indexado binario (BIT) es una estructura de datos que puede actualizar valores de manera eficiente y calcular sumas de prefijos en una matriz de valores.

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

En comparación con una matriz plana de valores, el árbol Fenwick logra un equilibrio mucho mejor entre dos operaciones: actualización de valores y cálculo de la suma del prefijo. Una matriz plana de valores puede almacenar los valores o las sumas de prefijos. En el primer caso, calcular sumas de prefijos requiere tiempo lineal; en el segundo caso, actualizar los valores de la matriz requiere tiempo lineal (en ambos casos, la otra operación se puede realizar en tiempo constante). Los árboles Fenwick permiten realizar ambas operaciones a tiempo. Esto se logra representando los valores como un árbol con nodos donde el valor de cada nodo en el árbol es la suma del prefijo de la matriz desde el índice del padre (inclusive) hasta el índice del nodo (exclusivo). El árbol en sí es implícito y puede almacenarse como una matriz de valores, con el nodo raíz implícito omitido de la matriz. La estructura de árbol permite que las operaciones de recuperación de valores, actualización de valores, suma de prefijos y suma de rangos se realicen utilizando únicamente accesos a nodos. ${\displaystyle n}$ ${\displaystyle O(\log n)}$ ${\displaystyle n+1}$ ${\displaystyle n}$ ${\displaystyle O(\log n)}$

Motivación

Dada una matriz de valores, a veces es deseable calcular el total acumulado de valores hasta cada índice de acuerdo con alguna operación binaria asociativa (la suma de números enteros es, con diferencia, la más común). Los árboles de Fenwick proporcionan un método para consultar el total acumulado en cualquier índice o suma de prefijo, además de permitir cambios en la matriz de valores subyacente y hacer que todas las consultas posteriores reflejen esos cambios.

Los árboles de Fenwick están especialmente diseñados para implementar el algoritmo de codificación aritmética , que mantiene los recuentos de cada símbolo producido y necesita convertirlos a la probabilidad acumulada de un símbolo menor que un símbolo determinado. El desarrollo de las operaciones que apoya estuvo motivado principalmente por el uso en ese caso. ^{[ cita necesaria ]}

Descripción

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

Una función importante en esta aritmética de índices es el bit de configuración menos significativo , también llamado operación de búsqueda del primer conjunto . Esta es la mayor potencia de dos que divide un índice . Esta es la potencia de dos (1, 2, 4, 8,...) y no el exponente (0, 1, 2, 3,...). Se puede calcular de manera eficiente en aritmética en complemento a dos como (donde & denota AND bit a bit ). ${\displaystyle i}$ ${\displaystyle \operatorname {lsb} (i)=i\mathbin {\&} -i}$

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

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

Un "árbol de Fenwick" consta en realidad de tres árboles implícitos en la misma matriz: 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 para traducir sumas de prefijos a índices (consultas de clasificación). ^[4] Los dos primeros normalmente se caminan hacia arriba, mientras que el tercero generalmente se camina hacia abajo.

El árbol de interrogatorios

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

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

El nodo tiene hijos ( ) y descendientes totales. (Estos números incluyen nodos mayores que , que se omiten y a los que nunca se accede). ${\displaystyle i}$ ${\displaystyle \log _{2}(\operatorname {lsb} (i))}$ ${\displaystyle i+1,i+2,i+4,...,i+\operatorname {lsb} (i)/2}$ ${\displaystyle \operatorname {lsb} (i)}$ ${\displaystyle n}$

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

Representación de un árbol de interrogación Fenwick de 16 nodos que contiene sumas de rangos de una matriz A de 15 nodos

Para encontrar el prefijo sum , sume los valores en , su padre, el padre de su padre, y así sucesivamente hasta (pero sin incluir) la raíz. Para calcular una suma de rango , reste las sumas de prefijo para y . Esto se puede optimizar deteniéndose en su primer ancestro común. ${\displaystyle A[1]+\cdots +A[i]}$ ${\displaystyle i}$ ${\displaystyle A[i]+\cdots +A[j]}$ ${\displaystyle i-1}$ ${\displaystyle j}$

El árbol de actualización

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

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

Aquí, los ancestros de un nodo son todos los nodos cuyas sumas de rango incluyen el suyo propio. Por ejemplo, contiene la suma de , contiene la suma de , etc. ${\displaystyle F[6]}$ ${\displaystyle A(4,6]}$ ${\displaystyle F[8]}$ ${\displaystyle A(4,8]}$

Para modificar uno de los valores , agregue el cambio a , luego al padre, luego a su abuelo, y así sucesivamente, hasta que el índice exceda . ${\displaystyle A[i]}$ ${\displaystyle F[i]}$ ${\displaystyle i}$ ${\displaystyle n}$

El árbol de búsqueda

A diferencia de los otros dos árboles, el árbol de búsqueda es un árbol binario , organizado 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 los índices numéricamente más cercanos de la altura adyacente. Los nodos con índices impares ( ) son hojas. Los nodos con índices pares tienen como hijos los dos nodos más cercanos del siguiente índice más bajo . El padre del nodo en el árbol de búsqueda es . ${\displaystyle \operatorname {lsb} (i)=1}$ ${\displaystyle i\pm \operatorname {lsb} (i)/2}$ ${\displaystyle i}$ ${\displaystyle (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 más alto existente , cuyo índice es la mayor potencia de 2 menor o igual a . ${\displaystyle n}$

Es posible que un nodo tenga un padre ficticio con un índice mayor que el que aún tiene 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. ${\displaystyle n}$

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 el 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 se puede encontrar mediante varios pasos hacia arriba 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 clasificación: dada una suma de prefijo, ¿en qué índice aparece? Esto se hace 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 enraizado en el nodo actual y un "índice alternativo" 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, la clasificación buscada es la consulta original y el índice alternativo es un valor de "desbordamiento" especial que indica que la clasificación no está en el árbol. (Dependiendo de la aplicación, o podría usarse para este propósito). ${\displaystyle 0}$ ${\displaystyle n+1}$

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

Estas tres posibilidades luego se dividen según 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), devuelve el índice actual.
  • es ficticio o el objetivo está en su subárbol derecho, devuelve el índice alternativo.
• Si el nodo actual no es una hoja y:
  • es ficticio, busque el mismo rango en su subárbol izquierdo con un índice alternativo 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 alternativo.
  • el objetivo está en su subárbol derecho, busque el rango objetivo menos el valor del nodo actual en el subárbol derecho, con un índice alternativo sin cambios.

Pseudocódigo

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

consulta de función (árbol, índice) es suma: = 0 mientras que el índice> 0 lo hace suma += árbol[índice] índice -= lsb(índice) suma de devoluciónLa función de actualización (árbol, índice, valor) es  mientras que el índice <tamaño (árbol) lo hace. árbol[índice] += valor índice += lsb(índice)

La función calcula el 1 bit menos significativo o el último bit establecido del dado o, equivalentemente, la potencia más grande de dos que también es divisor de . Por ejemplo, como se muestra en su representación binaria: . Esta función se puede implementar simplemente en código mediante una operación AND bit a bit : , asumiendo un tipo de datos entero con signo . ^[3] ${\displaystyle {\text{lsb}}(n)}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle {\text{lsb}}(20)=4}$ ${\displaystyle {\text{lsb}}(10{\textbf {1}}00_{2})=100_{2}=4}$lsb(n) = n & (-n)

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 a tiempo, pero es posible una construcción: ^[6] ${\displaystyle O(n\log {n})}$ ${\displaystyle O(n)}$

construcción de función (valores) es árbol := valores para cada índice, el valor en el árbol parentIndex := índice + lsb(índice) si parentIndex <tamaño (árbol) entonces árbol[parentIndex] += valor árbol de retorno

Ver también

• Ordenar árbol de estadísticas
• Sumas de prefijo
• Árbol de segmentos

Referencias

1. Boris Ryabko (1989). «Un código rápido en línea» (PDF) . Matemáticas soviéticas. Dokl . 39 (3): 533–537. Archivado (PDF) desde el original el 17 de julio de 2019 . Consultado el 17 de julio de 2019 .
2. Boris Ryabko (1992). "Un código adaptable rápido en línea" (PDF) . Transacciones IEEE sobre teoría de la información . 28 (1): 1400-1404. Archivado (PDF) desde el original el 14 de julio de 2019 . Consultado el 14 de julio de 2019 .
3. Peter M. Fenwick (1994). "Una nueva estructura de datos para tablas de frecuencia acumulativa". Software: práctica y experiencia . 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]. Amplia discusión sobre los detalles prácticos de implementación.
5. Knuth, Donald (2011). Algoritmos combinatorios, parte 1 . El arte de la programación informática . vol. 4A. Upper Saddle River, Nueva Jersey: Addison-Wesley Professional. págs. 164-165.
6. Halim, Steven; Halim, Félix; Effendy, Suhendry (3 de diciembre de 2018). Programación Competitiva . vol. 1 (4ª ed.). Prensa Lulu, incorporada. ISBN 9781716745522.

enlaces externos

• Un tutorial sobre los árboles Fenwick en TopCoder
• Un artículo sobre los árboles de Fenwick en Algorithmist
• Una entrada sobre Fenwick Trees en Polymath wiki
• intercambio de pila