Sparse table: как правильно предпосчитать log[] и не словить ошибку на границах?
В sparse table для запроса нужен k = floor(log2(len)). Видел два способа: считать через __builtin_clz/std::__lg и через предпосчитанный массив lg[]. Какой брать, и где тут типовые ошибки на границах (len=1, len=0)?
2 ответа
Оба способа корректны, выбор — про скорость и удобство.
Предпосчёт lg[] — самый быстрый в запросе (просто чтение из массива), классика:
int lg[N + 1];
lg[1] = 0;
for (int i = 2; i <= n; ++i) lg[i] = lg[i / 2] + 1;
Здесь lg[i] = floor(log2(i)). Обратите внимание: lg[1] = 0 — база, и цикл идёт с 2. lg[0] не определяем и не используем (длина отрезка всегда ≥ 1).
Через встроенные функции:
int k = std::__lg(len); // floor(log2(len)) для len >= 1
// или: 31 - __builtin_clz(len) // для unsigned/int > 0
std::__lg(len) — то же floor(log2(len)), работает для len >= 1. Для len = 0 поведение не определено — не вызывайте.
Граничные случаи: len = 1 → k = 0, запрос min(sp[0][l], sp[0][l]) — корректно. len = 0 (l > r) — такого запроса быть не должно, проверяйте на входе или возвращайте нейтраль до вызова. Рекомендация: на контесте — предпосчёт lg[], он надёжнее и не зависит от компилятора.
Частая грабля — размер массива lg[]. Он должен быть как минимум n + 1, потому что максимальная длина отрезка равна n, и вы обращаетесь к lg[r - l + 1] вплоть до lg[n]. Заведёте lg[n] (без +1) — выход за границу при запросе на весь массив.
Вторая грабля — размер второго измерения sparse table: LOG должно быть floor(log2(n)) + 1, иначе при j-цикле вылезете. Берите LOG = 20 для n до 10^6 (2^20 ≈ 10^6) или вычисляйте __lg(n) + 1.
И про __builtin_clz: он не определён для аргумента 0, и работает с unsigned int. Если len может быть результатом вычитания, где случайно получился 0 или отрицательное — будет мусор. Предпосчитанный lg[] от этого свободен, ещё один аргумент в его пользу для надёжного кода на контесте.