árbol binario que almacena las sumas parciales: Nombre y implementaciones existentes

Question

Considere una secuencia de n números reales positivos, (un _i), y su secuencia de suma parcial, (s _i). Dado un número x ε (0, s _n], tenemos que encontrar i tal que s_{i -1} < x ≤ s _i. También queremos poder cambiar uno de los a _i sin tener que actualizar todas las sumas parciales. Ambos se pueden hacer en O (registro n) utilizando un árbol binario con a _i como valores de nodo de hoja y los valores de los nodos de hoja como la suma de los valores de los hijos respectivos. Si se conoce y se establece n, el árbol no tiene que ser autoequilibrado y se puede almacenar de manera eficiente en una matriz lineal. Además, si n tiene una potencia de dos, solo se requieren 2 n - 1 elementos de matriz. Ver Blue et al., Phys. Rev. E (1995), pp. R867-R868 para una aplicación. Dada la complejidad del problema y la simplicidad de la solución, me pregunto si esta estructura de datos tiene un nombre específico y si existen implementaciones existentes (preferiblemente en C++). Ya lo he implementado yo mismo, pero escribir estructuras de datos desde cero siempre me parece reinventar la rueda; me sorprendería que nadie lo haya hecho antes.

Answer 1

Fenwick tree (también conocido como árbol binario indexado) es una estructura de datos que mantiene una secuencia de elementos y puede calcular la suma acumulativa de cualquier rango de elementos consecutivos en el tiempo O (logn). El cambio de valor de cualquier elemento individual también necesita tiempo O (logn).

Answer 2

Esto se conoce como finger tree en programación funcional pero aparentemente hay implementaciones en lenguajes imperativos. En los artículos hay un enlace a blog post explicando una implementación de esta estructura de datos en C# que podría serle útil.