Дерево отрезков: обзор задач - История изменений

Ctrlalt в 21:34, 15 июня 2016

2016-06-15T21:34:53Z

← Предыдущая версия		Версия от 21:34, 15 июня 2016
Строка 1:		Строка 1:
	== Запрос минимума (максимума) на отрезке ==		=== Запрос минимума (максимума) на отрезке ===
	* Массив не меняется: [[Sparse table]], O(1)		* Массив не меняется: [[Sparse table]], O(1)
	* ~~Прибавление~~ к одному элементу: стандартная реализация дерева отрезков, O(logN)		: [[МЦНМО 3309]], [[SPOJ GSS1]]
	* ~~Прибавление~~ на отрезке: дерево отрезков с lazy propagation, O(logN)		* Присвоение/прибавление к одному элементу: стандартная реализация дерева отрезков, O(logN)
			: [[МЦНМО 3316]], [[SPOJ GSS3]]
			* Присвоение/прибавление на отрезке: дерево отрезков с lazy propagation, O(logN)
			: [[МЦНМО 3328]]

	== Запрос индекса минимума (максимума) на отрезке ==		=== Запрос индекса минимума (максимума) на отрезке ===
	* ~~Прибавление~~ к одному элементу: стандартная реализация дерева отрезков, либо в вершине вместе с индексом хранится величина максимума/минимума, либо эта величина проверяется в исходном массиве, O(logN)		* Присвоение/прибавление к одному элементу: стандартная реализация дерева отрезков, либо в вершине вместе с индексом хранится величина максимума/минимума, либо эта величина проверяется в исходном массиве, O(logN)
	* ~~Прибавление~~ на отрезке: дерево отрезков с lazy propagation, в вершине вместе с индексом хранится величина максимума/минимума, O(logN)		: [[МЦНМО 3318]]
			* Присвоение/прибавление на отрезке: дерево отрезков с lazy propagation, в вершине вместе с индексом хранится величина максимума/минимума, O(logN)

	== Запрос суммы на отрезке ==		=== Запрос суммы на отрезке ===
	* Массив не меняется: префиксные суммы, O(1)		* Массив не меняется: префиксные суммы, O(1)
	* ~~Прибавление~~ к одному элементу: стандартная реализация дерева отрезков, O(logN), либо [[дерево Фенвика]], O(logN)		: [[МЦНМО 3308]]
	* ~~Прибавление~~ на отрезке: дерево отрезков с lazy propagation (в push() сумма обновляется как t[v] += tAdd[v] *(vr - vl + 1)), O(logN)		* Присвоение/прибавление к одному элементу: стандартная реализация дерева отрезков, O(logN), либо [[дерево Фенвика]], O(logN)
			: [[МЦНМО 3317]]
			* Присвоение/прибавление на отрезке: дерево отрезков с lazy propagation (в push() сумма обновляется как t[v] += tAdd[v] *(vr - vl + 1)), O(logN)

	== Запрос суммы квадратов на отрезке ==		=== Запрос суммы квадратов на отрезке ===
	* Массив не меняется: префиксные суммы, O(1)		* Массив не меняется: префиксные суммы, O(1)
	* ~~Прибавление~~ к одному элементу: стандартная реализация дерева отрезков, O(logN)		* Присвоение/прибавление к одному элементу: стандартная реализация дерева отрезков, O(logN)
	* ~~Прибавление~~ на отрезке: дерево отрезков с lazy propagation, вершина хранит сумму и сумму квадратов на отрезке, O(logN)		* Присвоение/прибавление на отрезке: дерево отрезков с lazy propagation, вершина хранит сумму и сумму квадратов на отрезке, O(logN)

	== Запрос НОД на отрезке ==		=== Запрос НОД на отрезке ===
	* Массив не меняется: [[Sparse table]], O(1)		* Массив не меняется: [[Sparse table]], O(1)
	* ~~Прибавление~~ к одному элементу: стандартная реализация дерева отрезков, O(logN)		: [[МЦНМО 3314]]
	* ~~Прибавление~~ на отрезке: 2 дерева отрезков: [http://codeforces.com/blog/entry/14518 1], [http://codeforces.com/blog/entry/9722 2] , O(logN)		* Присвоение/прибавление к одному элементу: стандартная реализация дерева отрезков, O(logN)
			: [[МЦНМО 3321]]
			* Присвоение/прибавление на отрезке: 2 дерева отрезков: [http://codeforces.com/blog/entry/14518 1], [http://codeforces.com/blog/entry/9722 2] , O(logN)

	== Запрос количества нулей на отрезке ==		=== Запрос количества нулей на отрезке ===
	* Массив не меняется: префиксные суммы, O(1)		* Массив не меняется: префиксные суммы, O(1)
	* ~~Прибавление~~ к одному элементу: стандартная реализация дерева отрезков, O(logN)		: [[МЦНМО 3313]]
			* Присвоение/прибавление к одному элементу: стандартная реализация дерева отрезков, O(logN)
			: [[МЦНМО 3325]]
	* Присвоение на отрезке: дерево отрезков с lazy propagation, O(logN)		* Присвоение на отрезке: дерево отрезков с lazy propagation, O(logN)
	* Прибавление на отрезке: ???		* Прибавление на отрезке: ???

	== Запрос индекса k-го нуля на отрезке ==		=== Запрос индекса k-го нуля на отрезке ===
	* ~~Прибавление~~ к одному элементу: запрос количества нулей на префиксе и спуск по дереву отрезков, O(logN)		* Присвоение/прибавление к одному элементу: запрос количества нулей на префиксе и спуск по дереву отрезков, O(logN)
			: [[МЦНМО 3323]]
	* Присвоение на отрезке: дерево отрезков с lazy propagation, запрос количества нулей на префиксе и спуск по дереву отрезков, O(logN)		* Присвоение на отрезке: дерево отрезков с lazy propagation, запрос количества нулей на префиксе и спуск по дереву отрезков, O(logN)
	* Прибавление на отрезке: ???		* Прибавление на отрезке: ???

	== Запрос максимального ряда нулей на отрезке ==		=== Запрос максимального ряда нулей на отрезке ===
	* ~~Прибавление~~ к одному элементу: дерево отрезков, вершина хранит также максимальные длины префикса и суффикса из нулей и длину отрезка, O(logN)		* Присвоение/прибавление к одному элементу: дерево отрезков, вершина хранит также максимальные длины префикса и суффикса из нулей и длину отрезка, O(logN)
			: [[МЦНМО 111798]]
	* Присвоение на отрезке: дерево отрезков с lazy propagation, вершина хранит также максимальные длины префикса и суффикса из нулей и длину отрезка, O(logN)		* Присвоение на отрезке: дерево отрезков с lazy propagation, вершина хранит также максимальные длины префикса и суффикса из нулей и длину отрезка, O(logN)
	* Прибавление на отрезке: ???		* Прибавление на отрезке: ???

	== Запрос ряда с максимальной суммой на отрезке ==		=== Запрос ряда с максимальной суммой на отрезке ===
	* ~~Прибавление~~ к одному элементу: дерево отрезков, вершина хранит также максимальные суммы префикса и суффикса и сумму всего отрезка, O(logN)		* Присвоение/прибавление к одному элементу: дерево отрезков, вершина хранит также максимальные суммы префикса и суффикса и сумму всего отрезка, O(logN)
	* Присвоение на отрезке: дерево отрезков с lazy propagation, вершина хранит также максимальные суммы префикса и суффикса и сумму всего отрезка, O(logN)		* Присвоение на отрезке: дерево отрезков с lazy propagation, вершина хранит также максимальные суммы префикса и суффикса и сумму всего отрезка, O(logN)
	* Прибавление на отрезке: ???		* Прибавление на отрезке: ???

	== Запрос количества чисел от a до b на отрезке ==		=== Запрос количества чисел от a до b на отрезке ===
	* Массив не меняется:		* Массив не меняется:
	* ~~Прибавление~~ к одному элементу:		: [[SPOJ KQUERY]], [[SPOJ KQUERYO]]
	* ~~Прибавление~~ на отрезке:		* Присвоение/прибавление к одному элементу:
			* Присвоение/прибавление на отрезке:

	== Запрос количества различных чисел на отрезке ==		=== Запрос количества различных чисел на отрезке ===
	* Массив не меняется:		* Массив не меняется:
	* ~~Прибавление~~ к одному элементу:		: [[SPOJ DQUERY]]
	* ~~Прибавление~~ на отрезке:		* Присвоение/прибавление к одному элементу:
			* Присвоение/прибавление на отрезке:

	== Запрос k-й порядковой статистики на отрезке ==		=== Запрос k-й порядковой статистики на отрезке ===
	* Массив не меняется:		* Массив не меняется:
	* ~~Прибавление~~ к одному элементу:		: [[SPOJ MKTHNUM]]
	* ~~Прибавление~~ на отрезке:		* Присвоение/прибавление к одному элементу:
			* Присвоение/прибавление на отрезке:

Ctrlalt в 22:01, 9 июня 2016

2016-06-09T22:01:22Z

← Предыдущая версия		Версия от 22:01, 9 июня 2016
Строка 12:		Строка 12:
	* Прибавление к одному элементу: стандартная реализация дерева отрезков, O(logN), либо [[дерево Фенвика]], O(logN)		* Прибавление к одному элементу: стандартная реализация дерева отрезков, O(logN), либо [[дерево Фенвика]], O(logN)
	* Прибавление на отрезке: дерево отрезков с lazy propagation (в push() сумма обновляется как t[v] += tAdd[v] *(vr - vl + 1)), O(logN)		* Прибавление на отрезке: дерево отрезков с lazy propagation (в push() сумма обновляется как t[v] += tAdd[v] *(vr - vl + 1)), O(logN)

			== Запрос суммы квадратов на отрезке ==
			* Массив не меняется: префиксные суммы, O(1)
			* Прибавление к одному элементу: стандартная реализация дерева отрезков, O(logN)
			* Прибавление на отрезке: дерево отрезков с lazy propagation, вершина хранит сумму и сумму квадратов на отрезке, O(logN)

	== Запрос НОД на отрезке ==		== Запрос НОД на отрезке ==
Строка 36:		Строка 41:
	== Запрос ряда с максимальной суммой на отрезке ==		== Запрос ряда с максимальной суммой на отрезке ==
	* Прибавление к одному элементу: дерево отрезков, вершина хранит также максимальные суммы префикса и суффикса и сумму всего отрезка, O(logN)		* Прибавление к одному элементу: дерево отрезков, вершина хранит также максимальные суммы префикса и суффикса и сумму всего отрезка, O(logN)
	* ~~Прибавление~~ на отрезке: дерево отрезков с lazy propagation, вершина хранит также максимальные суммы префикса и суффикса и сумму всего отрезка, O(logN)		* Присвоение на отрезке: дерево отрезков с lazy propagation, вершина хранит также максимальные суммы префикса и суффикса и сумму всего отрезка, O(logN)
			* Прибавление на отрезке: ???

	== Запрос количества чисел от a до b на отрезке ==		== Запрос количества чисел от a до b на отрезке ==

Ctrlalt: Новая страница: «== Запрос минимума (максимума) на отрезке == * Массив не меняется: Sparse table, O(1) * Прибавление…»

2016-06-09T20:50:26Z

Новая страница: «== Запрос минимума (максимума) на отрезке == * Массив не меняется: Sparse table, O(1) * Прибавление…»

Новая страница

== Запрос минимума (максимума) на отрезке ==
* Массив не меняется: [[Sparse table]], O(1)
* Прибавление к одному элементу: стандартная реализация дерева отрезков, O(logN)
* Прибавление на отрезке: дерево отрезков с lazy propagation, O(logN)

== Запрос индекса минимума (максимума) на отрезке ==
* Прибавление к одному элементу: стандартная реализация дерева отрезков, либо в вершине вместе с индексом хранится величина максимума/минимума, либо эта величина проверяется в исходном массиве, O(logN)
* Прибавление на отрезке: дерево отрезков с lazy propagation, в вершине вместе с индексом хранится величина максимума/минимума, O(logN)

== Запрос суммы на отрезке ==
* Массив не меняется: префиксные суммы, O(1)
* Прибавление к одному элементу: стандартная реализация дерева отрезков, O(logN), либо [[дерево Фенвика]], O(logN)
* Прибавление на отрезке: дерево отрезков с lazy propagation (в push() сумма обновляется как t[v] += tAdd[v] *(vr - vl + 1)), O(logN)

== Запрос НОД на отрезке ==
* Массив не меняется: [[Sparse table]], O(1)
* Прибавление к одному элементу: стандартная реализация дерева отрезков, O(logN)
* Прибавление на отрезке: 2 дерева отрезков: [http://codeforces.com/blog/entry/14518 1], [http://codeforces.com/blog/entry/9722 2] , O(logN)

== Запрос количества нулей на отрезке ==
* Массив не меняется: префиксные суммы, O(1)
* Прибавление к одному элементу: стандартная реализация дерева отрезков, O(logN)
* Присвоение на отрезке: дерево отрезков с lazy propagation, O(logN)
* Прибавление на отрезке: ???

== Запрос индекса k-го нуля на отрезке ==
* Прибавление к одному элементу: запрос количества нулей на префиксе и спуск по дереву отрезков, O(logN)
* Присвоение на отрезке: дерево отрезков с lazy propagation, запрос количества нулей на префиксе и спуск по дереву отрезков, O(logN)
* Прибавление на отрезке: ???

== Запрос максимального ряда нулей на отрезке ==
* Прибавление к одному элементу: дерево отрезков, вершина хранит также максимальные длины префикса и суффикса из нулей и длину отрезка, O(logN)
* Присвоение на отрезке: дерево отрезков с lazy propagation, вершина хранит также максимальные длины префикса и суффикса из нулей и длину отрезка, O(logN)
* Прибавление на отрезке: ???

== Запрос ряда с максимальной суммой на отрезке ==
* Прибавление к одному элементу: дерево отрезков, вершина хранит также максимальные суммы префикса и суффикса и сумму всего отрезка, O(logN)
* Прибавление на отрезке: дерево отрезков с lazy propagation, вершина хранит также максимальные суммы префикса и суффикса и сумму всего отрезка, O(logN)

== Запрос количества чисел от a до b на отрезке ==
* Массив не меняется:
* Прибавление к одному элементу:
* Прибавление на отрезке:

== Запрос количества различных чисел на отрезке ==
* Массив не меняется:
* Прибавление к одному элементу:
* Прибавление на отрезке:

== Запрос k-й порядковой статистики на отрезке ==
* Массив не меняется:
* Прибавление к одному элементу:
* Прибавление на отрезке: