Обратите внимание на другие наши ресурсы: Youtube | Telegram | VK | Rutube | Dzen | Boosty

Введение

Разреженная таблица (sparse table) - структура данных, которая решает задачу поиска максимума или минимума на отрезке за $О(1)$.

Пример: есть массив $А = [4, 8, 15, 16, 23, 42, 8, 4, 16, 20]$. Нужно найти минимум на отрезке $[2, 7]$. Обозначим индексы границ $L = 2$, $R = 7$.

В статье разобран поиск минимума, то же применимо к поиску максимума.

---

Решение №1

Пройдем циклов while по массиву, с условием $L \le R$. На каждом шаге делаем проверку на минимум, сохраняем его в результирующую переменную, и прибавляем к $L$ один.

Сохранили в минимум 4.

Прошлись по массиву и нашли значение минимума меньше, чем в результирующей переменной.

Сложность решения №1

Пусть $n$ - длина изначального массива, тогда:

1. Поиск минимума/максимума - $О(n)$
2. Препроцесс - $O(1)$
3. Необходимое количество памяти - $О(n)$

---

Решение №2

Если требуется найти минимум на массиве $k$ раз, то необходимо $k$ проходить по массиву и выполнять поиск минимума.

Можно заранее расчитать минимум на каждом отрезке, чтобы находить минимум за $О(1)$. Всего комбинаций отрезков $[L, R]$ в массиве - $n^2$.

Пример использования решения №2: найти минимум на отрезке $[1, 7]$. Обратимся по индексам 1 и 7:

Минимум на отрезке $[1, 7]$ равен 3.

Сложность решения №2

Пусть $n$ - длина изначального массива, тогда:

1. Поиск минимума/максимума - $О(1)$
2. Препроцесс - $O(n^2)$
3. Необходимое количество памяти - $О(n^2/2)$

---

Решение №3

Используем разреженную таблицу, где $n$ - длина изначального массива.

Преимущества разреженной таблицы:

1. Поиск минимума/максимума за $О(1)$
2. Постройка таблицы за $O(n * log_2n)$, где $n$ - размер изначального массива
3. Необходимое количество памяти - $O(n * log_2n)$

Недостатки разреженной таблицы:

1. Поиск суммы очень сложен в реализации, поэтому для него разреженную таблицу не используют
2. Сложнее в реализации, чем проход по массиву и матрица $n^2$
3. Если количество итераций поиска минимума/максимума меньше, чем $log_2n$, то выгоднее использовать обычный проход по массиву

Сложность решения №3

1. Поиск минимума/максимума - $О(1)$
2. Препроцесс - $O(n * log_2(n))$
3. Необходимое количество памяти - $О(n * log_2n)$

---

Построение разреженной таблицы

Идея:

1. Предпосчитаем минимум на каждом отрезке длины 2, 4, 8, 16 ... (то есть длины степени двойки)
2. Каждую следующую длину отрезка найдём из предыдущей, это понизит сложность с $n^2$ до $n * log(n)$

Поиск минимума на отрезке из предыдущих

Пусть $ST$ = разреженная таблица, $i = 0$, изначальный массив или $ST[0] = A$ ($A$ - массив, в котором ищем минимум)

Для $i = 1$, чтобы найти минимум, надо сравнить две ячейки в массиве $i = 0$: ячейку сверху, и которая правее на один.

Для следующей ячейки нужно подвинуть все указатели вправо на один.

В итоге, получили массив для $i = 1$.

---

Для $i = 2$, чтобы найти минимум, надо сравнить две ячейки в массиве $i = 1$: ячейку сверху, и которая правее на две:

Для следующей ячейки нужно подвинуть все указатели вправо на один:

В итоге, получили массив для $i = 2$.

---

Для $i = 3$, чтобы найти минимум, надо сравнить две ячейки в массиве $i = 2$: ячейку сверху, и которая правее на четыре.

Для следующей ячейки нужно подвинуть все указатели вправо на 1.

В итоге, получили массив для $i = 3$.

------ ## Получение минимума на двух ячейках для каждой возможной длины степени двойки

$ST$ - разреженная таблица

$ST[ i ][ j ] = min(ST[ i - 1 ][ j ], ST[ i - 1 ][ j + 2^{i-1} ])$ где $j$ = индекс, по которой итерируемся по массивам, $i$ - индекс массива, который заполняем.

Проверим формулу, например:

