Реализация запроса в дереве отрезков сверху — различия между версиями
(Новая страница: «{{Определение |definition= '''Дерево отрезков''' {{---}} это структура данных, которая позволяет за ас…») |
(→Реализация) |
||
| Строка 5: | Строка 5: | ||
==Реализация== | ==Реализация== | ||
| − | + | 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); | ||
| + | } | ||
==Ссылки== | ==Ссылки== | ||
Версия 01:06, 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); }
