Разработать структуру данных

Question

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

1. добавить новый элемент значения v в k-ю позицию
2. удалить k-й элемент
3. возвращает сумму значений элементов от i до j
4. увеличить на x значения элементов от i до j

Любая идея будет оценена, спасибо

Answer 1

Я подозреваю, что вы могли бы сделать это с красно-черным деревом. Над классическим красно-черным деревом каждому узлу потребуются следующие дополнительные поля:

• размер
• сумма
• прибавка

Поле размера будет отслеживать общее количество дочерних узлов, что позволяет вводить и удалять время регистрации (n).

Поле суммы будет отслеживать сумму его дочерних узлов, позволяя суммировать время log (n).

Поле приращения будет использоваться для отслеживания приращения к каждому из его дочерних узлов, которое будет добавлено при расчете сумм. Таким образом, при вычислении итоговой суммы мы возвращаем сумму + размер * приращение. Это самый хитрый. Поле приращения будет добавлено при расчете сумм. Я думаю , добавляя положительные и отрицательные приращения в соответствующих узлах, можно было бы корректно изменить возвращаемую сумму во всех случаях, изменяя только log (n) узлов.

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

Обновление: я не собираюсь пытаться решить это полностью, но я хотел бы отметить, что увеличение i через j на n эквивалентно увеличению целого дерева на n, затем уменьшению от 0 до i на n и уменьшению от j до конец. Глобальное приращение может быть выполнено в постоянное время, при этом две другие операции являются «декрементом левой стороны» и «декрементом правой стороны», которые являются симметричными. Выполнение уменьшения левой стороны до i будет выглядеть примерно так: «возьмите счетчик левого поддерева корневого узла. Если число меньше i, уменьшите поле приращения левого дочернего элемента root на n. Затем примените левое уменьшение n к правому поддереву корневого узла до элементов i - count (left поддерево). В качестве альтернативы, если число больше i, уменьшите поле приращения левого-левого внука корня на n, затем примените левое уменьшение n к лево-правому поддереву корня до счетчика (лево-левое поддерево ) Поскольку дерево сбалансировано, я думаю, что левая операция декремента должна применяться только рекурсивно ln (n) раз. Правильный декрет был бы похожим, но обратным.

Answer 2

Требование 1, 2 и 3 может быть удовлетворено двоичным индексированным деревом (BIT, Fenwick Tree): http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees

Я подумываю о том, как изменить BIT для работы с # 4 по сложности логарифма.

Answer 3

То, что вы просите, неосуществимо.

Требование № 3 может быть возможным, но № 4 просто невозможно выполнить в логарифмическом времени. Вы должны редактировать не более каждого узла. Представьте, что я 0, а j n-1. Вам придется редактировать каждый узел. Даже при постоянном доступе это линейное время.

Edit: При дальнейшем рассмотрении, если вы отслеживали «увеличение массы», вы могли бы потенциально контролировать доступ к узлу, украсив его на выходе любым необходимым для этого увеличением массы. Я все еще думаю, что это было бы совершенно нехорошо, но я полагаю, что это возможно.