Sparse table: различия между версиями

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
 
(не показаны 4 промежуточные версии этого же участника)
Строка 5: Строка 5:
  public:
  public:
     SparseTable(vector<int> &a) {
     SparseTable(vector<int> &a) {
         lg.push_back(0);
         lg.resize(a.size() + 1);
         for (int i = 1; i <= a.size(); i++)
         for (int i = 2; i <= a.size(); i++)
             lg.push_back(lg[i / 2] + 1);
             lg[i] = lg[i / 2] + 1;
   
   
         st.push_back(a);
         st.push_back(a);
         for (int level = 1, levelWidth = 2; levelWidth <= a.size(); level++, levelWidth *= 2) {
         for (int level = 1, levelWidth = 2; levelWidth <= a.size(); level++, levelWidth *= 2) {
             st.emplace_back();
             st.emplace_back();
             for (int i = 0; i + (1 << level) <= a.size(); i++)
             for (int i = 0; i + levelWidth <= a.size(); i++)
                 st[level].push_back(min(st[level - 1][i], st[level - 1][i + levelWidth / 2]));
                 st[level].push_back(min(st[level - 1][i], st[level - 1][i + levelWidth / 2]));
         }
         }
Строка 27: Строка 27:
* [http://adilet.org/blog/sparse-table/ adilet.org — Sparse Table]
* [http://adilet.org/blog/sparse-table/ adilet.org — Sparse Table]
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%A0%D0%B5%D1%88%D0%B5%D0%BD%D0%B8%D0%B5_RMQ_%D1%81_%D0%BF%D0%BE%D0%BC%D0%BE%D1%89%D1%8C%D1%8E_%D1%80%D0%B0%D0%B7%D1%80%D0%B5%D0%B6%D0%B5%D0%BD%D0%BD%D0%BE%D0%B9_%D1%82%D0%B0%D0%B1%D0%BB%D0%B8%D1%86%D1%8B neerc.ifmo.ru/wiki &mdash; Решение RMQ с помощью разреженной таблицы]
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%A0%D0%B5%D1%88%D0%B5%D0%BD%D0%B8%D0%B5_RMQ_%D1%81_%D0%BF%D0%BE%D0%BC%D0%BE%D1%89%D1%8C%D1%8E_%D1%80%D0%B0%D0%B7%D1%80%D0%B5%D0%B6%D0%B5%D0%BD%D0%BD%D0%BE%D0%B9_%D1%82%D0%B0%D0%B1%D0%BB%D0%B8%D1%86%D1%8B neerc.ifmo.ru/wiki &mdash; Решение RMQ с помощью разреженной таблицы]
* [https://algorithmica.org/ru/sparse-table algorithmica.org — Sparse table]
* [http://codeforces.com/blog/entry/45485 Codeforces — 2D Range minimum Query in O(1)]
* [http://codeforces.com/blog/entry/45485 Codeforces — 2D Range minimum Query in O(1)]
Код:
Код:

Текущая версия от 00:34, 18 мая 2023

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[i] = 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 + levelWidth <= 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]);
    }
};

Ссылки

Теория:

Код:

Задачи: