Объяснение дерева Фенвика
19 мая 2022 г.Рассмотрим задачу отслеживания списка целых чисел A. Пользователи списка «А» заинтересованы в выполнении двух типов операций:
(1) Обновление значения любого элемента в A и
(2) Вычисление суммы некоторого подмассива A[l..r].
Длина списка A равна O(N), количество запросов типа 1 равно O(Q_1), а количество запросов типа 2 равно O(Q_2). В дополнение к правильному выполнению процедур, время, затрачиваемое на каждый процесс, должно быть соответствующим, чтобы удовлетворить все запросы.
:::Информация
Пример: Рассмотрим следующий список целых чисел A = [1, 2, 3, 4, 5].
Пользователь запрашивает запрос типа 1, чтобы увеличить 2-й элемент A на 3. Это приводит к обновленному списку A = [1, 5, 3, 4, 5]. Следующий запрос пользователя — это сумма элементов в A[1..3]. Это значение равно 9.
Суть проблемы заключается в определении наилучшей структуры данных для удовлетворения таких потребностей. Одним из таких хороших вариантов является дерево Фенвика, которое требует логарифмического времени для каждого запроса (как для обновления, так и для запроса диапазона). В оставшейся части этой статьи исследуется концепция этой интригующей структуры данных.
Первая попытка решения
Рассмотрим несколько возможных решений ситуации. Самое естественное решение состоит в том, чтобы оставить в исходном виде только список целых чисел A. Любой запрос на обновление может быть обработан быстро и легко. Поскольку запрос на обновление требует изменения элемента A, запрос может быть обработан за время O(1). С другой стороны, запрос суммы зависит от длины запрошенного интервала. Каждый раз, когда выполняется запрос типа 2, необходимо было вычислять сумму путем перебора диапазона. В худшем случае запрос суммы диапазона может занять O (N). Когда количество запросов типа 2 невелико, эта стратегия будет работать эффективно. Однако по мере увеличения количества запросов типа 2 общая временная сложность становится O(Q_2.N). Который является квадратичным по своей природе и, следовательно, нежелательным.
Когда обновлений больше, а запросов суммы диапазона меньше, поддержка только списка A решает проблему.
Но что, если Q2 большой? Мы хотели бы ускорить запросы суммы диапазона. Простое наблюдение показывает, что любую сумму подмассива можно обозначить как разность сумм префиксов. Вот как это считается -
сумма(A[l..r]) = сумма(A[0..r]) - сумма(A[0..l-1])
Таким образом, если у нас есть предварительно рассчитанные суммы префиксов, подзапрос диапазона может быть обработан за время O(1). Основываясь на этой идее, давайте сохраним массив сумм префиксов P для массива A. Теперь на любой запрос диапазона можно ответить, используя значения, присутствующие в списке P. Но это делает операцию обновления дорогостоящей. Обратите внимание, что любое изменение значения A[i] заставит нас пересчитать записи в P для всех позиций, больших или равных i. Таким образом, в худшем случае операция обновления может занять время O(n).
Когда количество операций обновления меньше по сравнению с количеством запросов диапазона, сохранение массива префиксов является эффективным решением.
То, что мы только что видели, — это две крайности всех возможных решений. То, как дерево Фенвика поддерживает все эти данные, позволяет нам отвечать на оба типа запросов за время O(logn).
Основная идея дерева Фенвика
Идея Fenwick Tree состоит в том, чтобы поддерживать список T. Длина списка T такая же, как и у списка A. Каждый элемент списка T[i] хранит сумму элементов A в диапазоне от g(i) до i. Где g(i) попадает в диапазон [0, i]. Таким образом, есть много вариантов функции g(.). Как только список «T» создан, мы можем обработать запрос, чтобы найти сумму префикса «A[0..r]», как предлагает следующая процедура.
```питон
def sum(r): # Сумма из A[0...r]
с = 0
в то время как г >= 0:
с = с + Т[г]
г = г (г) - 1
вернуть с
Для запроса на обновление список T необходимо обновить, чтобы учесть увеличение «дельты» в элементах в индексе «pos». Таким образом, запрос на обновление повлияет на те индексы j в T, диапазон которых содержит pos. Следующие процедуры резюмируют то же самое.
```питон
обновление защиты (поз., дельта):
для всех j, где g(j) <= pos <= j:
T[j] += дельта
возврат
Выбор функции g() — это последняя часть головоломки. Грамотный выбор одной и той же функции помогает достичь пределов Fenwick Tree.
Когда g(i)=0, список T сводится к сумме префиксов. И, когда g(i)=i, список T становится точно таким же, как список A.
Выбор функции g() в дереве Фенвика
Следующий выбор функции g() сделан в Fenwick Tree. Он определяется как «g(i)» — это число, полученное путем перестановки всех конечных нулей числа «i». Другими словами, g(i) получается путем преобразования всех единиц в ноль при переходе от младшего значащего бита (LSB) к старшему значащему биту (MSB) до тех пор, пока не будет получен ноль. Эту функцию можно красиво записать в терминах побитовых операторов как g(i) = i & (i + 1).
:::Информация
Примеры — цифры, выделенные жирным шрифтом, в двоичном формате
г(8) = г(1000) = 1000 = 8
г(7) = г(111) = 000 = 0
г(23) = г(10111) = 10000 = 16
Таким образом, у нас есть все детали, необходимые для обработки запросов суммы. Но все еще существует препятствие в реализации метода обновления. Как нам найти все те позиции в списке T, которые затронуты операцией обновления? Важно отметить, что после преобразования завершающих единиц в ноль любые позиции списка T, которые становятся меньше или равными позиции pos, которая обновляется, также должны быть обновлены. Все эти числа можно получить, заменив младший значащий ноль на «1». Продолжение этого процесса приведет к получению всех тех позиций, которые будут затронуты запросом на обновление. Для этого тоже есть прямая функция, которую можно задать следующим образом: -h(j) = j | (j + 1)
:::Информация
Пример
pos = 5. Таким образом, T[5] будет обновлен.
ч (5) = Н ( 101 ) = 111 = 7. Таким образом, T [7] будет обновляться.
h(8) = h(111) = 1111 = 15. Таким образом, T[15] будет обновлен.
Это также завершает последнюю часть головоломки. Теперь на оба запроса можно ответить за время O(log n). Далее мы увидим неофициальное доказательство этого утверждения.
Понимание временной сложности
Во-первых, давайте возьмем метод суммы. Для любого диапазона [0, r] мы переходим от r к g(r)-1, к g(g(r))-1 и так далее, пока не достигнем 0. Рассмотрим число n, у которого младший значащий бит (LSB) равен нулю. Если число n не содержит единиц в двоичном представлении, мы закончили. Итак, предположим, что число n имеет 1 на ith немного слева. Число n будет иметь вид n = b_1 b_2 b_3 … b_(i-1) 1 0 0 0 … 0, где b_1, b_2, …, b_(i-1) равно 0 или 1. Так как завершающих единиц нет, мы будем иметь g(n) = n. Таким образом, мы будем двигаться от n к n-1 во время цикла. Число n-1 будет иметь следующее двоичное представление n-1 = b_1 b_2 b_3 … b_(i-1) 0 1 1 1 … 1. Обратите внимание, что g(n-1) будет выглядеть как g(n-1) = b_1 b_2 b_3 … b_(i-1) 0 0 0 0 … 0. Таким образом, всего за 2 шага самый правый установленный бит в числе n сбрасывается. А поскольку в числе может быть не более log n установленных битов, цикл завершится через логарифмическое число шагов.
Если число уже имеет конечные нули, то также каждый шаг будет сбрасывать крайний правый установленный бит. Таким образом, вся процедура обязательно остановится через логарифмическое число шагов.
Вывод
Использование дерева Фенвика для обработки обновлений точек и запроса суммы диапазона является одним из многих приложений, в которых эта интересная структура данных находит свое применение. Многие реализации Fenwick Tree доступны по всему Интернету. Один такой можно найти [здесь] (https://cp-algorithms.com/data_structures/fenwick.html#:\~:text=ranges%20they%20cover.-,Implementation,-Finding%20sum%20in). Для дальнейшего чтения читателям рекомендуется обратиться к следующим источникам, к которым автор обращался при написании этой статьи.
- [CP-алгоритмы] (https://cp-algorithms.com/data_structures/fenwick.htm)
С помощью этой интересной структуры данных можно решить множество интересных задач. Знаете ли вы какую-либо другую структуру данных, которая также может быть использована для решения этой проблемы? Ответы в комментариях пожалуйста!
Оригинал