Блог

Мне нужно было вычислить суммы в пределах диапазона в массиве, поэтому я наткнулся на дерево сегментов и дерево Фенвика, и я заметил, что оба этих дерева запрашивают и обновляют с одинаковым асимптотическим временем выполнения. Я провел немного больше исследований, и эти 2 структуры данных, похоже, делают все с одинаковой скоростью. Оба имеют линейное использование памяти (дерево сегментов использует в два раза больше).

Помимо постоянных факторов во времени выполнения / памяти и реализациях, есть ли какая-либо причина, по которой я бы выбрал один над другим?

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

Я видел 2 других вопроса StackOverflow по этому поводу, но ответы просто описывали обе структуры данных, а не объясняли, когда одна может быть лучше другой.

Я прочитал это на Quora. Надеюсь, вы найдете это полезным.

1. Есть вещи, которые дерево сегментов может делать, но НЕМНОГО не может: БИТ по существу работает с кумулятивными величинами. Когда требуется кумулятивная величина для интервала [i..j], она определяется как разница между кумулятивными величинами для [1 … j] и [1 … i-1]. Это работает только потому, что сложение имеет обратную операцию. Вы не можете этого сделать, если операция необратима (например, max). С другой стороны, каждый интервал в дереве сегментов может быть найден как объединение непересекающихся интервалов, и обратная операция не требуется
2. БИТ требует вдвое меньше памяти, чем дерево сегментов: в тех случаях, когда у вас мазохистские ограничения памяти, вы почти застряли с использованием БИТА
3. Хотя операции с битовым и сегментным деревом равны O (log (n)), операции с деревом сегментов имеют больший постоянный коэффициент: это не должно иметь значения для большинства случаев. Но еще раз, если у вас мазохистские временные ограничения, вы можете переключиться с дерева сегментов на БИТ. Постоянный коэффициент может стать большей проблемой, если дерево БИТ / сегментов многомерно.

Я нашел кое-что в cp-алгоритме, который может вам помочь.

Дерево сегментов —

• отвечает на каждый запрос в O (logN)
• предварительная обработка выполнена за O (N)
• Плюсы: хорошая временная сложность.
• Минусы: больший объем кода по сравнению с другими структурами данных.

Дерево Фенвика —

• отвечает на каждый запрос в O (logN)

• предварительная обработка выполнена в O (NlogN)

• Плюсы: самый короткий код, хорошая временная сложность

• Минусы: дерево Фенвика можно использовать только для запросов с L = 1, поэтому оно неприменимо ко многим проблемам.

Комментарий к ответу Харша Хитеша Шаха: Последнее замечание против использования дерева Фенвика вообще не выполняется. Доказательство встречным примером: допустим, у нас есть дерево Фенвика для сумм префиксов, функция query(x) возвращает сумму префиксов, начиная с первого индекса 1 и вплоть до индекса x. Если мы хотим вычислить сумму для некоторого интервала [L, R] с 1 < L <= R <= N, мы можем просто взять query(R)-query(L-1) .

Некоторая дополнительная информация:

• Деревья сегментов могут храниться также неявно (как куча), и это займет 2n место
• Деревья Фенвика — это интерактивная структура данных, а это означает, что вы можете добавлять элементы в конец, как в массив, и это все равно будет работать. Деревья сегментов не имеют этого свойства по умолчанию. Если вы сохраняете их неявно, вы можете выполнить операции добавления и добавления в амортизированном O(log(n)) , удвоив размер дерева сегментов (точно так же, как амортизированные O(1) массивы). Вам нужно изучить, как выглядит дерево сегментов в памяти, а затем соответствующим образом поместить новое пространство (вы не можете просто поместить все лишнее пространство в один конец). Имейте в виду, что, поскольку дерево сегментов уже занимает 2n место, каждый раз, когда вы удваиваете массив, у вас теперь есть 4n использование пространства
• Деревья Фенвика быстрее и чрезвычайно просты в реализации. Асимптотические оценки эквивалентны, но самый простой код запроса и обновления практически не имеет ветвей, нерекурсивен и использует очень мало операций. Версии этого дерева сегментов могут быть сделаны почти так же быстро, но это требует дополнительных усилий. К счастью, это имеет значение только при очень больших входных данных, поскольку хранение дерева сегментов неявно имеет отличную пространственную локальность, что дает ему хороший импульс по сравнению с хранением указателей
• Деревья Фенвика не могут вычислить обратный запрос в log(n) (насколько мне известно); то есть, если мы храним, например, частичные суммы, и я хочу знать, какой индекс i оценивает частичную сумму s , это займет log(n)^2 . Этот процесс тривиален log(n) для дерева сегментов
• Существует множество других запросов, которые могут выполнять деревья сегментов, многие из которых невозможны в дереве Фенвика. Разумеется, вы платите за эту дополнительную гибкость стоимостью 2n хранения

Редактировать: вы можете вычислить этот запрос в log(n) ! Вот моя реализация:

 def find(self, s):
    b = 1
    while b < len(bit):
        b <<= 1
    b >>= 1
    index = 0
    cur = 0
    while b > 0:
        if bit[index   b]   cur <= s:
            index  = b
            cur  = bit[index]
        b >>= 1
    return (index, cur)
  

Это вернет индекс и сумму, которые были ближе всего к целевой частичной сумме (всегда будет <= target). Однако я не верю, что это работает с отрицательными числами в БИТЕ.

Хорошая запись дерева сегментов: https://cp-algorithms.com/data_structures/segment_tree.html