Многомерное дерево отрезков — различия между версиями
| Строка 1: | Строка 1: | ||
Дерево отрезков можно обобщить в многомерный случай. | Дерево отрезков можно обобщить в многомерный случай. | ||
| − | ===Анализ и оценка структуры | + | ==Пример двумерного дерева== |
| + | |||
| + | ==Анализ и оценка структуры== | ||
Структура использует <tex>О(n*log^{d - 1} n)</tex> памяти, и отвечает на запрос за <tex>O(log^{d} n)</tex>, где <tex>d</tex>-размерность дерева. | Структура использует <tex>О(n*log^{d - 1} n)</tex> памяти, и отвечает на запрос за <tex>O(log^{d} n)</tex>, где <tex>d</tex>-размерность дерева. | ||
Версия 03:58, 14 июня 2011
Дерево отрезков можно обобщить в многомерный случай.
Пример двумерного дерева
Анализ и оценка структуры
Структура использует памяти, и отвечает на запрос за , где -размерность дерева.
