Изменения
→Алгоритм
==Алгоритм==
Будем рассматривать запрос на примере задачи RSQ(запрос суммы)
[[Файл:Презентация1.jpg|right|380px|thumb|Пример дерева отрезков для вычисления сумм]]
Обработка запроса суммы представляет собой рекурсивную функцию, которая всякий раз вызывает себя либо от левого сына, либо от правого (не изменяя границы запроса в обоих случаях), либо от обоих сразу (при этом деля наш запрос на два соответствующих подзапроса). Однако рекурсивные вызовы будем делать не всегда: если текущий запрос совпал с границами отрезка в текущей вершине дерева отрезков, то в качестве ответа будем возвращать предвычисленное значение суммы на этом отрезке, записанное в дереве отрезков.
==Реализация==
