Построить сбалансированное бинарное дерево с n листьями; прикрепите элементы вдоль нижней части дерева в их первоначальном порядке.
Дополнить каждый узел дерева "суммой листьев поддерева"; у дерева есть # листья-1 узлы, так что это занимает O (n) время установки (которое у нас есть).
Запрос частичной суммы выглядит следующим образом: Спускайтесь по дереву к узлу запроса (листа), но всякий раз, когда вы спускаетесь вправо, добавьте сумму поддерева слева и элемент, который вы только что посетили, так как эти элементы находятся в сумма.
Изменение значения происходит следующим образом: найдите узел запроса (слева). Рассчитайте разницу, которую вы добавили. Путешествие к корню дерева; По мере продвижения к корню обновляйте каждый посещаемый узел, добавляя разницу (вам может понадобиться посетить соседние узлы, в зависимости от того, храните ли вы «сумму листьев поддерева» или «сумму левого поддерева плюс меня» или какой-то вариант); Основная идея заключается в том, что вы соответствующим образом обновите все расширенные данные ветки, которые необходимо обновить, и эти данные будут находиться в корневом пути или рядом с ним.
Две операции занимают время O (log (n)) (это высота дерева), и вы выполняете O (1) работу на каждом узле.
Возможно, вы можете использовать любое дерево поиска (например, самообалансирующееся двоичное дерево поиска может допускать вставки, другие - для более быстрого доступа), но я не подумал, что это возможно.