Комментарии 4
Ым... Может быть надо бы расширить немного вводную часть, чтобы было понятно, о чем идет речь?
"Многие знакомы с алгоритмами дерева отрезков"? Да, многие действительно знакомы с весьма распространенной и полезной хрестоматийной структурой данных - деревом отрезков (aka interval tree) - и сопутствующими алгоритмами, использующимися для решения таких задач как эффективное обнаружение перекрывающихся интервалов, попадания точки в набор интервалов и т.п.
Какое отношение ко всему этому имеют ваши рассуждения - тайна за семью печатями. "Дерево отрезков похоже на корневую декомпозицию"... Оок....
"Собственно код на С (подключенным для удобства STL)"? Чего? STL в С?
По поводу первых двух абзацев. Подразумевается. что вы понимаете, что такое дерево отрезков, кроме того на статье стоит тег "спортивное программирование", то есть подразумевается то, что нужно/можно погуглить "дерево отрезков спортивное программирование", если у вас возникли сомнения... Кроме того, буквально после введения, которое нужно чисто для понимания того, откуда идея возникла, идёт прямая постановка задачи, которую я решаю, что сужает круг "поиска" до 1 конкретного алгоритма.
Про "Дерево отрезков похоже на корневую декомпозицию", да, это некоторое не совсем корректное сравнение, которое мне показалось забавным, поэтому оно и находится в "неформальной части" статьи, но могу добавить "рекурсивная корневая" чтобы было понятнее, что я имею ввиду.
Последнее поправил, хотя кажется понятно что я подразумаевал под этим, просто неаккуратно выразился.
Кроме того, я считаю ваш ответ достаточно агрессивным, не очень понимаю чем это вызвано, возможно, я ошибаюсь(
P.S. по итогу я не очень понял что именно мне следует добавить в введение, опять же статья расчитана на людей которые сталкивались и активно использовали дерево отрзков (https://neerc.ifmo.ru/wiki/index.php?title=Дерево_отрезков._Построение)
upd: если вбить запрос "дерево отрезков", то первые пять ссылок будут о нужном в статье дереве отрезков, так что претензия что "непонятно что за дерево" мне кажется вообще не справедливой
В моих экспериментах (несколько лет назад) никогда не получалось заставить работать подобную структуру быстрее аккуратно написанного "китайского дерева отрезков" (https://codeforces.com/blog/entry/18051), более того, есть версии ДО, которые ещё сильнее оптимизированы с помощью SIMD инструкций (https://codeforces.com/blog/entry/89399).
Оптимизируем дерево отрезков, делаем из него куст o_O