Que haya alguna matriz. En ausencia de cambios, podemos encontrar rápidamente (más rápido que una línea) el valor de algunas funciones en un subsegmento de esta matriz. Para hacer esto, necesitamos usar memoria adicional y hacer un cálculo previo.
Por ejemplo, necesitamos encontrar rápidamente la suma en algún segmento de la matriz.
Obtengamos una matriz de sumas de prefijos, en la que el índice i será la suma de todos los elementos de la matriz con índices menores o iguales a i.
un[] – matriz dada, p[] – matriz de sumas de prefijos
Recuento de matrices p:
Obviamente p[0] = a[0]. Tenga en cuenta que podemos volver a calcular fácilmente p[i] a través de p[i – 1], porque la cantidad en el prefijo i es la cantidad en el prefijo i – 1 + a[i].
Por lo tanto, el código para calcular sumas de prefijos se ve así:
int a[n], p[n];
p[0] = a[0< /intervalo>];
para (int i = 1; yo < n; yo++)
p[i] = p[i - 1] + a[i];
Además, notamos que la suma en el segmento – la diferencia entre las dos sumas en el prefijo.
Verde = rojo – azul
Así, si es necesario encontrar la suma en el intervalo [l,r], entonces la respuesta es p[r] – p[l-1].
Sin embargo, si yo – 1 elemento puede no existir. Para prescindir de los condicionales, puede ingresar la indexación 1, y a[0] y p[0] tendrán valores neutrales (0 para la suma).
Tenga en cuenta que esta técnica es un caso especial de la fórmula de inclusión-exclusión, por lo que de esta manera es posible almacenar no solo sumas, sino también otras funciones, como la multiplicación y xor.