Реализация запроса в дереве отрезков сверху
Версия от 22:23, 16 мая 2011; 192.168.0.2 (обсуждение)
Содержание
Алгоритм
Будем рассматривать запрос на примере задачи 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); }