Calculadora de índices Fenwick

Un árbol de Fenwick, también llamado binary indexed tree, responde sumas de prefijo y actualizaciones en un punto en tiempo logarítmico al guardar rangos parciales cuyas longitudes son potencias de dos. Cada paso de navegación depende de un truco de bits: el bit menos significativo del índice 1-based actual, escrito lsb igual a i AND el negativo de i en complemento a dos. Sumar ese lsb recorre la cadena de actualización; restarlo recorre la cadena de consulta de prefijo. Estudiantes, programadores competitivos y autores de bibliotecas necesitan esos índices padre y siguiente sin rederivar las identidades bajo presión de examen. Esta calculadora de índices del árbol de Fenwick acepta un índice positivo i y, opcionalmente, un tamaño de árbol n; devuelve el lsb, el siguiente de actualización y el padre de consulta en un paso, formas binarias para enseñanza y, cuando se indica n, la ruta completa de actualización y de consulta del código BIT clásico.

Cómo los índices de Fenwick usan el bit menos significativo

En un binary indexed tree con índices 1-based, la celda en el índice i es responsable de un segmento contiguo del array subyacente cuya longitud es el bit menos significativo de i. Esa longitud se calcula como lsb igual a i AND la negación en complemento a dos de i, a menudo escrito i and minus i en lenguajes con aritmética modular sobre enteros de ancho fijo.

Geométricamente, invertir todos los bits por debajo del uno menos significativo aísla esa potencia de dos; el AND bit a bit con el índice original produce exactamente esa potencia. El bucle clásico de actualización parte del índice modificado y sustituye i por i más lsb mientras i permanece dentro del tamaño n del árbol, de modo que cada paso salta al siguiente índice que debe absorber el delta.

El bucle clásico de consulta de prefijo parte del extremo derecho del prefijo y sustituye i por i menos lsb mientras i sigue siendo positivo, sumando las celdas responsables que recubren el rango desde uno hasta el índice original. Juntas, esas dos recorridas implementan sumas de rango mediante la inclusión de dos prefijos.

Comprender un solo paso—siguiente de actualización igual a i más lsb, padre de consulta igual a i menos lsb—basta para depurar errores off-by-one, dibujar el árbol de responsabilidades en la pizarra y verificar que una implementación coincide con las identidades del manual antes de integrarla en una plantilla de concurso o en un pipeline analítico de producción.

Cuándo ayudan los pasos de un árbol de Fenwick

Entrenadores de programación competitiva y jueces en línea usan una calculadora de índices del árbol de Fenwick para que los alumnos comprueben pasos padre y siguiente mientras escriben a mano los bucles de actualización y consulta. Las herramientas de preparación de entrevistas necesitan un oráculo determinista que coincida con todo tutorial BIT estándar sobre las mismas entradas enteras, incluidos índices incómodos que son uno menos que una potencia de dos. La validación fallida no consume saldo.

Mantenga los índices en el rango positivo de treinta y dos bits, fije los arrays de ruta en las pruebas cuando size esté definido, y obtendrá navegación reproducible para deberes, capturas de documentación y edge workers sin montar un sandbox completo de estructuras de datos propio.