Реализация запроса в дереве отрезков сверху — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Алгоритм)
Строка 1: Строка 1:
{{Определение
 
 
 
==Алгоритм==
 
==Алгоритм==
 
Будем рассматривать запрос на примере задачи RSQ(запрос суммы)
 
Будем рассматривать запрос на примере задачи RSQ(запрос суммы)

Версия 22:07, 5 мая 2011

Алгоритм

Будем рассматривать запрос на примере задачи RSQ(запрос суммы)

Пример дерева отрезков для вычисления сумм

Обработка запроса суммы представляет собой рекурсивную функцию, которая всякий раз вызывает себя либо от левого сына, либо от правого (не изменяя границы запроса в обоих случаях), либо от обоих сразу (при этом деля наш запрос на два соответствующих подзапроса). Однако рекурсивные вызовы будем делать не всегда: если текущий запрос совпал с границами отрезка в текущей вершине дерева отрезков, то в качестве ответа будем возвращать предвычисленное значение суммы на этом отрезке, записанное в дереве отрезков.

Реализация

 int sum (int v, int tl, int tr, int l, int r)
 {
       if (l > r)
           return 0;
       if (l == tl && r == tr)
           return t[v];
       int tm = (tl + tr) / 2;
       return sum (v*2, tl, tm, l, min(r,tm))
           + sum (v*2+1, tm+1, tr, max(l,tm+1), r);
 } 

Ссылки

- MAXimal :: algo :: Дерево отрезков

- Дерево отрезков — Википедия