Запросы суммы на отрезке
Дан массив из
n элементов и q запросов на сумму значений на отрезке. Ваша задача — эффективно отвечать на каждый запрос, вычисляя сумму элементов на заданном отрезке с помощью структуры данных «дерево отрезков» (segment tree).Ввод
Первая строка входных данных содержит два целых числа
n и q (1 ≤ n, q ≤ 100 000), которые обозначают количество элементов в массиве и количество запросов соответственно.Во второй строке содержится
n целых чисел (), разделённых пробелами, представляющих элементы массива.В следующих
q строках каждая строка содержит два целых числа и (), указывающих границы каждого запроса.Вывод
Для каждого запроса выведите сумму элементов в указанном диапазоне в отдельной строке.
Примеры
Ввод | Вывод |
5 3
1 2 3 4 5
1 3
2 4
1 5 | 6
9
15 |
Пояснение
Для данного массива
[1, 2, 3, 4, 5] выполняются следующие запросы на сумму на отрезке:- Запрос
[1, 3]: сумма элементов в диапазоне [1, 3] равна 1 + 2 + 3 = 6.
- Запрос
[2, 4]: сумма элементов в диапазоне [2, 4] равна 2 + 3 + 4 = 9.
- Запрос
[1, 5]: сумма элементов в диапазоне [1, 5] равна 1 + 2 + 3 + 4 + 5 = 15.
Constraints
Time limit: 10 seconds
Memory limit: 512 MB
Output limit: 1 MB