Задача взята с сайта e-olymp.com
Условие задачи
Мама подарила мальчику Диме массив длины [latex]n[/latex]. Массив этот не простой, а особенный. Дима может выбрать два числа [latex]i[/latex] и [latex]d[/latex] ([latex]1\leq i\leq n[/latex], [latex]-1000\leq d\leq 1000[/latex]), и элемент с индексом [latex]i[/latex] магически становится равным [latex]d[/latex]. Дима играет со своим массивом, а мама время от времени задает ему вопросы — какова сумма всех чисел в массиве с индексами от [latex]f[/latex] до [latex]t[/latex]? Дима легко справился с этими вопросами, сможете ли Вы?
Входные данные
В первой строке находятся два целых числа [latex]n[/latex] и [latex]q[/latex] [latex]1\leq n\leq 5\cdot 10^{5},~1\leq q\leq 10^{5}[/latex] — количество элементов в массиве и суммарное количество операций и запросов соответственно. В следующей строке дано [latex]n[/latex] чисел [latex]a_{1},a_{2},\ldots,a_{n}[/latex] [latex]\left ( -1000\leq a_{i}\leq 1000 \right )[/latex] — начальное состояние массива. В следующих [latex]q[/latex] строках заданы операции и запросы. Первый символ в строке может быть [latex]=[/latex] или [latex]?[/latex]. Если строка начинается с [latex]=[/latex], то это операция присваивания. Далее следуют [latex]i[/latex] и [latex]d[/latex], ограничения на которые описаны в условии. Если строка начинается с [latex]?[/latex], то это запрос. Далее следуют числа [latex]f[/latex] и [latex]t[/latex] [latex]\left (1\leq f,~t\leq n \right )[/latex].
Выходные данные
Для каждого запроса выведите сумму чисел в массиве с индексами от [latex]f[/latex] до [latex]t[/latex], по одному результату в строке.
Тесты
| Входные данные | Выходные данные |
| 3 3 1 2 3 ? 1 3 = 3 2 ? 1 3 |
6 5 |
| 5 3 1 2 3 4 5 ? 1 5 = 1 7 ? 1 3 |
15 12 |
| 5 6 1 2 3 4 5 ? 1 5 = 1 0 ? 1 5 = 2 7 ? 1 5 ? 1 3 |
15 14 19 10 |
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
#include <iostream> using namespace std; // построение дерева void build (int tree[], int arr[], int v, int left, int right) { if (left != right) { int middle = (left + right) / 2; build (tree, arr, v*2, left, middle); build (tree, arr, v*2+1, middle+1, right); tree[v] = tree[v*2] + tree[v*2+1]; } else tree[v] = arr[left];} // запрос суммы int sum (int tree[], int v, int left, int right, int from, int to) { if (from > to) return 0; if (from == left && to == right) return tree[v]; int middle = (left + right) / 2; return sum(tree,v*2,left,middle,from,min(to,middle))+sum(tree,v*2+1,middle+1,right,max(from,middle+1),to); } // операция присваивания void update (int tree[], int v, int left, int right, int index, int new_val) { if (left != right) { int middle = (left + right) / 2; if (index <= middle) update (tree, v*2, left, middle, index, new_val); else update (tree, v*2+1, middle+1, right, index, new_val); tree[v] = tree[v*2] + tree[v*2+1]; } else tree[v] = new_val; } int main() { int n, q, i, d, from, to; char query; cin >> n >> q; int size = 2*n; /* максимальный размер дерева*/ int arr[n], tree[size]; for(int i = 0; i < n; i++) cin >> arr[i]; /* передаем функции построения массив для записи дерева, исходный массив, корень и границы отрезка, принадлежащего корню */ build(tree, arr, 1, 0, n-1); for (q; q>0; q--) { cin >> query; if (query == '=') { cin >> i >> d; update(tree, 1, 0, n-1, i-1, d); } else if (query == '?') { cin >> from >> to; cout << sum(tree, 1, 0, n-1, from-1, to-1) << endl; } } } |
Засчитанное решение на e-olymp.com.
Решение
Для решения данной задачи необходимо воспользоваться структурой данных «дерево отрезков».
Для построения дерева считываем исходный массив, затем запускаем функцию построения от корня дерева. Если длина массива не равна единице или функция была запущена не от листа, то она вызывается рекурсивно от каждого из двух сыновей и суммирует вычисленные значения. Если функция построения была вызвана от листа, то значения элементов массива записываются в дерево.
Для операции присваивания передаем рекурсивной функции текущую вершину дерева и она выполняет вызов от одного из своих сыновей, который содержит элемент с данным индексом. Пересчитывает суммы и доходит до листа, которому присваивается новое значение.
Для выполнения запроса суммы также используется рекурсивная функция. Она запускается либо от правого, либо от левого сына текущей вершины, если границы исходного запроса лежат в одном из их отрезков. Либо запускается от обоих сыновей, если границы исходного запроса принадлежат пересечению их отрезков, суммируя результаты двух запросов. Таким образом функция доходит до отрезка, границы которого совпадают с текущим запросом или до листа и возвращает их значение.
Для решения данной задачи были использованы материалы сайта e-maxx.ru.
Первая же ссылка не туда.
Спасибо, исправила.