Sparse table: различия между версиями
Перейти к навигации
Перейти к поиску
Ctrlalt (обсуждение | вклад) |
Ctrlalt (обсуждение | вклад) Нет описания правки |
||
| Строка 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( | 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]);
}
};
Ссылки на задачи
- Codeforces #100093.E — Разреженные таблицы (Базовая реализация)
- Codeforces #100255.A — Грибы (Базовая реализация)