Sparse table - История изменений

Ctrlalt в 00:34, 18 мая 2023

2023-05-18T00:34:36Z

← Предыдущая версия		Версия от 00:34, 18 мая 2023
Строка 12:		Строка 12:
	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]));
	}		}

Ctrlalt в 05:08, 9 октября 2022

2022-10-09T05:08:46Z

← Предыдущая версия		Версия от 05:08, 9 октября 2022
Строка 7:		Строка 7:
	lg.resize(a.size() + 1);		lg.resize(a.size() + 1);
	for (int i = 2; 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);

Ctrlalt в 04:59, 9 октября 2022

2022-10-09T04:59:10Z

← Предыдущая версия		Версия от 04:59, 9 октября 2022
Строка 6:		Строка 6:
	SparseTable(vector<int> &a) {		SparseTable(vector<int> &a) {
	lg.resize(a.size() + 1);		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.push_back(lg[i / 2] + 1);

Ctrlalt в 04:58, 9 октября 2022

2022-10-09T04:58:55Z

← Предыдущая версия		Версия от 04:58, 9 октября 2022
Строка 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 = 1; i <= a.size(); i++)
	lg.push_back(lg[i / 2] + 1);		lg.push_back(lg[i / 2] + 1);

Ctrlalt: /* Ссылки */

2022-05-20T10:09:47Z

Ссылки

← Предыдущая версия		Версия от 10:09, 20 мая 2022
Строка 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 — Решение 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 — Решение 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)]
	Код:		Код:

Ctrlalt в 04:08, 26 декабря 2021

2021-12-26T04:08:30Z

← Предыдущая версия		Версия от 04:08, 26 декабря 2021
Строка 1:		Строка 1:
	class SparseTable {		class SparseTable {
	int lg~~[100010],~~ st~~[20][100010]~~;		vector<int> lg;
			vector<vector<int>> st;

	public:		public:
	SparseTable(int a~~[], int size~~) {		SparseTable(vector<int> &a) {
	for (int i = 0; i <= size; i++)		lg.push_back(0);
	lg~~[i] =~~ (~~i > 1 ?~~ lg[i / 2] + 1 ~~: 0~~);		for (int i = 1; i <= a.size(); i++)
	for (int p = 0; ~~(1 << p)~~ <= size; p++) {		lg.push_back(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 + (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 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 — Разреженные таблицы] (Базовая реализация)
	* [http://codeforces.ru/gym/100255/problem/A Codeforces #100255.A — Грибы] (Базовая реализация)

	== Ссылки ==		== Ссылки ==
Строка 30:		Строка 33:
	Задачи:		Задачи:
	* [http://informatics.mccme.ru/course/view.php?id=18 informatics.mccme.ru — Курс «Структуры данных» — часть 10]		* [http://informatics.mccme.ru/course/view.php?id=18 informatics.mccme.ru — Курс «Структуры данных» — часть 10]
			* [http://codeforces.ru/gym/100093/problem/E Codeforces #100093.E — Разреженные таблицы] (Базовая реализация)
			* [http://codeforces.ru/gym/100255/problem/A Codeforces #100255.A — Грибы] (Базовая реализация)


	[[Category:Структуры данных для задач RSQ/RMQ]]		[[Category:Структуры данных для задач RSQ/RMQ]]

Ctrlalt в 08:09, 2 августа 2019

2019-08-02T08:09:53Z

← Предыдущая версия		Версия от 08:09, 2 августа 2019
Строка 26:		Строка 26:
	* [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)]
	Код:		Код:
	* [~~https~~://github.com/indy256/codelibrary/blob/master/java/structures/RmqSparseTable.java CodeLibrary — RMQ: Sparse Table]		* [http://github.com/indy256/codelibrary/blob/master/java/structures/RmqSparseTable.java CodeLibrary — RMQ: Sparse Table]
	* [http://github.com/ADJA/algos/blob/master/DataStructures/SparseTable.cpp Algos — Sparse table]		* [http://github.com/ADJA/algos/blob/master/DataStructures/SparseTable.cpp Algos — Sparse table]
	Задачи:		Задачи:

Ctrlalt: /* Ссылки */

2019-08-02T08:09:33Z

Ссылки

← Предыдущая версия		Версия от 08:09, 2 августа 2019
Строка 21:		Строка 21:

	== Ссылки ==		== Ссылки ==
			Теория:
	* [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 — Решение 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 — Решение RMQ с помощью разреженной таблицы]
			* [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 — RMQ: Sparse Table]
			* [http://github.com/ADJA/algos/blob/master/DataStructures/SparseTable.cpp Algos — Sparse table]
			Задачи:
	* [http://informatics.mccme.ru/course/view.php?id=18 informatics.mccme.ru — Курс «Структуры данных» — часть 10]		* [http://informatics.mccme.ru/course/view.php?id=18 informatics.mccme.ru — Курс «Структуры данных» — часть 10]
	* [http://github.com/indy256/codelibrary/blob/master/java/src/RmqSparseTable.java CodeLibrary — RMQ: Sparse Table]
	* [http://github.com/ADJA/algos/blob/master/DataStructures/SparseTable.cpp Algos — Sparse table]

	[[Category:Структуры данных для задач RSQ/RMQ]]		[[Category:Структуры данных для задач RSQ/RMQ]]

Ctrlalt в 11:08, 22 апреля 2019

2019-04-22T11:08:45Z

← Предыдущая версия		Версия от 11:08, 22 апреля 2019
Строка 21:		Строка 21:

	== Ссылки ==		== Ссылки ==
			* [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 — Решение 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 — Решение RMQ с помощью разреженной таблицы]
	* [http://informatics.mccme.ru/course/view.php?id=18 informatics.mccme.ru — Курс «Структуры данных» — часть 10]		* [http://informatics.mccme.ru/course/view.php?id=18 informatics.mccme.ru — Курс «Структуры данных» — часть 10]

Ctrlalt в 20:28, 8 июня 2016

2016-06-08T20:28:09Z

← Предыдущая версия		Версия от 20:28, 8 июня 2016
Строка 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]);
	}		}
	};		};