Часть 1 ( из 3). RSQ, RMQ, Segment Tree, Дерево Отрезков. LevelB1+B2-06-01-2021
Описание
Рассмотрели задачу RMQ - Дерево Отрезков. На первом занятии этой темы разбирались, как построить Дерево Отрезков, выясняли волшебные свойства массива Tree, перенесли дерево на рисунке в программу. В Дереве отрезков получаются номера связанных значений, диапазоны отрезков и на обратной ветке вычисляются суммы на отрезках.
Для примера можете попробовать сдать на 100 баллов задачу №6959 Запрос Суммы на Отрезке с сайта e-olymp.com
https://www.e-olymp.com/ru/problems/6959
Комментарии