Árbol de Fenwick para sumas prefijas
Actualice un punto y consulte un prefijo en log n
Árbol de Fenwick para sumas prefijas es una lección gratuita de Coding Interview Prep en CoddyKit. Esta es la lección 1 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Coding Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Coding Interview Prep incluye 4 lecciones en total.
Por qué fallan los arrays de prefijos
Un array normal de sumas prefijas responde consultas de rangos al instante, pero una sola actualización obliga a reconstruirlo. Con muchas actualizaciones, eso se vuelve lento. ⏱️
Aparece el árbol de Fenwick
El árbol de Fenwick, o BIT, admite actualizaciones puntuales y consultas de prefijos en O(log n). Es la opción habitual para mantener sumas acumuladas dinámicas.
Indexado desde uno por diseño
Un árbol de Fenwick vive en un array indexado desde 1. Usamos el índice 0 como centinela inactivo, así que todos los datos reales comienzan en la posición 1.
tree = [0] * (n + 1)La magia del bit menos significativo
Cada índice cubre un bloque de valores. El tamaño del bloque es igual a i & -i, el bit menos significativo activado de i. Este sencillo truco hace funcionar todo el árbol.
lowbit = i & -iActualizar un único punto
Para añadir un valor en la posición i, avance saltando el lowbit en cada paso y visite cada bloque que contiene i.
while i <= n:
tree[i] += delta
i += i & -iConsultar una suma prefija
Para sumar los primeros i valores, avance hacia atrás restando el lowbit en cada paso hasta llegar a cero.
s = 0
while i > 0:
s += tree[i]
i -= i & -iAmbos bucles son logarítmicos
Cada bucle apaga un bit en cada iteración, por lo que se ejecuta como máximo log n veces. Por eso tanto la actualización como la consulta siguen siendo rápidas.
Suma de un rango a partir de dos prefijos
¿Quiere la suma de l a r? Calcule prefix(r) menos prefix(l-1), igual que con un array de prefijos estático, pero ahora las actualizaciones también son económicas.
range_sum = query(r) - query(l - 1)Construir el árbol
La construcción más sencilla simplemente llama a update para cada valor inicial. Es O(n log n) y suficientemente rápida para la mayoría de los concursos.
for i, v in enumerate(a, 1):
update(i, v)Un consumo de memoria mínimo
Un árbol de Fenwick solo necesita un array de tamaño n+1. Ese espacio compacto es una de las razones por las que es tan apreciado en los concursos. 💾
Cuándo recurrir a un BIT
Elija un árbol de Fenwick cuando intercale actualizaciones puntuales con consultas de prefijos o de sumas de rangos. Es breve de programar y difícil de superar.
Comprobación rápida
Fijemos cómo se desplazan los bucles.
Repaso: conceptos básicos de BIT
Conoció el árbol de Fenwick: indexado desde 1, basado en i & -i, con actualización puntual y consulta de prefijo, ambas en O(log n). A continuación, lo usaremos para contar inversiones. 🎯
Preguntas frecuentes
¿La lección «Árbol de Fenwick para sumas prefijas» es gratis?
Sí — el texto completo de «Árbol de Fenwick para sumas prefijas» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Coding Interview Prep, actualiza a CoddyKit PRO. El curso de Coding Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «Árbol de Fenwick para sumas prefijas»?
Actualice un punto y consulte un prefijo en log n Practicas Coding Interview Prep con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar Coding Interview Prep?
No se requiere experiencia previa. Coding Interview Prep en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 1 de 4.
¿Cuánto tiempo toma la lección «Árbol de Fenwick para sumas prefijas»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de Coding Interview Prep?
Sí. Cada lección de Coding Interview Prep incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- Árbol de Fenwick para sumas prefijas
- Inversiones con un BIT
- Árbol de segmentos: construcción y consultas
- Propagación diferida para actualizaciones de rangos