Module: Decomposição de raiz


Problem

1 /6


Soma no segmento - 1

Theory Click to read/hide

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.
 

Problem

Dado um array a de comprimento n (\(1 <= n <= 2 \cdot 10^6\ )< /span>, \(1 <= a_i <= 10^9\)). Também fornece m (\(1 <= m <= 500\)) consultas como l, r (\(1 <= l <= r <= n\)).

Para cada consulta, imprima a soma dos números entre l e r inclusive. Os elementos são numerados começando com 1 para n.

 

Exemplos
# Entrada Saída
1
4
1 2 3 4
2
1 4
1 1
 10
1
2
5
5 5 5 5 5
1
5 5
 5

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!