Можно ли построить дерево отрезков (segment tree) по нескольким запросам?

Question

[becks]

Добрый день!

Разбираюсь с Segment Tree и смотрю типичные задачи, которые данная структура позволяет эффективно решать на запрашиваемом отрезке. Типичная задача - нахождение суммы на отрезке или поиск минимума/максимума, вроде всё логично и понятно. Но у меня возник вопрос, а можно ли применять этот тип данных, если меняются не только границы отрезка, но и атрибут какой-нибудь операции? О чем идет речь. Допустим, нужно найти на отрезке число элементов делящихся без остатка на x из набора X. Т.е. мы построили дерево отрезков, а потом получаем на вход несколько запросов, каждый из которых содержит границы отрезка и делитель, и, соответственно, для каждого такого запроса мы должны дать ответ. Нужно ли будет перестраивать дерево?
Если подкинете ссылочку, где можно детальнее почитать про такого рода особенности, буду благодарен.

Answer 1

[Владимир Олохтонов]

У вас в каждой вершине лежит информация о применении к отвечающему ей сегменту заранее определенной операции, если вы изменяете операцию и при этом не делали предпросчет заранее, то вам придется пересчитать значения во всех вершинах, что равносильно перестраиванию дерева с нуля.

Comments

[becks]

Понял. Для такого рода задач существует какой-то другой класс структур или тут уже ничего хитрого не придумать и нужен простой линейный проход по отрезку?

[Mercury13]

Крайне сложно придумать другую структуру.

[Владимир Олохтонов]

becks: можете просто в каждой вершине хранить весь набор заранее подсчитанных операций (если их не слишком много).