Всем привет, у клавиатуры Кодер Арсений. Не так давно я узнал о прекрасной альтернативе префиксному массиву - дерево отрезков. Сегодня именно о нём и пойдёт речь. Теория Картинки взяты со статьи на Хабре. Как и сам массив. Приведу простую задачу, с помощью которой чаще всего объясняется дерево отрезков. У нас есть массив чисел, затем вводится огромное количество запросов l, r. Задача в ответ на каждый запрос вывести сумму чисел на подотрезке [l:r]...

Задача из раздела комбинаторика, но на мой взгляд - это в чистом виде динамическое программирование. Давайте разбираться: Давайте посмотрим на последний ряд дерева. Понятно, что все листья разбиваются на группы по 2 или 3. Научимся считать количество разбиений методом динамического программирования. База динамики: 2, 3 и 4 элемента разбиваются единственным способом. Шаг динамики, если все ответы до i элементов посчитаны: какой могла быть последняя группа? Всё те же 2 или 3 элемента, то есть ответ для задачи размера i складывается из ответов для подзадач размера i - 2 и i - 3...