Árboles de Fenwick (binary indexed)

Sumas de prefijo + actualizaciones puntuales, ambas O(log n). El trabajo de un segment tree para sumas — en un array y dos ciclos.

El árbol vive en los índices

• El índice i cubre i & -i posiciones que terminan en i (bit menos significativo encendido)
• Esos rangos embaldosan el array
• Consulta de prefijo: recorre HACIA ABAJO, i -= i & -i
• Actualización: recorre HACIA ARRIBA, i += i & -i
• ≤ log n bits por índice → O(log n)

Mira los saltos de índice

prefix_sum(6): 6 → 4 → 0 (resta el lowbit). update(3): 3 → 4 → 8 (suma el lowbit). No se dibuja ningún árbol — no hay árbol.

El especialista ligero le gana al segment tree

46× más rápido que el array crudo, 403× que las sumas de prefijo — y 4× más rápido que un segment tree (6ms vs 25ms).

El detalle: solo invertibles

• Suma de rango = prefix(hi) − prefix(lo−1) → necesita resta
• Sumas, xors, conteos — sí. Min / max / gcd — no (usa un segment tree)
• 1-indexed (el índice 0 no se usa) — el bug clásico

Conclusión

Mismo Big-O, constante diminuta → empata la herramienta con el problema exacto. Siguiente: B-trees — el árbol balanceado, reimaginado para disco.