Дерево отрезков: обзор задач: различия между версиями

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
 
Строка 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]]
* Прибавление на отрезке:
* Присвоение/прибавление к одному элементу:
* Присвоение/прибавление на отрезке:

Текущая версия от 21:34, 15 июня 2016

Запрос минимума (максимума) на отрезке

МЦНМО 3309, SPOJ GSS1
  • Присвоение/прибавление к одному элементу: стандартная реализация дерева отрезков, O(logN)
МЦНМО 3316, SPOJ GSS3
  • Присвоение/прибавление на отрезке: дерево отрезков с lazy propagation, O(logN)
МЦНМО 3328

Запрос индекса минимума (максимума) на отрезке

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

Запрос суммы на отрезке

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

Запрос суммы квадратов на отрезке

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

Запрос НОД на отрезке

МЦНМО 3314
  • Присвоение/прибавление к одному элементу: стандартная реализация дерева отрезков, O(logN)
МЦНМО 3321
  • Присвоение/прибавление на отрезке: 2 дерева отрезков: 1, 2 , O(logN)

Запрос количества нулей на отрезке

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

Запрос индекса k-го нуля на отрезке

  • Присвоение/прибавление к одному элементу: запрос количества нулей на префиксе и спуск по дереву отрезков, O(logN)
МЦНМО 3323
  • Присвоение на отрезке: дерево отрезков с lazy propagation, запрос количества нулей на префиксе и спуск по дереву отрезков, O(logN)
  • Прибавление на отрезке: ???

Запрос максимального ряда нулей на отрезке

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

Запрос ряда с максимальной суммой на отрезке

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

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

  • Массив не меняется:
SPOJ KQUERY, SPOJ KQUERYO
  • Присвоение/прибавление к одному элементу:
  • Присвоение/прибавление на отрезке:

Запрос количества различных чисел на отрезке

  • Массив не меняется:
SPOJ DQUERY
  • Присвоение/прибавление к одному элементу:
  • Присвоение/прибавление на отрезке:

Запрос k-й порядковой статистики на отрезке

  • Массив не меняется:
SPOJ MKTHNUM
  • Присвоение/прибавление к одному элементу:
  • Присвоение/прибавление на отрезке: