Разреженная таблица без пересечений
Для ассоциативной операции запрос на отрезке просит вычислить
Двумерная разреженная таблица для запросов минимума в прямоугольнике
Обычная разреженная таблица отвечает на общий ассоциативный запрос за , объединяя непересекающиеся блоки. Её запрос за использует пересекающиеся отрезки и требует, чтобы повторение элементов не меняло результат.
Разреженная таблица без пересечений (disjoint sparse table) объединяет два отрезка без пересечения. Поэтому она работает с любой ассоциативной операцией. Коммутативность не требуется: элементы объединяются в исходном порядке.
Индексы начинаются с , а интервалы запросов включают оба конца.
На уровне разделим массив на блоки длины , начиная с позиции . У блока, начинающегося в , середина равна
Для каждой позиции в левой половине храним суффикс, заканчивающийся в :
Для каждой позиции в правой половине храним префикс, начинающийся в :
Суффиксы строим справа налево, добавляя каждый новый элемент слева. Префиксы строим слева направо, добавляя каждый новый элемент справа. Это сохраняет порядок операции.
Последний блок может быть короче. Обрабатываем только существующие позиции и пропускаем блок, если его правая половина пуста.
Если , вернём .
Иначе пусть — позиция старшего установленного бита в :
Здесь — побитовый XOR.
Все биты выше равны, поэтому и принадлежат одному блоку длины . Их биты с номером различаются. Так как , этот бит равен у и у , то есть они лежат в левой и правой половинах.
На этом уровне покрывает , а покрывает . Эти два отрезка не пересекаются и в точности покрывают запрос. Ответ равен
Сначала объединяем левый суффикс, затем правый префикс.
Каждый уровень обрабатывает элементов, а уровней . Предобработка занимает времени, а каждый запрос — времени.
Таблица использует элементов; глобальные массивы резервируют место под максимально допустимый размер. Эти оценки предполагают, что каждое хранимое значение занимает памяти, а объединение двух значений занимает времени.
Массив не меняется после предобработки.
#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
const int K = 20;
const int MOD = 1000;
int n;
long long a[N], t[K][N];
long long op(long long x, long long y) {
return x * y % MOD;
}
void build() {
for (int k = 0; (1 << k) < n; k++) {
int b = 1 << k;
for (int l = 0; l < n; l += 2 * b) {
int m = min(l + b, n);
int r = min(l + 2 * b, n);
if (m == r) continue;
t[k][m - 1] = a[m - 1];
for (int i = m - 2; i >= l; i--) {
t[k][i] = op(a[i], t[k][i + 1]);
}
t[k][m] = a[m];
for (int i = m + 1; i < r; i++) {
t[k][i] = op(t[k][i - 1], a[i]);
}
}
}
}
long long get(int l, int r) {
if (l == r) return a[l];
int k = 31 - __builtin_clz((unsigned int)(l ^ r));
return op(t[k][l], t[k][r]);
}