Sparse table

class SparseTable {
    vector<int> lg;
    vector<vector<int>> st;

public:
    SparseTable(vector<int> &a) {
        lg.resize(a.size() + 1);
        for (int i = 2; i <= a.size(); i++)
            lg.push_back(lg[i / 2] + 1);

        st.push_back(a);
        for (int level = 1, levelWidth = 2; levelWidth <= a.size(); level++, levelWidth *= 2) {
            st.emplace_back();
            for (int i = 0; i + (1 << level) <= a.size(); i++)
                st[level].push_back(min(st[level - 1][i], st[level - 1][i + levelWidth / 2]));
        }
    }

    int getMin(int l, int r) {
        int level = lg[r - l + 1], levelWidth = 1 << level;
        return min(st[level][l], st[level][r - levelWidth + 1]);
    }
};

Ссылки

Теория:

• adilet.org — Sparse Table
• neerc.ifmo.ru/wiki — Решение RMQ с помощью разреженной таблицы
• algorithmica.org — Sparse table
• Codeforces — 2D Range minimum Query in O(1)

Код:

• CodeLibrary — RMQ: Sparse Table
• Algos — Sparse table

Задачи:

• informatics.mccme.ru — Курс «Структуры данных» — часть 10
• Codeforces #100093.E — Разреженные таблицы (Базовая реализация)
• Codeforces #100255.A — Грибы (Базовая реализация)