LINUX.ORG.RU

Насколько часто используются segment(interval) trees в программировании

 ,


0

2

Насколько часто segment trees/interval trees и запросы по ним используются в коммерческом программировании, в open source проектах и на каких языках программирования чаще всего?

На англоязычных форумах пишут, что segment trees/interval trees (рекурсивный или нерекурсивный подход) достаточно популярны в соревнованиях по программированию.

А как обстоят дела на практике, которая, возможно, имеет мало общего со спортивным программированием?

Перемещено maxcom из general

Я пишу код чуть больше 10 лет. Про «segment trees/interval trees» слышу впервые. Это, разумеется, не значит что я никогда их не использовал: я вполне мог дёргать какие-то либы, которые с помощью этих деревьев что-то делают, но точно никогда не использовал эти хрени явно.

ZweiStein ()

Ну что вы как маленький. Когда нужно работать с большими, но разреженными упорядоченными множествами, причем задача определить, принадлежит ли элемент множеству, встречается намного чаще, чем множество менятеся, тогда и используют. Я с год назад использовал в реализации потокового сетевого протокола. Получилось сильно экономнее по памяти и быстрее, чем просто дерево поиска. Вот только я сначала придумал и запрогал эту штуку, а уже на ревью мне сказали, как она называется))

roof ★★ ()