Que haja alguma matriz. Na ausência de mudanças, podemos encontrar rapidamente (mais rápido que uma linha) o valor de algumas funções em um subsegmento dessa matriz. Para fazer isso, precisamos usar memória adicional e fazer um pré-cálculo.
Por exemplo, precisamos encontrar rapidamente a soma em algum segmento do array.
Vamos obter um array de somas de prefixos, em que o índice i será a soma de todos os elementos do array com índices menores ou iguais a i.
a[] – dada matriz, p[] – matriz de somas de prefixos
Contagem de array p:
Obviamente p[0] = a[0]. Observe que podemos facilmente recalcular p[i] por meio de p[i – 1], porque o valor no prefixo i é o valor no prefixo i – 1 + a[i].
Assim, o código para calcular as somas de prefixos fica assim:
int a[n], p[n];
p[0] = a[0< /extensão>];
para (int i = 1; i < n; i++)
p[i] = p[i - 1] + a[i];
Além disso, notamos que a soma no segmento – a diferença entre as duas somas no prefixo.
Verde = vermelho – azul
Assim, se for necessário encontrar a soma no intervalo [l,r], então a resposta é p[r] – p[l-1].
No entanto, se l – 1 elemento pode não existir. Para fazer sem if's, você pode inserir 1-indexing, e a[0] e p[0] terão valores neutros (0 para a soma).
Observe que esta técnica é um caso especial da fórmula de inclusão-exclusão, portanto, desta forma é possível armazenar não apenas somas, mas também outras funções, como multiplicação e xor.