Дерево отрезков: обзор задач

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

• Массив не меняется: Sparse table, O(1)

МЦНМО 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)

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

• Массив не меняется: Sparse table, O(1)

МЦНМО 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

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