Задача RMQ — 1. Static RMQ

[SkyKos]

Снизить сложность с n^3 до n^2 можно используя следующее предположение: раз мы знаем экстремум на отрезке [i,j] — то для определения экстремума на отрезке [i,j+1] достаточно сравнить минимум/максимум на [i,j] с элементом j+1, вместо того, что б искать его на всем интервале [i,j+1]?

[Zlobober]

Да, конечно.

[SkyKos]

Спасибо за интересную статью!

[Zlobober]

Не за что. Дальше будет ещё интереснее, здесь пока были основы.

[gasya]

Ну что, Макс, осилим всю программу ЛКШ на двоих? =)

[Skiminok]

Да ладно, оставьте всем алгоритмистам Хабра что-нибудь интересненькое на рассказ :)

[Zlobober]

Осилим. Я ещё летом делал попытку так оказаться на хабре. Однако с точно такой же статьёй тогда ничего не вышло, видимо, все интересующиеся люди отдыхали.

Я когда гулял по разделу алгоритмы, я заметил кучу недописанных топиков типа «Декартовы деревья, часть 1», которые тоже обещались быть завершёнными. Надо бы исправить ситуацию :)

[Skiminok]

Насчет декартовых деревьев: там завершать-то оставалось только функциональную реализацию, которая не всем интересна и в принципе к алгоритмистике не относится (разве что пропагандирует персистентные структуры данных, но на это можно и отдельный цикл статей выделить).

[Zlobober]

Ну да, неудачный пример.
В любом случае, есть много интересных тем, которые можно рассмотреть.
Была ещё идея рассказать про суффиксные структуры (массив, автомат, дерево), но нахрапом написать о ком-нибудь из них меня не хватило.

[Skiminok]

Нееее, статью о суффиксном массиве я вынашиваю уже много месяцев, не советую отбирать у меня этот хлеб, это же давно заметная мечта, там столько классного описать-то можно… :)

[Zlobober]

Хорошо, хорошо :)
В любом случае, у меня ещё много сюжетов, о которых можно рассказать. Так сказать, несём алгоритмы в массы.

[Skiminok]

Да, кстати, насчет сюжетов.
О RMQ-цикле я уже понял, а что еще вы планируете (и напишете), чтобы я зря не продумывал наперед?

У меня просто подготовка одной серьезной статьи вроде «Декартового дерева» — с иллюстрациями, исходниками, большим количеством красиво отформатированного текста — занимает довольно продолжительное время, минимум полдня. Не хотелось бы тратить его зря, если материал пересекается :)

[Zlobober]

Я пока не знаю. Я думал завершить этот цикл и уже дальше размышлять на эту тему. Лучше вы скажите, что это у вас за статья :)
А ещё давайте перенесём диалог в личку, всё-таки оффтопик.

[Zlobober]

Вы меня раскрыли :) а то негоже, что на хабре тусуется так много программистов, не умеющих даже кучу написать.

[Nostr]

В рисунке Sparse Table случайно при k=1 не должно быть 364225001 вместо 364235001

[Zlobober]

Да, тройке там взяться, конечно, неоткуда. Я поправлю, когда буду переносить на другой хостинг все картинки.

[tagir_valeev]

Спасибо, может в жизни пригодиться. Я такую задачу как-то оптимизировал по-другому (сам велосипед изобрёл): разбил множество из n элементов примерно на sqrt(n) блоков примерно одинаковой длины, посчитал и сохранил минимум для каждого из них, а в онлайн-задаче брал минимумы целых блоков, вошедших в диапазон, и дополнял элементами, не составившими целый блок. Получается вроде (O(n), O(n^(1/2)) и O(n^(1/2)) дополнительной памяти помимо самого массива. Описанный здесь метод, конечно, красивее :-)

[0leGG]

Ага. Если знать структуру запросов, то и ваш «велосипед» сносен. Только сразу придумывается, как специально подобранными запросами всё сведётся к полному перебору по отрезкам длины 2*(n^(1/2) — 1).

[gasya]

Такая структура данных гарантирует ответ на запрос за O(n^1/2). Ваш пример с отрезками длины 2*(n^1/2 — 1) никак не противоречит этой оценке.

[kirilloid]

Эээ, а почему тогда было не написать кэш по типу mipmapping, чтобы выполнять запросы за O(log(n))?

[Zlobober]

Да, понятно, что копая в направлении различных логарифмических структур, можно что-то придумать. По сути, что-то похожее и происходит в дереве отрезков, топик про который я уже написал.

[kirilloid]

Да там и придумывать-то особо ничего не надо.
Можно вообще всё просто в один массив запихать. На нечётных индексах расположить сами значения элементов, а на чётных натыкать между ними дерево кэша.

Читаем числа и строим кэш (гнался за минимизацией 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

[Zlobober]

У вас то же самое дерево отрезков просто по-другому уложено в массив.

[kirilloid]

Ну да, частный случай.
Кстати, вам бы в статье тоже код можно было бы написать.

[Zlobober]

Ну, sparse table это совсем простая штука, а в дальнейших постах код я прилагаю.

[vad4]

Лирическое отступление. Заметим, что в качестве основания логарифма можно брать любое число, т.к. log_an всегда отличается от log_bc ровно в константное число раз. Константа, как мы помним из курса школьной алгебры равна log_ab.

Наверно имелось ввиду log_bn вместо log_bc?

[Zlobober]

Да, тоже верно. Спасибо.