Я полагаю, что вы можете получить эту работу за амортизированное время O (log n) на доступ к элементу или изменение значения, используя модификацию Splay Tree. Идея этого подхода двояка. Во-первых, вместо того, чтобы хранить массив в виде массива, мы сохраняем его в виде пары массивов, содержащих исходные значения, и дерева сплайнов, где ключ каждого узла является индексом в массиве. Например, для массива из семи элементов установка может выглядеть следующим образом:
Array: 3 1 4 2 5 9 3
Tree: 3
/ \
1. 5
/ \. / \
0. 2 4. 6
Обратите внимание, что дерево содержит индексы в массиве, а не сами элементы массива. Если мы хотим найти значение по определенному индексу, мы просто выполняем поиск индекса по индексу Splay Tree, а затем возвращаем элемент массива в заданной позиции, что занимает время амортизации O (log n).
Операцию, которую вы хотите поддержать, изменяя все будущие значения, я назову операцией «потолок», поскольку она устанавливает потолок для всех значений после текущего. Один из способов думать об этом состоит в том, что с каждым элементом в массиве связан верхний предел (который изначально равен бесконечности), и тогда истинное значение элемента является минимумом его истинного значения и верхнего предела. Хитрость заключается в том, что с помощью Splay Tree мы можем отрегулировать потолок всех значений в определенной точке или за ее пределами за время амортизации O (log n). Для этого мы расширяем дерево отображения, сохраняя в каждом узле значение c, которое представляет верхний предел, налагаемый этим элементом вперед, а затем вносим соответствующие изменения в c по мере необходимости.
Например, предположим, что мы хотим наложить потолок от некоторого элемента вперед. Давайте предположим, что этот элемент уже находится в корне дерева. В этом случае мы просто устанавливаем его значение c в качестве нового потолка за время O (1). С этого момента, всякий раз, когда мы выполняем поиск некоторого значения, которое приходит к этому элементу или после него, мы можем записать потолок, когда спускаемся по дереву от корня к рассматриваемому элементу. В более общем смысле, когда мы выполняем поиск, каждый раз, когда мы следуем по правильной дочерней ссылке, мы отмечаем значение c этого узла. Как только мы попадаем в рассматриваемый элемент, мы знаем потолок этого элемента, потому что мы можем просто взять минимальный потолок узлов на пути от корня, правые дочерние элементы которого мы следовали. Таким образом, чтобы найти элемент в структуре, мы выполняем стандартный поиск в Splay Tree, отслеживая значение c, в котором мы находимся, затем выводим минимум значения массива origin и значения c.
Но для того, чтобы сделать эту работу, наш подход должен учитывать тот факт, что Splay Tree делает вращения. Другими словами, мы должны показать, как распространять значения c во время вращения. Предположим, что мы хотим сделать вращение, подобное этому:
A. B
/. ->. \
B. A
В этом случае мы не изменяем никакие значения c, поскольку любое значение, найденное после A, все равно будет проходить через узел A. Тем не менее, если мы сделаем противоположное вращение и потянем A выше B, то мы установим значение c в A как минимум значения c в B и значения c в A, так как, если мы спустимся в левое поддерево A после выполнения вращения, нам нужно Потолок B во внимание. Это означает, что мы выполняем O (1) работу за оборот, а поскольку амортизированное число вращений, выполненных за одно расширение, составляет O (log n), мы выполняем амортизированную O (log n) работу за поиск.
Чтобы завершить картину, чтобы обновить произвольный потолок, мы развернем узел, потолок которого должен быть изменен, до корня, затем установим его значение c.
Короче говоря, у нас есть O (log n), время поиска O (log n) (амортизировано).
Эта идея основана на обсуждении деревьев ссылок / срезов из оригинальной статьи Слеатора и Тарьяна "Саморегулирующиеся деревья бинарного поиска", в которой также представлено дерево сплайнов.
Надеюсь, это поможет!