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

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
Нет описания правки
Строка 12: Строка 12:
     int getMin(int l, int r) {
     int getMin(int l, int r) {
         int p = lg[r - l + 1];
         int p = lg[r - l + 1];
         return min(t[p][l], t[p][r - (1 << p) + 1]);
         return min(st[p][l], st[p][r - (1 << p) + 1]);
     }
     }
  };
  };

Версия от 20:28, 8 июня 2016

class SparseTable {
    int lg[100010], st[20][100010];
public:
    SparseTable(int a[], int size) {
        for (int i = 0; i <= size; i++)
            lg[i] = (i > 1 ? lg[i / 2] + 1 : 0);
        for (int p = 0; (1 << p) <= size; p++) {
            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]);
        }
    }
    int getMin(int l, int r) {
        int p = lg[r - l + 1];
        return min(st[p][l], st[p][r - (1 << p) + 1]);
    }
};

Ссылки на задачи

Ссылки