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

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

• Массив не меняется: 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-й порядковой статистики на отрезке

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