Module: Descomposición de la raíz


Problem

1 /6


Suma en segmento - 1

Theory Click to read/hide

Tenemos un problema sobre cómo calcular rápidamente las sumas en el intervalo l...r en una matriz estática a en asintóticas menores que O(n).
Dividamos el arreglo a en k bloques del mismo tamaño y primero calculemos la suma de elementos para cada uno de ellos.
Ahora, al responder la solicitud, podemos revisar los elementos de la matriz a y agregarlos al resultado, también si uno de los bloques se encuentra dentro del segmento, entonces podemos agregar su suma al resultado y omitir el elementos de este bloque.
El número máximo de operaciones por consulta con este algoritmo es n / k + k, por lo que el k óptimo es igual a la raíz cuadrada de n.
 

Problem

Dada una matriz a de longitud n (\(1 <= n <= 2 \cdot 10^6\ )< /span>, \(1 <= a_i <= 10^9\)). También dado m (\(1 <= m <= 500\)) consultas como l, r (\(1 <= l <= r <= n\)).

Para cada consulta, imprima la suma de números entre l y r inclusive. Los elementos se numeran comenzando con 1 a n.

 

Ejemplos

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!

# Entrada Salida
1
4
1 2 3 4
2
1 4
1 1
 10
1
2
5
5 5 5 5 5
1
5 5
 5