Компактная структура данных для частичных продуктов последовательности?

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

Основная идея заключается в следующем: дополнить каждый узел дерева так, чтобы он хранил произведение всех чисел в левом поддереве и произведение всех чисел, хранящихся в правом поддереве. Мы назовем их leftProd и rightProd. Эти значения могут быть вычислены за время O(1) из значений в левом и правом поддеревьях узла и значения в самом узле, поэтому дополнение дерева этой дополнительной информацией не меняет асимптотическую временную сложность реализации. Кроме того, сохраните еще два значения: minIndex и maxIndex, минимальный и максимальный индексы в поддереве с корнем в данном узле. Эти два значения можно эффективно вычислить из значений в левом и правом поддеревьях, поэтому добавление этого дополнительного дополнения не требует дополнительных затрат.

Теперь предположим, что вы хотите найти произведение значений в диапазоне [низкий, высокий]. Для этого выполните рекурсивный поиск в дереве следующим образом:

1. Если [low, high] находится слева от индекса текущего узла, рекурсивно вычислить значение в левом поддереве.
2. Если [low, high] находится справа от индекса текущего узла, рекурсивно вычислить значение в правом поддереве.
3. Если [low, high] точно соответствует диапазону [minIndex, maxIndex], вернуть произведение значения узла, leftProd и rightProd.
4. В противном случае сделайте рекурсивный вызов в левом поддереве для [низкий, индекс - 1], рекурсивный вызов в правом поддереве для [индекс + 1, высокий] и верните произведение этих двух чисел и собственное значение узла.

Нам нужно обосновать, почему это будет работать эффективно. Суть идеи в следующем. Случаи 1 и 2 делают ровно один рекурсивный вызов. Случай 3 не делает рекурсивных вызовов. Случай 4 сделает два рекурсивных вызова. В каждом случае работает O(1). Если бы не ветвление, выполненное в случае 4, рекурсия просто проходила бы по дереву сверху вниз, выполняя O(1) работы на уровне, поэтому общая проделанная работа равна O(log n).

Однако я собираюсь заявить, что случай 4 на самом деле не так сильно разветвляется, как вы могли бы подумать. Представьте, что в первый раз в рекурсии происходит случай 4. Когда это произойдет, он сделает два рекурсивных вызова, один влево и один вправо. Обратите внимание, что эти рекурсивные вызовы предназначены для очень специфических поддиапазонов: вызов в левом поддереве запрашивает диапазон от некоторого индекса до последнего индекса в левом поддереве, а вызов в правом поддереве запрашивает диапазон от первого индекса в правое поддерево до некоторого индекса. Другими словами, сделанные рекурсивные вызовы находятся в поддиапазонах, которые "выровнены" с одной стороной поддеревьев, в которые они возвращаются.

Теперь подумайте о каждом случае, когда мы сталкиваемся со Случаем 4 с этого момента. Всякий раз, когда мы это делаем, мы знаем, что один из двух диапазонов, в которые будет спускаться рекурсия, будет состоять из диапазона полного поддерева. Это немедленно приведет к тому, что мы столкнемся со случаем 3, так что рекурсивный вызов фактически не будет настоящим рекурсивным вызовом. Это означает, что количество раз, когда Случай 4 может «действительно» разветвляться, не более одного раза. С этого момента рекурсия эффективно продолжается только по одному пути в дереве.

В целом это означает, что мы можем ограничить общую проделанную работу — по крайней мере, асимптотически — как работу, необходимую для того, чтобы дважды пройти от вершины дерева вниз до основания, выполняя работу O (1) на узел. Это составляет O(log n) общей работы, как и требовалось.

И сколько места нам нужно? Это увеличение использует только O (1) пространства на узел, поэтому общее необходимое пространство составляет O (n).

Надеюсь это поможет!