|
|
| Строка 1: |
Строка 1: |
| | {{Определение | | {{Определение |
| − | |definition= '''Дерево отрезков''' {{---}} это структура данных, которая позволяет за асимптотику <tex>O(\log n)</tex> реализовать операции следующего вида: нахождение суммы (задача RSQ), минимума или максимума (задача RMQ) элементов массива в заданном отрезке (<tex>a[i...j]</tex>, где <tex>i</tex> и <tex>j</tex> поступают на вход алгоритма).}}При этом дополнительно возможно изменение элементов массива: как изменение значения одного элемента, так и изменение элементов на целом подотрезке массива, т.е. разрешается присвоить всем элементам <tex>a[i...j]</tex> какое-либо значение, либо прибавить ко всем элементам массива какое-либо число. Структура занимает <tex>O(n)</tex> памяти и выстраивается из массива за <tex>O(n)</tex>.
| |
| | | | |
| | ==Алгоритм== | | ==Алгоритм== |
Версия 01:18, 4 мая 2011
{{Определение
Алгоритм
Реализация
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 :: Дерево отрезков
- Дерево отрезков — Википедия