1. Минимум в ячейке $ST[1][1] = min(ST[0][1], ST[0] [1 + 2^{1-1} = 1 + 1 = 2])$
2. Минимум в ячейке $ST[2][3] = min(ST[1][3], ST[1] [3 + 2^{2-1} = 3 + 2 = 5])$

Разреженная таблица построена.

Псевдокод функции построения разреженной таблицы

функция построения разреженной таблицы
    Ввод: Изначальный массив А;
    Вывод: Массив массивов ST;
    
    ST <- двумерный массив
    ST[0] = A
    LEN <- размер массива А

    Для каждой строки i = 1, пока i < log2(LEN):
        Для каждого j = 0, пока j+2^i <= LEN:
            добавь к массиву ST[i] величину min(ST[i-1][j], ST[i-1][j + 2^(i-1)])
    вернуть ST

---

Применение разреженной таблицы для поиска минимума

Пример №1

L = 1
R = 4
LEN = 4
где LEN = R - L + 1

$LEN = 4$ означает, что нужно рассматривать промежутки длины четыре (четыре является длиной степени двойки, по которым строилась таблица).

Промежутки длины четыре располагается в $ST$ с индексом $i = 2$. Результат находится в $ST [2][1]$ или в $ST [ log_2LEN ][ L ]$

---

Пример №2

L = 1
R = 7
LEN = 7

В таблице сохранены минимумы на промежутках степени двойки, поэтому необходимо взять минимум на 2 участках таких, чтобы они покрыли всю длину $LEN$.

Сначала нужно определить минимальный размер промежутка (размера степени двойки), который поместится в семь. То есть $i = log_2LEN$, округлённый вниз.

Длина промежутка равна $2^i$, назовём его $SHIFT$.

1. Первый промежуток начинается в $L$ и имеет длину SHIFT, первый промежуток заканчивается в $L + SHIFT$
2. Второй промежуток начинается в $R - SHIFT + 1$ и имеет длину $SHIFT$, заканчивается в $R$

Для двух промежутков обратимся к разреженной таблице и найдём их минимумы, затем получим минимум из найденных минимумов, например: Для $L = 1, R = 7$, $i = log_2LEN = 2$, $SHIFT = 2^i = 2^2 = 4$

Значения на промежутке ищем в разреженной таблице, в нашем случае: $MIN = min ( ST[2] [1] , ST[2] [1 + SHIFT - 1] ) = min ( ST[2] [1] , ST[2] [4] )$.

Формула для общего случая: $min ( ST[i] [L], ST[i] [R - SHIFT + 1])$, где $i = log_2LEN$, $SHIFT = 2^i$ Начало первого промежутка → $L$ Начало второго промежутка → $R - SHIFT + 1$.

Псевдокод поиска минимума

Функция поиска минимума в разреженной таблице
    ввод: Границы поиска L и R, разреженная таблица, 
    которая построена для минимума;
    вывод: минимум на подмассиве [L, R] массива A;

    LEN <- R - L + 1
    i <- log2(LEN), округленная вниз
    результат <- min(ST[i][L], ST[i][R - 2^i + 1])
    вернуть результат

---

Реализация разряженной таблицы

Псевдокод

функция построения разреженной таблицы
    ввод: Изначальный массив А;
    вывод: Массив массивов ST;
    
    ST <- двумерный массив
    ST[0] = A
    LEN <- размер массива А

    Для каждой строки i = 1, пока i < log2(LEN):
        Для каждого j = 0, пока j+2^i <= LEN:
            добавь к массиву ST[i] величину min(ST[i-1][j], ST[i-1][j + 2^(i-1)])
    вернуть ST

Функция поиска минимума в разреженной таблице
    ввод: Границы поиска L и R, разреженная таблица, построенная для минимума;
    вывод: минимум на подмассиве [L, R] массива A;

    LEN <- R - L + 1
    i <- log2(LEN), округленная вниз
    результат <- min(ST[i][L], ST[i][R - 2^i + 1])
    вернуть результат

Реализация на Python

Аннотация:

sparse_table(A) -> создает разреженную таблицу для эффективного поиска минимума на поддиапазоне, где A - входной список чисел

find_min(L, R, ST) -> находит минимальное значение на поддиапазоне [L, R] с использованием разреженной таблицы

