Двумерная разреженная таблица для запросов минимума в прямоугольнике
Двумерная разреженная таблица отвечает на запросы минимума на неизменной сетке . Индексы начинаются с , границы запросов включаются.
Элемент хранит минимум в прямоугольнике, начинающемся в , высотой и шириной .
Хранятся только прямоугольники, помещающиеся в сетку.
Начнём с отдельных клеток:
Остальные элементы строим в два шага:
На каждом шаге берём минимум из двух половин.
Пусть и — левый верхний и правый нижний углы. Высота и ширина запроса равны
Выберем наибольшие степени двойки, помещающиеся в эти размеры:
Используем четыре блока , по одному в каждом углу запроса. Пусть
Блоки начинаются в
Поскольку , верхние и нижние блоки покрывают все строки запроса. Аналогично, , поэтому левые и правые блоки покрывают все столбцы запроса. Вместе четыре блока покрывают весь прямоугольник.
Блоки могут пересекаться, но повторение клеток не меняет минимум. Прочитаем четыре минимума и возьмём минимум из этих значений.
Есть уровней по высоте и уровней по ширине. Предобработка и используемая память составляют
Каждый запрос занимает времени.
Глобальные массивы резервируют место под максимально допустимый размер сетки. Одна только таблица занимает около МиБ.
Сетка не меняется после предобработки.
#include <bits/stdc++.h>
using namespace std;
const int N = 301;
const int K = 9;
int n, m, lg[N];
long long a[N][N], t[K][K][N][N];
void build() {
for (int i = 2; i <= max(n, m); i++) {
lg[i] = lg[i / 2] + 1;
}
for (int x = 1; x <= n; x++) {
for (int y = 1; y <= m; y++) {
t[0][0][x][y] = a[x][y];
}
}
for (int ky = 1; ky <= lg[m]; ky++) {
int w = 1 << ky;
for (int x = 1; x <= n; x++) {
for (int y = 1; y + w - 1 <= m; y++) {
t[0][ky][x][y] = min(t[0][ky - 1][x][y],
t[0][ky - 1][x][y + w / 2]);
}
}
}
for (int kx = 1; kx <= lg[n]; kx++) {
int h = 1 << kx;
for (int ky = 0; ky <= lg[m]; ky++) {
int w = 1 << ky;
for (int x = 1; x + h - 1 <= n; x++) {
for (int y = 1; y + w - 1 <= m; y++) {
t[kx][ky][x][y] = min(t[kx - 1][ky][x][y],
t[kx - 1][ky][x + h / 2][y]);
}
}
}
}
}
long long get(int x1, int y1, int x2, int y2) {
int kx = lg[x2 - x1 + 1];
int ky = lg[y2 - y1 + 1];
int x = x2 - (1 << kx) + 1;
int y = y2 - (1 << ky) + 1;
return min({t[kx][ky][x1][y1], t[kx][ky][x1][y],
t[kx][ky][x][y1], t[kx][ky][x][y]});
}