Структура данных, которая поддерживает <O (n) запросов суммы элементов от 0 до n

Question

В качестве примера представьте, что у вас есть следующие числа в списке в указанном порядке:

list = [4, 10, 3, 5, 1]

итак list [0] == 4 и list [4] == 1.

Теперь представьте, что вам нужен запрос суммы, который сообщит вам сумму всех предыдущих значений до этой заданной позиции.

list.sum(0) == 4
list.sum(1) == 14
list.sum(2) == 17
list.sum(3) == 22
list.sum(4) == 23

Кроме того, я хотел бы выполнить следующие операции, не меняя при этом запросы суммы:

list.swap(0, 1) // swap the two positions
list == [10, 4, 3, 5, 1]
list.slideBefore(0, 3) // slides 1st position value to before the 2nd position
list == [4, 3, 10, 5, 1]
list.slideAfter(2, 3) // slide 1st position value to after 2nd position
list == [4, 3, 5, 10, 1]
list.replace(3, 9) // replace value at 1st param with literal value 2nd param
list == [4, 3, 5, 9, 1]
list.append(17) // adds value to end
list == [4, 3, 5, 9, 1, 17]

Это может быть тривиально обработано массивом. Но запрос суммы всегда будет O (n). Я надеялся найти структуру данных, которая сохранит запрос суммы в O (1) или O (lg n), а также сохранит вышеуказанные операции в O (1) или O (lg n).

Полагаю, я мог бы манипулировать структурой данных fast array для достижения того, чего я хочу, но я еще не до конца ее проработал.

Другой структурой данных, на которую я смотрел, было дерево Фенвика, но мне не было ясно, как оно будет работать.

Любые предложения, мысли, хитрости или советы?

Answer 1

Рассмотрим простой массив, в котором вы храните сумму до этого элемента вместо элемента. Таким образом,

int sum(int n){ 
    return array[n]; // O(1) !
};

int elem(int n){
    if (n)
        return array[n] - array[n-1];
    return array[0];
};

Было бы O (1) раз для всех операций, кроме replace, что потребовало бы O (n).

Вы также можете рассмотреть двоичное дерево, которое содержит значения только в листьях и сохраняет сумму своих дочерних элементов в каждом узле.

Answer 2

Структура данных, которую вы хотите использовать, будет во многом зависеть от вашей схемы доступа. Если запросы очень частые, а операции модификации нечастые, вы можете просто сохранить флаг «грязный» и пересчитать суммы по запросу, если установлен флаг «грязный».

Затем вы можете уточнить это, установив «грязный индекс», который содержит индекс самого низкого элемента, который был изменен. По запросу вы должны пересчитать суммы для этого элемента и все после. Или, возможно, только до элемента, для которого вам нужна сумма, и в этот момент вы можете обновить «грязный индекс».

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

'swap' и 'append` можно выполнить за O (1) раз, и они не "испачкают" суммы, если они еще не были испорчены. «замена», конечно, приведет к тому, что грязный индекс будет установлен на этот индекс (при условии, конечно, что он не был уже с более низким индексом).

slidebefore и slideafter являются неотъемлемо O (N), если ваша структура данных является массивом, потому что вы должны перемещать данные в массиве. В вашем примере у вас есть:

list == [10, 4, 3, 5, 1]
list.slideBefore(0, 3) // slides 1st position value to before the 2nd position
list == [4, 3, 10, 5, 1]

Таким образом, элементы 1 и 2 в массиве должны были быть сдвинуты влево на одну позицию, чтобы освободить место для позиции 0, которую нужно переместить. Если бы у вас было slideBefore(0, 1000), то 1000 элементов в массиве должны были бы переместиться на одну позицию вверх. Если эти операции выполняются часто и у вас большой список, вам, вероятно, понадобится другое базовое представление.

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

Чтобы обрабатывать вставки и удаления, разрешите подлистам расти до некоторого максимального значения, прежде чем они будут разделены. Скажите, что ваш «идеал» - это пять пунктов в каждом подсписке. Но вы позволяете ему расти до 10, прежде чем разделить его на два подсписка. Для удаления вы можете разрешить подсписку переходить в 0 или объединить его с предыдущим или следующим подсписком, если в подсписке менее 3 элементов.

Идеальный размер подсписков будет зависеть от общего количества элементов, которые вы ожидаете включить в список, и, опять же, от сочетания операций, которые вы ожидаете встретить. Операции, которые по своей природе O (N) (такие как удаление и скольжение), будут отдавать предпочтение меньшим подспискам, но тогда пересчет становится более дорогим, потому что у вас больше подсписков.

Это на самом деле не меняет сложности алгоритма во время выполнения (то есть O (n / 5) по-прежнему считается O (N)), но оно действительно меняет фактическое время выполнения на довольно немного. Для списков среднего размера это может быть настоящей победой.