def sparse_table(A: list):
    LEN = len(A)
    LOG = floor(log2(LEN))
    ST = []
    for i in range(0, LOG+1):
        ST.append([])
    ST[0] = A
    
    for i in range(1, LOG+1):
        j = 0
        while ((j + (1 << i)) <= LEN):
            ST[i].append(min(ST[i - 1][j], ST[i - 1][j + (1 << (i - 1))]))
            j+=1
    return ST

def find_min(L, R, ST):
    i = floor(log2(R - L + 1));
    return min(ST[i][L], ST[i][R - (1 << i) + 1]);

Олимпиадная реализация на C++

Аннотация:

sparse_table(A) -> создает разреженную таблицу для эффективного поиска минимума на поддиапазоне, где A - входной список чисел

find_min(L, R, ST) -> находит минимальное значение на поддиапазоне [L, R] с использованием разреженной таблицы

vector<vector<int>> sparse_table(vector<int> &A) {
    int LOG = floor(log2(A.size()));
    vector<vector<int>> ST(LOG + 1);
    ST[0] = A;
    for (int i = 1; i <= LOG; i++) {
        for (int j = 0; j + (1 << i) <= A.size(); j++) {
            ST[i].push_back(min(ST[i - 1][j], ST[i - 1][j + (1 << (i - 1))]));
        }
    }
    return ST;
}

int find_min(int L, int R, vector<vector<int>> &ST) {
    int i = floor(log2(R - L + 1));
    return min(ST[i][L], ST[i][R - (1 << i) + 1]);
}

Продуктовая реализация на C++

Аннотация:

SparseTable -> шаблонный класс для создания разреженной таблицы, поддерживающей операции нахождения минимума и максимума на поддиапазонах

buildMinST -> создает разреженную таблицу для эффективного поиска минимума на поддиапазоне

buildMaxST -> создает разреженную таблицу для эффективного поиска максимума на поддиапазоне

findMin -> находит минимальное значение на поддиапазоне `[L, R]` с использованием разреженной таблицы

findMax -> Находит максимальное значение на поддиапазоне `[L, R]` с использованием разреженной таблицы

#pragma once
#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

template <typename TValue>
class SparseTable {
    vector<vector<TValue>> ST;
public:
    void buildMinST(vector<TValue> &A);
    void buildMaxST(vector<TValue> &A);
    TValue findMin(int L, int R);
    TValue findMax(int L, int R);
};

template <typename TValue>
void SparseTable<TValue>::buildMinST(vector<TValue> &A) {
    int LEN = A.size();
    int A_loglen = floor(log2(LEN));
    vector<vector<TValue>> ST(A_loglen + 1);
    ST[0] = A;
    
    for (int i = 1; i <= A_loglen; i++) {
        for (int j = 0; j + (1 << i) <= LEN; j++) {
            int SHIFT = 1 << (i - 1);
            TValue num1 = ST[i - 1][j];
            TValue num2 = ST[i - 1][j + SHIFT];
            TValue temp = min(num1, num2);
            ST[i].push_back(temp);
        }
    }
    
    this->ST = ST;
}

template <typename TValue>
void SparseTable<TValue>::buildMaxST(vector<TValue> &A) {
    int LEN = A.size();
    int A_loglen = floor(log2(LEN));
    vector<vector<TValue>> ST(A_loglen + 1);
    ST[0] = A;
    
    for (int i = 1; i <= A_loglen; i++) {
        for (int j = 0; j + (1 << i) <= LEN; j++) {
            int SHIFT = 1 << (i - 1);
            TValue num1 = ST[i - 1][j];
            TValue num2 = ST[i - 1][j + SHIFT];
            TValue temp = max(num1, num2);
            ST[i].push_back(temp);
        }
    }
    
    this->ST = ST;
}

template <typename TValue>
TValue SparseTable<TValue>::findMin(int L, int R) {
    int LEN = R - L + 1;
    int i = floor(log2(LEN));
    int SHIFT = (1 << i);
    TValue num1 = ST[i][L];
    TValue num2 = ST[i][R - SHIFT + 1];
    TValue res = min(num1, num2);
    return res;
}

template <typename TValue>
TValue SparseTable<TValue>::findMax(int L, int R) {
    int LEN = R - L + 1;
    int i = floor(log2(LEN));
    int SHIFT = (1 << i);
    TValue num1 = ST[i][L];
    TValue num2 = ST[i][R - SHIFT + 1];
    TValue res = max(num1, num2);
    return res;
}