НачалоПодразделы
Другие разделы
| Занятие 1 |
| Занятие 2 |
| Занятие 3 |
| Занятие 4 |
| Занятие 5 |
| Занятие 6 |
| Занятие 7 |
| Занятие 9 |
| Занятие 10 |
| Занятие 11 |
| Занятие 12 |
| Занятие 13 |
| Занятие 14 |
| Занятие 15 |
| Занятие 16 |
| Занятие 17 |
| Занятие 18 |
| Занятие 19 |
| Занятие 20 |
Дата и время
16/11/2024 23:24:18
Занятие 8
D. Суммы
Дерево отрезков, декартово дерево, √-декомпозицияОлимпиадные задачи на русском языке
| 02/11/2006 | Практическое занятие 8 (D) |
| 21/04/2012 | Занятие 15 (A) |
| 05/03/2014 | Занятие 15 (A) |
| 14/07/2016 | Лето 2016 - 9 (A) |
| 19/03/2024 | Дерево отрезков (начало) (проводит BOGAT) (C) |
Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Есть массив, содержащий 100000 элементов, первоначально все элементы равны 0. В массиве производятся изменения элементов и требуется находить суммы части массива с `i`-го по `j`-ый элементы.
Ввод
В первой строке содержится число `K\ (1≤K≤50000)` – количество запросов. Далее следует `K` строк, в каждой строке содержится либо команда "S `i\ v`", где `1≤i≤100000,\ -100≤v≤100`, заменяющая значение `i`-го элемента массива на `v`, либо команда "Q `i\ j`", где `1≤i≤j≤100000`, требующая вывести сумму части массива с `i`-го по `j`-ый элементы.
Вывод
Для каждой команды 'Q' вывести на отдельной строке результат запроса.
Пример ввода
5 S 1 100 S 5 10 Q 5 10 S 5 -1 Q 1 100000
Пример вывода
10 99
