¿Cómo implementar un árbol de Fenwick para sumas de prefijos dinámicas y selección ponderada?

1. Pregunta

Tienes una tabla de frecuencias dinámica de longitud n. Los valores en las posiciones se incrementan con frecuencia, y el sistema debe responder sumas de prefijos, sumas de rangos y ubicar la posición que contiene la unidad k-ésima de peso acumulado. Implementa un árbol de Fenwick (Binary Indexed Tree) con actualizaciones puntuales y consultas de prefijos en O(log n), y compáralo con un arreglo de prefijos simple y un árbol de segmentos.

2. Restricciones y aclaraciones

• Utiliza indexación basada en uno internamente; una API pública puede aceptar posiciones basadas en cero, pero debe convertirlas exactamente una vez.
• Las actualizaciones pueden ser deltas o diferencias respecto a un nuevo valor; especifica si se permiten valores negativos.
• Los rangos comienzan en 1. La selección ponderada solo está definida cuando todos los pesos son no negativos y el total es al menos k.
• Analiza primero la estructura monohilo; las actualizaciones concurrentes necesitan un bloqueo o particionamiento (sharding) y no pueden asumir que las escrituras de enteros ordinarias formen una instantánea consistente.

3. Idea central

La entrada i almacena la suma de un rango contiguo cuya longitud es lowbit(i) = i & -i. Una consulta de prefijo resta repetidamente lowbit, mientras que una actualización puntual suma repetidamente lowbit, por lo que cada una toca O(log n) posiciones del arreglo. La suma de un rango es la diferencia de dos prefijos. Cuando se conoce el arreglo inicial, propaga cada valor a su índice padre para construirlo en O(n).

4. Implementación de referencia

class Fenwick:
  init(values):
    tree = [0] * (len(values) + 1)
    for i from 1 to len(values):
      tree[i] += values[i - 1]
      parent = i + lowbit(i)
      if parent < len(tree):
        tree[parent] += tree[i]

  add(index0, delta):
    i = index0 + 1
    while i < len(tree):
      tree[i] += delta
      i += lowbit(i)

  prefixSum(index0Exclusive):
    total = 0
    i = index0Exclusive
    while i > 0:
      total += tree[i]
      i -= lowbit(i)
    return total

  rangeSum(left0, right0Exclusive):
    return prefixSum(right0Exclusive) - prefixSum(left0)

Para la selección ponderada, sondea desde el paso binario más alto. Si avanzar al índice candidato mantiene la suma acumulada por debajo de k, acepta ese paso y resta su suma de k; el índice final más uno es la posición que contiene el rango k. Esto requiere sumas acumuladas monótonas y, por lo tanto, no se puede usar directamente con pesos negativos.

5. Complejidad y compensaciones

Un árbol de Fenwick utiliza un arreglo de O(n). La adición puntual, las sumas de prefijos y la selección ponderada son de O(log n), mientras que la construcción lineal es de O(n). Es más compacto y a menudo tiene constantes menores que un árbol de segmentos, pero expresa de forma natural agregados de prefijo reversibles en lugar de mínimos de rango, actualizaciones de rango complejas o metadatos de segmento enriquecidos. Para datos de solo lectura, un arreglo de prefijos simple responde consultas en O(1); Fenwick se vuelve valioso cuando las actualizaciones son frecuentes.

6. Verificación y observabilidad

• Compara cada add, prefixSum y rangeSum con un arreglo ingenuo en entradas aleatorias, incluidos los casos de arreglo vacío, de un solo elemento y del último índice.
• Prueba con todo ceros, pesos muy grandes, un total exactamente igual a k, k fuera de rango e índices inválidos.
• Realiza una verificación cruzada de la construcción lineal frente a adiciones puntuales repetidas y compara tanto los arreglos internos como los resultados de las consultas.
• Genera pesos aleatorios no negativos para la selección ponderada y verifica los límites de prefijo para cada k; rechaza por separado las entradas con pesos negativos.

7. Errores comunes

• Mezclar índices basados en cero y en uno, de modo que la posición cero se omita o la última posición se desborde.
• Tratar i & -i como un truco de negación sin explicar que extrae el bloque binario más bajo.
• Utilizar la selección ponderada con valores negativos a pesar de que las sumas acumuladas ya no son monótonas.
• Sobrescribir un nodo del árbol con el nuevo valor en lugar de sumar el delta a lo largo de la ruta de actualización.

8. Criterios de evaluación en entrevistas

Explica lowbit y la cobertura de rangos

El candidato debe indicar qué rango contiguo almacena cada nodo y por qué las consultas y actualizaciones siguen saltos de lowbit.

Escribe una implementación sin errores de límites

La respuesta debe mantener una indexación interna basada en uno, manejar arreglos vacíos, posiciones inválidas y rangos semiabiertos, y nunca acceder más allá del final del arreglo.

Deduce la complejidad y la construcción

El candidato debe indicar los costos de O(log n) para consultas, actualizaciones y selección, la construcción lineal en O(n) y comparar los límites frente a arreglos de prefijos y árboles de segmentos.

Reconoce las precondiciones de la selección ponderada

La respuesta debe exigir pesos no negativos y sumas acumuladas monótonas, para luego probar coincidencias exactas, desbordamientos y límites con números grandes.