Многомерное дерево отрезков — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 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

Дерево отрезков можно обобщить в многомерный случай.

Пример двумерного дерева

Анализ и оценка структуры

Структура использует [math]О(n*log^{d - 1} n)[/math] памяти, и отвечает на запрос за [math]O(log^{d} n)[/math], где [math]d[/math]-размерность дерева.