Un array de sumas de prefijos responde totales de rango en O(1), pero un solo valor que cambia te obliga a reconstruir O(n) entradas. Un árbol de Fenwick, también llamado árbol indexado binario, cambia un poco de velocidad en las consultas por actualizaciones rápidas: las dos operaciones cuestan O(log n).
La idea cabe en dos bucles. La celda tree[i] guarda el total de los últimos i & -i valores que terminan en la posición i, donde i & -i es el bit activo más bajo de i. Para sumar en la posición i, sube con i += i & -i y toca cada celda que la cubre. Para leer el prefijo hasta i, baja con i -= i & -i sumando celdas disjuntas. El árbol empieza en el índice 1 porque el 0 no tiene bit activo más bajo.
Recurre a un árbol de Fenwick cuando los valores cambian entre preguntas de prefijo o de suma de rango, o cuando cuentas cosas «hasta ahora» por valor: puntuaciones anteriores por debajo de esta, o marcas de tiempo anteriores por encima. Combinado con un array de diferencias también resuelve actualizaciones de rango con consultas puntuales. Para mínimos, máximos o combinaciones más complejas, usa un árbol de segmentos.
Las actualizaciones suben por el bit activo más bajo; las lecturas de prefijo bajan por él.