Сегментно дърво на английски
Очевидно все ощеСегментни дървета. Доказателство. Статията е същата, но трябва да превъртите малко по-надолу.
Ако не съм овен, то на български сегментно дърво се нарича малко по-различно - когато можеш да отговориш на въпроса "колко интервала покрива дадена точка." Това е специален случай на това, което описахте, където единствената разрешена операция е добавянето на единица към интервала.
Ясно е, че алгоритъмът може да бъде разширен до всеки асоциативен оператор.
В тази форма (отговаряща само на въпроса колко сегмента пресичат точка), това се нарича на английски интервално дърво.
Хм, трябва да спя през нощта и да не пълзя в интернет%)
UPD: И ако Wikipedia замени абстрактнитеpiс човешки половини на цели числа и не съхранява боклуци във възли, тогава ще излезе.
UPD2: В и бележката в уикито по тази тема е:
друг плюс на сегментното дърво е, че може лесно да се адаптира към преброяване на заявки; т.е. докладвайте броя на сегментите, съдържащи дадена точка, вместо да докладвате самите сегменти. Вместо да се съхраняват интервалите в каноничните подмножества, може просто да се съхранява цяло число, представляващо тяхната сума. Такова сегментно дърво използва линейно съхранение и изисква O(log n) време за заявка, така че е оптимално.
Пренаписах статията за сегментното дърво.
Опитах се да обхвана всички познати ми приложения. Статията е в алфа версия, така че всякакви коментари са добре дошли. Особено искам да чуя за онези приложения на сегментното дърво, които забравих да спомена.
И да, малко по-късно ще сложа съдържание на статията, иначе е лесно да се изгубите в него - тук стандартните h1/h2/h3 не работят добре :)