Сегментно дърво

В информатиката сегментното дърво е структура от данни за съхранение на интервали или сегменти. То позволява да се разбере кои от запазените интервали съдържат дадена точка. Поначало сегментното дърво е статична структура, тоест съдържанието му не може да се променя, след като дървото е построено. Друга подобна структура от данни е интервалното дърво.

Сегментното дърво на множеството I от n интервала използва количество памет O(n log n) и може да се построи за време O(n log n). То позволява да се намерят всички интервали, които съдържат дадена точка за време O(k + log n), където k е броят на сегментите.

Сегментното дърво се прилага в геометричните алгоритми и в геоинформационните системи.

Тази страница частично или изцяло представлява превод на страницата Segment tree в Уикипедия на английски. Оригиналният текст, както и този превод, са защитени от Лиценза „Криейтив Комънс – Признание – Споделяне на споделеното“, а за съдържание, създадено преди юни 2009 година – от Лиценза за свободна документация на ГНУ. Прегледайте историята на редакциите на оригиналната страница, както и на преводната страница, за да видите списъка на съавторите. ​ ВАЖНО: Този шаблон се отнася единствено до авторските права върху съдържанието на статията. Добавянето му не отменя изискването да се посочват конкретни източници на твърденията, които да бъдат благонадеждни.​