Comments 29
Снизить сложность с n^3 до n^2 можно используя следующее предположение: раз мы знаем экстремум на отрезке [i,j] — то для определения экстремума на отрезке [i,j+1] достаточно сравнить минимум/максимум на [i,j] с элементом j+1, вместо того, что б искать его на всем интервале [i,j+1]?
Ну что, Макс, осилим всю программу ЛКШ на двоих? =)
Да ладно, оставьте всем алгоритмистам Хабра что-нибудь интересненькое на рассказ :)
Осилим. Я ещё летом делал попытку так оказаться на хабре. Однако с точно такой же статьёй тогда ничего не вышло, видимо, все интересующиеся люди отдыхали.
Я когда гулял по разделу алгоритмы, я заметил кучу недописанных топиков типа «Декартовы деревья, часть 1», которые тоже обещались быть завершёнными. Надо бы исправить ситуацию :)
Я когда гулял по разделу алгоритмы, я заметил кучу недописанных топиков типа «Декартовы деревья, часть 1», которые тоже обещались быть завершёнными. Надо бы исправить ситуацию :)
Насчет декартовых деревьев: там завершать-то оставалось только функциональную реализацию, которая не всем интересна и в принципе к алгоритмистике не относится (разве что пропагандирует персистентные структуры данных, но на это можно и отдельный цикл статей выделить).
Ну да, неудачный пример.
В любом случае, есть много интересных тем, которые можно рассмотреть.
Была ещё идея рассказать про суффиксные структуры (массив, автомат, дерево), но нахрапом написать о ком-нибудь из них меня не хватило.
В любом случае, есть много интересных тем, которые можно рассмотреть.
Была ещё идея рассказать про суффиксные структуры (массив, автомат, дерево), но нахрапом написать о ком-нибудь из них меня не хватило.
Нееее, статью о суффиксном массиве я вынашиваю уже много месяцев, не советую отбирать у меня этот хлеб, это же давно заметная мечта, там столько классного описать-то можно… :)
Хорошо, хорошо :)
В любом случае, у меня ещё много сюжетов, о которых можно рассказать. Так сказать, несём алгоритмы в массы.
В любом случае, у меня ещё много сюжетов, о которых можно рассказать. Так сказать, несём алгоритмы в массы.
Да, кстати, насчет сюжетов.
О RMQ-цикле я уже понял, а что еще вы планируете (и напишете), чтобы я зря не продумывал наперед?
У меня просто подготовка одной серьезной статьи вроде «Декартового дерева» — с иллюстрациями, исходниками, большим количеством красиво отформатированного текста — занимает довольно продолжительное время, минимум полдня. Не хотелось бы тратить его зря, если материал пересекается :)
О RMQ-цикле я уже понял, а что еще вы планируете (и напишете), чтобы я зря не продумывал наперед?
У меня просто подготовка одной серьезной статьи вроде «Декартового дерева» — с иллюстрациями, исходниками, большим количеством красиво отформатированного текста — занимает довольно продолжительное время, минимум полдня. Не хотелось бы тратить его зря, если материал пересекается :)
В рисунке Sparse Table случайно при k=1 не должно быть 364225001 вместо 364235001
Спасибо, может в жизни пригодиться. Я такую задачу как-то оптимизировал по-другому (сам велосипед изобрёл): разбил множество из n элементов примерно на sqrt(n) блоков примерно одинаковой длины, посчитал и сохранил минимум для каждого из них, а в онлайн-задаче брал минимумы целых блоков, вошедших в диапазон, и дополнял элементами, не составившими целый блок. Получается вроде (O(n), O(n^(1/2)) и O(n^(1/2)) дополнительной памяти помимо самого массива. Описанный здесь метод, конечно, красивее :-)
UFO just landed and posted this here
Ага. Если знать структуру запросов, то и ваш «велосипед» сносен. Только сразу придумывается, как специально подобранными запросами всё сведётся к полному перебору по отрезкам длины 2*(n^(1/2) — 1).
Такая структура данных гарантирует ответ на запрос за O(n1/2). Ваш пример с отрезками длины 2*(n1/2 — 1) никак не противоречит этой оценке.
Эээ, а почему тогда было не написать кэш по типу mipmapping, чтобы выполнять запросы за O(log(n))?
Да, понятно, что копая в направлении различных логарифмических структур, можно что-то придумать. По сути, что-то похожее и происходит в дереве отрезков, топик про который я уже написал.
Да там и придумывать-то особо ничего не надо.
Можно вообще всё просто в один массив запихать. На нечётных индексах расположить сами значения элементов, а на чётных натыкать между ними дерево кэша.
Читаем числа и строим кэш (гнался за минимизацией CM, поэтому массив тупо добивается до кратного 2^n)
ищем минимум на отрезке по двум введённым индексам
Копипаста моего решения четырёхлетней давности этой задачи:
acm.mipt.ru/judge/problems.pl?problem=105
Можно вообще всё просто в один массив запихать. На нечётных индексах расположить сами значения элементов, а на чётных натыкать между ними дерево кэша.
Читаем числа и строим кэш (гнался за минимизацией CM, поэтому массив тупо добивается до кратного 2^n)
for (k = 1; k < 524288; k += 2)
if (k<N) scanf("%f", &a[k]);
else a[k] = a[k-2];
long s = 2;
while (s < 524288) {
j = s >> 1;
for(k = s; k < 524288; k += (s << 1))
a[k] = (a[k - j] < a[k + j]) ? a[k - j] : a[k + j];
s <<= 1;
}
ищем минимум на отрезке по двум введённым индексам
float minf;
void addmin(long z) {
float c = a[(z << 1) + s];
if (c < minf) minf = c;
}
s = 1;
scanf("%ld %ld", &i, &j);
minf = a[(i << 1) + 1];
while (i != j) {
if(i & s) {
addmin(i);
i += s;
}
if(j & s) {
j -= s;
addmin(j);
}
s <<= 1;
}Копипаста моего решения четырёхлетней давности этой задачи:
acm.mipt.ru/judge/problems.pl?problem=105
Лирическое отступление. Заметим, что в качестве основания логарифма можно брать любое число, т.к. logan всегда отличается от logbc ровно в константное число раз. Константа, как мы помним из курса школьной алгебры равна logab.
Наверно имелось ввиду logbn вместо logbc?
Sign up to leave a comment.
Задача RMQ — 1. Static RMQ