Реализация запроса в дереве отрезков сверху — различия между версиями
(→Реализация) |
(→Алгоритм) |
||
| Строка 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);
}
