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

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
(Новая страница: «== Запрос минимума (максимума) на отрезке == * Массив не меняется: Sparse table, O(1) * Прибавление…»)
 
Нет описания правки
Строка 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 на отрезке ==

Версия от 22:01, 9 июня 2016

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

  • Массив не меняется: 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)

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

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

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

  • Массив не меняется: Sparse table, O(1)
  • Прибавление к одному элементу: стандартная реализация дерева отрезков, O(logN)
  • Прибавление на отрезке: 2 дерева отрезков: 1, 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-й порядковой статистики на отрезке

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