Comments 16
Восхитительная статья.
За ссылки на разные репозитории - отдельное спасибо: даже нашел новые для себя.
В sparse set ещё можно быстро случайный элемент генерировать.
Вы про получение случайного из множества? Там что-то более умное чем взять рандомный элемент на отрезке [0; n)?
Раз уж речь пошла о структурах данных, не могу не поделиться моей любимой структурой данных: дерево отрезков декартовых деревьев.
Это двумерная структура данных, позволяющая делать всякие запросы в прямоугольных областях За O(log^2 n). При этом потребляющая O(n log n) памяти.
По одной координате это дерево отрезков, где каждая вершина — это балансированное бинарное дерево. Обычно декартово, потому что его довольно просто реализовывать, ведь стандартные реализации почти всегда не умеют выполнять всякие хитрые запросы вроде "минимальное значение среди ключей на данном отрезке". А еще оно, как и скиплисты, использует теорию вероятности для балансировки.
В "пополняемом массиве" интересная общая идея, но, по моему, для задачи, которая приводится в пример, лучше подойдет сбалансированное дерево поиска.
Держите задачу, где такая концепция является решением: https://codeforces.com/problemset/problem/342/E?locale=ru : )
Жесть какая-то. Я кроме ужаса за O(n log^2 n) ничего придумать не могу: там обработка всех запросов оффлайн и персистентные балансированные деревья с минимумом в поддереве (для каждого направленного ребра найти множество красных вершин в поддереве, отсортированных по времени добавления. При запросе взять любое соседнее ребро и ему обратное, сделать запрос в деревьях. Построение снизу вверх со слиянием меньшего персистентного дервева в большее соседнее).
Дайте, что ли подсказку — в какую сторону копать и как применять концепцию накапливания изменений?
Можно попробовать каждые 
операций пересчитывать ответ, чтобы отвечать на запрос за единицу, а неучтённые новые запросы (которых до корня) обрабатывать втупую.
Вы имеете ввиду, каждые sqrt(n) новых вершин пересчитать bfs-ом по всему дереву каратчайшие расстояния, и оставшиеся добавленные вершины проверять отдельно?
Мало того, что надо научиться за O(1) отвечать на запросы о расстоянии между двумя вершинами в дереве (это надо online LCM за константу делать — весьма экзотический алгоритм), так еще и работать это все счастье будет за O(n sqrt(n)), что для 10^5 как-то совсем медленно. В мое время такие ограничения подразумевали O(n log n) решение.
Хм… однако там есть разбор задач и именно такой метод и предполагается. Хотя, если учесть что там time limit 5 секунд, то вроде как и должно влезть. А я то думал там что-то хитрое и O(n log n) решение в итоге.
По модифицированному адду в пополняемом массиве
void add(int x) {
b.push_back(x);
if (sqr(size(b)) >= size(a)) {
a += b;
sort(a);
b = vector<int>();
}
}Сортировка после конкатенации здесь - это так себе затея по-моему. Если бОльший массив уже отсортирован - это почти готовый Merge Sort, осталось отсортировать меньший и смёржить. Но за псевдокод сойдёт.
Привлекательные структуры данных