Sume cualquier rango mediante resta

Construir el arreglo de sumas prefijas era la preparación. Ahora llega la magia: responder cualquier suma de rango con una sola resta. ⚡

Una suma de rango es simplemente un total grande menos otro más pequeño. Restar dos valores de sumas prefijas cancela limpiamente todo lo que queda fuera del rango.

Para sumar los elementos de l a r, reste prefix[l] de prefix[r + 1]. Esta única fórmula funciona para cualquier intervalo.

prefix[r + 1] contiene todo hasta r, y prefix[l] contiene todo lo anterior a l. La diferencia deja exactamente el segmento intermedio.

Para [3, 1, 4], el prefijo es [0, 3, 4, 8]. Para sumar los índices del 1 al 2, reste 3 de 8, lo que da 5. Eso coincide con 1 más 4.

Cada consulta consiste en una sola resta, por lo que se ejecuta en O(1). Mil consultas cuestan lo mismo por consulta que una sola.

El error más común está en el índice del extremo superior. Con un cero inicial, siempre se usa prefix[r + 1], no prefix[r]. Proteja ese límite.

Decida desde el principio si se incluye r. Esta fórmula considera el intervalo inclusivo tanto para l como para r, que es lo que esperan la mayoría de los problemas de programación competitiva.

Una pequeña función auxiliar mantiene legible la lógica y concentra los índices en un solo lugar. Apóyese en esta función auxiliar en lugar de insertar las operaciones matemáticas directamente.

Para sumar todo el arreglo, establezca l en 0 y r en n menos 1. La fórmula da prefix[n], el total general.

Siempre que un problema plantee muchas consultas de suma de intervalos sobre un arreglo fijo, las sumas de prefijos convierten un bucle de O(n) por consulta en respuestas instantáneas.

Necesita la suma de los índices de l a r, ambos inclusive.

Ahora puede responder cualquier suma de intervalo en O(1) con prefix[r + 1] menos prefix[l]. Tenga en cuenta el desfase del cero inicial y evitará errores. ✅