Soma de prefixo
Motivação
Pense no seguinte problema
Dado um array de inteiros com \( n \) elementos, e \( q \) consultas do tipo \( [i, j] \), retorne a soma dos elementos do intervalo \( [i, j] \) do array.
Note
Tente resolver o problema antes de continuar a leitura.
Uma abordagem consistiria em calcular a soma de cada intervalo individualmente. Para cada consulta \( [i, j] \), somaríamos diretamente os elementos \( a_i + a_{i+1} + \ldots + a_j \). A complexidade dessa abordagem é \( O(n) \) operações por consulta, resultando em uma complexidade total de \( O(nq) \) para \( q \) consultas. Considerando que tanto \( n \) quanto \( q \) podem ser da ordem de \( 10^5 \), essa abordagem é computacionalmente lenta.
Introdução
Na abordagem acima possivelmente iremos realizar vários cálculos repetidamente, a ideia aqui é pré-processar o array \( a \) e armazenar as somas parciais em um novo array. Seja \( prefix \) esse array, iremos definir \( prefix[i] \) como a soma dos primeiros \( i \) elementos do array \( a \).
Assim, podemos calcular a soma de qualquer intervalo \( [i, j] \) em tempo constante \( O(1) \), coletando o valor da soma dos \( j \) primeiros elementos e subtraindo/removendo todos os elementos anteriores a \( i \), ou seja, os \( i - 1 \) primeiros elementos. Mostraremos que a complexidade de pré-processamento é \( O(n) \), resultando em uma complexidade total de \( O(n + q) \) para \( q \) consultas.
Definição
Seja \( a \) um array de inteiros, o array \( prefix \) é definido como:
Ou seja:
Dessa forma, podemos calcular a soma de qualquer intervalo \( [i, j] \) como:
Pois:
Código
Esse código é um exemplo de como implementar a técnica de prefixo para a soma. Assim, podemos calcular o range de \( i \) até \( j \) como:
Outras estruturas algébricas
Imagine que para resolver certo problema, você precise realizar os cálculo de um range de um array utilizando uma operação que não seja a de soma, como o produto ou bitwise XOR. Nessa seção, vamos ver como podemos generalizar o conceito de soma de prefixo para outras operações e verificar se podemos ou não utilizar a técnica.
Para isso, a rigor matemático, é necessário que dado um conjunto \( G \) e uma operação \( \star \), \( (G, \star) \) seja um grupo.
Propriedades de um grupo
\( (G, \star) \) é um grupo se, e somente se, satisfaz as seguintes propriedades:
Fechamento
Operar quaisquer dois elementos de \( G \) com \( \star \) deve resultar em um elemento de \( G \)
Associatividade
A operação \( \star \) deve ser associativa, ou seja, a ordem de aplicação da operação entre quaisquer três elementos não importa
Elemento neutro
Deve existir um elemento \( e \) em \( G \), tal que, operar qualquer elemento \( x \) em \( G \) com \( e \) resulta em \( x \)
Inverso
Deve existir um elemento \( y \) em \( G \) para cada elemento \( x \) em \( G \), tal que, operar \( x \) com \( y \) resulta no elemento neutro \( e \)
Dessa forma, poderemos utilizar todo o conhecimento adquirido acima. Pois, seja:
Observe que \( prefix[i] \) pertence a \( G \) pela propriedade de fechamento. Dessa forma:
Como \( prefix[i] \) pertence a \( G \), logo \( prefix[i] \) possui um elemento inverso, seja \( prefix[i]^{-1} \) esse elemento. Assim, podemos definir a operação de range como:
Pois:
Note
- Linha 2 e 3: Associatividade
- Linha 4: Inverso
- Linha 5: Elemento neutro
Exemplo da operação de range
Tome o array \( \{ a_1, a_2, a_3, a_4, a_5 \} \), tal que, \( a_1, a_2, a_3, a_4, a_5 \in G \) e \( (G, \star) \) é um grupo e deseja calcular o \( range(3, 5) \):
Exemplo de grupos
Soma nos reais
\( ( \mathbb{R}, + ) \)
- Elemento neutro: \( 0 \)
- Inverso: Função de subtração
Multiplicação nos inteiros
\( ( \mathbb{Z}, * ) \)
- Elemento neutro: \( 1 \)
- Inverso: Função de divisão
Bitwise XOR nos inteiros
\( ( \mathbb{Z}, \oplus ) \)
- Elemento neutro: \( 0 \)
- Inverso: Função de bitwise XOR
Código geral
Esse código é um exemplo de como implementar a técnica de prefixo para o produto. Para isso, utilizamos o inverso da multiplicação, que é a divisão. Assim, podemos calcular o range de \( i \) até \( j \) como: