Decomposição de raiz

Temos um problema sobre como calcular rapidamente as somas no intervalo l...r em uma matriz estática a em menor que O(n) assintótica.

Vamos dividir o array a em k blocos do mesmo tamanho e primeiro calcular a soma dos elementos para cada um deles.

Agora, ao atender a solicitação, podemos passar pelos elementos do array a e adicioná-los ao resultado, também se um dos blocos estiver dentro do segmento, podemos adicionar sua soma ao resultado e pular o elementos deste bloco.

O número máximo de operações por consulta com este algoritmo é n / k + k, então o k ideal é igual à raiz quadrada de n.

 

Temos um problema sobre como calcular rapidamente as somas do segmento l...r no array a, no qual os elementos podem mudar um de cada vez, em assintóticas menores que O(n).

Esta tarefa é resolvida de forma semelhante à anterior, mas ao solicitar uma alteração, você precisa alterar o valor no bloco correspondente.

É dada uma tarefa na qual é necessário realizar operações em massa em um segmento e reconhecer um elemento por índice.

As operações em massa são realizadas como um cálculo de soma em um segmento.

Para cada bloco, armazenamos a alteração nesse bloco e, ao solicitar um elemento desse bloco, levamos essa informação em consideração.