algorithm - name - ¿Es posible construir un árbol Fenwick en O(n)?

seo meta name

Question

El árbol Fenwick es una estructura de datos que permite dos tipos de operaciones (puede aumentarlas con más operaciones):

• actualización punto actualización update(index, value)
• query(index) suma de prefijos query(index)

Ambas operaciones están en O(log(n)) donde n es el tamaño de una matriz. No tengo problemas para entender cómo hacer ambas operaciones y la lógica detrás de ellas.

Mi pregunta es cómo puedo inicializar un árbol Fenwick desde una matriz. Claramente puedo lograr esto en O(nlog(n)) , llamando n veces la update(i, arr[i]) , pero hay una manera de inicializarlo en O(n) .

¿Por qué pregunto esto si wikipedia dice que puedes inicializar en nlog(n) ? Debido a que el artículo es tan rudimentario, no estoy seguro de si es la mejor complejidad que se puede lograr. También dibujar paralelos con la creación de montones ingenua que se realiza al poblar los montones uno por uno y se puede lograr en O(nlog(n)) versus la inicialización de montones inteligentes en O(n) me da la esperanza de que se pueda hacer algo similar en el árbol Fenwick .

Answer 1

[EDIT: tuve cosas "al revés" - arreglado ahora!]

Sí. Recorra los elementos de la matriz n en orden creciente del índice, agregando siempre la suma solo al siguiente índice más pequeño al que se debe agregar, en lugar de a todos ellos:

for i = 1 to n:
    j = i + (i & -i)     # Finds next higher index that this value should contribute to
    if j <= n:
        x[j] += x[i]

Esto funciona porque aunque cada valor contribuye a varias sumas de rango, después de procesar la suma de rango inferior a la que contribuye el valor (que en realidad no requiere "procesamiento", ya que la suma ya está ahí), ya no necesitamos mantener su identidad separada - Se puede fusionar de forma segura con todos los demás valores que contribuyen a las sumas de rango restantes.

TTBOMK este algoritmo es "nuevo", pero entonces no he mirado mucho;)