Всем привет, у клавиатуры Кодер Арсений. Не так давно я узнал о прекрасной альтернативе префиксному массиву - дерево отрезков. Сегодня именно о нём и пойдёт речь.
Теория
Картинки взяты со статьи на Хабре. Как и сам массив.
Приведу простую задачу, с помощью которой чаще всего объясняется дерево отрезков. У нас есть массив чисел, затем вводится огромное количество запросов l, r. Задача в ответ на каждый запрос вывести сумму чисел на подотрезке [l:r].
Дан массив чисел a = [2, 3, 7, 6, 5, 4, 2, 8].
Чтобы найти сумму на отрезке, выделенном зелёным, нам нужно сложить 13 и 9.
Чтобы сложить числа на подрезке [3, 7, 6, 5, 4, 2, 8] нам нужно провести несколько другую операцию:
Реализация
Дерево отрезков - это структура данных. Реализуем на Python следующие функции:
- build_tree(a) - она должна строить дерево.
- sum_tree(l, r) - она должна суммировать числа на отрезке l, r.
А на этом всё.
Можете порешать задачи на дерево отрезков:
Простые
Сложные
Спасибо за прочтение