Реализация запроса в дереве отрезков сверху — различия между версиями
(→Реализация) |
(→Реализация) |
||
| Строка 5: | Строка 5: | ||
==Реализация== | ==Реализация== | ||
| − | int sum (int v, int tl, int tr, int l, int r) { | + | <code> |
| − | + | ||
| − | + | 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); | ||
| + | } | ||
| + | </code> | ||
==Ссылки== | ==Ссылки== | ||
Версия 01:18, 4 мая 2011
| Определение: |
| Дерево отрезков — это структура данных, которая позволяет за асимптотику реализовать операции следующего вида: нахождение суммы (задача RSQ), минимума или максимума (задача RMQ) элементов массива в заданном отрезке (, где и поступают на вход алгоритма). |
При этом дополнительно возможно изменение элементов массива: как изменение значения одного элемента, так и изменение элементов на целом подотрезке массива, т.е. разрешается присвоить всем элементам какое-либо значение, либо прибавить ко всем элементам массива какое-либо число. Структура занимает памяти и выстраивается из массива за .
Алгоритм
Реализация
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);
}
