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

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

Версия 20:27, 16 мая 2011

Алгоритм

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

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

Если запрашиваемый отрезок не пересекается с рассматриваемым отрезком возвращаем нейтральный элемент. Если запрашиваемый отрезок является подмножеством рассматриваемого возвращаем значение в вершине. Иначе считаем для подотрезков рекурсивно, комбинируем ответ и возвращаем значение.

Реализация

 int sum (int v, int tl, int tr, int l, int r)
 {
       if ([l,r] не пересекается с [tl, tr])
           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 :: Дерево отрезков

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