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

Текущая версия от 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]);
    }
};

Ссылки

Теория:

Код:

Задачи:

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

@@ Строка 1: / Строка 1: @@
   class SparseTable {
-      int lg[100010], st[20][100010];
+      vector<int> lg;
+     vector<vector<int>> st;
   public:
-      SparseTable(int a[], int size) {
+      SparseTable(vector<int> &a) {
-          for (int i = 0; i <= size; i++)
+         lg.resize(a.size() + 1);
-              lg[i] = (i > 1 ? lg[i / 2] + 1 : 0);
+          for (int i = 2; i <= a.size(); i++)
-          for (int p = 0; (1 << p) <= size; p++) {
+              lg[i] = lg[i / 2] + 1;
-              for (int i = 0; i + (1 << p) <= size; i++)
-                  st[p][i] = (p ? min(st[p - 1][i], st[p - 1][i + (1 << p - 1)]) : a[i]);
+         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 p = lg[r - l + 1];
+          int level = lg[r - l + 1], levelWidth = 1 << level;
-          return min(st[p][l], st[p][r - (1 << p) + 1]);
+          return min(st[level][l], st[level][r - levelWidth + 1]);
       }
   };
-== Ссылки на задачи ==
-* [http://codeforces.ru/gym/100093/problem/E Codeforces #100093.E &mdash; Разреженные таблицы] (Базовая реализация)
-* [http://codeforces.ru/gym/100255/problem/A Codeforces #100255.A &mdash; Грибы] (Базовая реализация)
 == Ссылки ==
@@ Строка 24: / Строка 27: @@
 * [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 с помощью разреженной таблицы]
+* [https://algorithmica.org/ru/sparse-table algorithmica.org — Sparse table]
 * [http://codeforces.com/blog/entry/45485 Codeforces — 2D Range minimum Query in O(1)]
 Код:
-* [https://github.com/indy256/codelibrary/blob/master/java/structures/RmqSparseTable.java CodeLibrary &mdash; RMQ: Sparse Table]
+* [http://github.com/indy256/codelibrary/blob/master/java/structures/RmqSparseTable.java CodeLibrary &mdash; RMQ: Sparse Table]
 * [http://github.com/ADJA/algos/blob/master/DataStructures/SparseTable.cpp Algos &mdash; Sparse table]
 Задачи:
 * [http://informatics.mccme.ru/course/view.php?id=18 informatics.mccme.ru &mdash; Курс &laquo;Структуры данных&raquo; &mdash; часть 10]
+* [http://codeforces.ru/gym/100093/problem/E Codeforces #100093.E &mdash; Разреженные таблицы] (Базовая реализация)
+* [http://codeforces.ru/gym/100255/problem/A Codeforces #100255.A &mdash; Грибы] (Базовая реализация)
 [[Category:Структуры данных для задач RSQ/RMQ]]

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

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

Ссылки

Навигация

Поиск