Consultas de Suma de Rangos
Se te proporciona un arreglo de
n elementos y q consultas de suma de rangos. Tu tarea es responder cada consulta de manera eficiente calculando la suma de los elementos en un rango determinado, usando una estructura de datos conocida como árbol de segmentos (segment tree).Entrada
La primera línea de la entrada contiene dos enteros
n y q (1 ≤ n, q ≤ 100 000), que representan la cantidad de elementos en el arreglo y el número de consultas, respectivamente.La segunda línea contiene
n números enteros separados por espacios (), que corresponden a los valores del arreglo.Las siguientes
q líneas contienen dos enteros y (), que indican los límites de cada consulta sobre el arreglo.Salida
Para cada consulta, imprime en una nueva línea la suma de los elementos que se encuentran dentro del rango especificado.
Ejemplos
Entrada | Salida |
5 3
1 2 3 4 5
1 3
2 4
1 5 | 6
9
15 |
Explicación
Para el arreglo
[1, 2, 3, 4, 5], se realizan las siguientes consultas de suma de rangos:- Consulta
[1, 3]: La suma de los elementos en el rango [1, 3] es 1 + 2 + 3 = 6.
- Consulta
[2, 4]: La suma de los elementos en el rango [2, 4] es 2 + 3 + 4 = 9.
- Consulta
[1, 5]: La suma de los elementos en el rango [1, 5] es 1 + 2 + 3 + 4 + 5 = 15.
Constraints
Time limit: 10 seconds
Memory limit: 512 MB
Output limit: 1 MB