Реализация запроса в дереве отрезков сверху — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «{{Определение |definition= '''Дерево отрезков''' {{---}} это структура данных, которая позволяет за ас…»)
(нет различий)

Версия 01:01, 4 мая 2011

Определение:
Дерево отрезков — это структура данных, которая позволяет за асимптотику [math]O(\log n)[/math] реализовать операции следующего вида: нахождение суммы (задача RSQ), минимума или максимума (задача RMQ) элементов массива в заданном отрезке ([math]a[i...j][/math], где [math]i[/math] и [math]j[/math] поступают на вход алгоритма).

При этом дополнительно возможно изменение элементов массива: как изменение значения одного элемента, так и изменение элементов на целом подотрезке массива, т.е. разрешается присвоить всем элементам [math]a[i...j][/math] какое-либо значение, либо прибавить ко всем элементам массива какое-либо число. Структура занимает [math]O(n)[/math] памяти и выстраивается из массива за [math]O(n)[/math].

Алгоритм

Реализация

Ссылки

- MAXimal :: algo :: Дерево отрезков

- Дерево отрезков — Википедия