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

Из предыдущего раздела видно, что дерево отрезков программируется достаточно сложно. Еще больших сложностей требует реализация без применения рекурсии. Затраты памяти хотя и пропорциональны величине N, но коэффициент пропорциональности k = 4 даже в простейшем случае.

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

Пусть задан массив A из N чисел: A0, A1,..., AN-1. C помощью дерева Фенвика можно выполнять две операции:

Rsq(I, J) – нахождение суммы элементов массива A в диапазоне индексов от I-го до J-го;

Update(K, D) – изменение K-го элемента массива A на величину D.

В отличие от дерева отрезков не обеспечивается операция Rmq – нахождение максимума элементов массива в заданном диапазоне индексов и операция интервальной модификации элементов.

Как уже говорилось выше, при простейшей работе с массивом A запрос Rsq(I, J) работает за время O(j − i + 1), что в общем случае составляет порядок O(N), а Update(K, D) - за O(1). C помощью дерева Фенвика каждая из указанных операций выполняется за время O(logN).

На практике дерево Фенвика представляет собой массив B из N чисел: B0, B1, …, BN -1, в k-м элементе которого хранится сумма элементов массива A с f(k)-го по k-й:

,

где f(k) = k & (k + 1). Под ”& ” имеется в виду операция побитового И (AND).

Рассмотрим двоичную запись числа k и посмотрим на его младший бит. Если он равен нулю, то f(k) = k. Иначе число k оканчивается группой из одной или нескольких единиц. Заменим все эти единицы на нули и присвоим полученное число значению f(k).

Следующий рисунок показывает, что хранится в массиве B. Клетка i - ой строки и k - го столбца черная, если Ai входит в частичную сумму Bk, то есть f(k) ≤ i≤ k.

Из рисунка видно, например, что A2 входит в качестве слагаемого в B2, B3 и B7.

Рассмотрим, как с помощью дерева Фенвика реализуются операции ответа на запрос Rsq(i, j) о частичной сумме элементов массива A с i-го по j-й.

Заметим, что Rsq(i, j) = Rsq(0, j) − Rsq(0, i − 1). Для i = 0 положим Rsq(0, − 1) = 0. Таким образом, для ответа на запрос Rsq(i, j) достаточно научиться отвечать на запрос вида Rsq(0, k), который для краткости обозначим Rsq(k).

Вместо того, чтобы проходить по всем элементам массива A, будем двигаться по массиву B, совершая прыжки через отрезки там, где это возможно. Поскольку

Bk = Af(k) + Af(k) + 1 + … + Ak,

то

Rsq (k) = (A0 + A1 + … + Af(k) – 1) + (Af(k) + Af(k) + 1 + … + Ak) =

= Rsq (f(k) – 1) + B k = Rsq(f(f(k) – 1) – 1) + Bf(k) – 1 + Bk = …

Указанная сумма расписывается до тех пор, пока значение f(…(f(f(k) – 1) – 1) …) не станет равным нулю. То есть Rsq(k) состоит из сумм элементов массива Aна отрезках [f(k); k], [f(f(k) – 1); f(k) – 1] и так далее.

Рассмотрим, например, процесс вычисления Rsq(14):

Из таблицы следует, что Rsq(14) = B14 + B13 + B11 + B7. Или то же самое, что суммируются интервалы: Rsq(14) = A[14..14] + A[12..13] + A[8..11] + A[0..7].

Ниже приводится текст функции, реализующий ответ на запрос Rsq(k).

Function Rsq(k: LongInt): LongInt;

Var

res: LongInt;

Begin

res: =0;

While (k > = 0) do

begin

inc(res, B[k]);

k: = k and (k + 1) - 1;

end;

Rsq: =res;

End;

Для оценки времени работы данной функции необходимо оценить количество итераций цикла While в строках, то есть количество слагаемых в итоговой сумме. Количество слагаемых на единицу больше количества единичных битов в числе f(k). Переход к каждому следующему индексу ”выбивает” ровно по одному единичному биту из числа f(ki). А поскольку в худшем случае количество единичных бит в f(k) может быть порядка O(logN), то и ответ на запросRsq(k) в худшем случае требует порядка O(logN) времени.

При изменении k-го элемента массива A необходимо соответствующим образом изменить элементы массива B, в определении которых частичные суммы содержат элемент Ak. То есть для выполнения операции Update(K, D) нужно прибавить D к тем элементам Bi, для которых f(i) ≤ k ≤ i.

Рассмотрим, как имея число k, быстро находить такие числа i, что f(i) ≤ k ≤ i. Оказывается, что все такие числа i получаются из k последовательными заменами самого правого (младшего) нуля в двоичном представлении.

Пусть, например, k = 8 = 10002. Последовательно заменяя последний 0 в двоичном представлении k на 1, получим числа: 10012 = 9, 10112 = 11, 11112 = 15, 111112 = 31, 1111112 = 63 и т. д. Следовательно A8 будет содержаться в B8, B9, B11, B15, B31 B63 и т. д.

Пусть k = 53 = 1101012. Аналогично заменяя последовательно по одному последнему нулю, получим числа: 1101112 = 55, 1111112 = 63, 11111112 = 127 и т. д. Следовательно, A53 содержится в B53, B55, B63, B127 и т. д.

Введем функцию H(k) = k | (k + 1), которая заменяет последний нуль в двоичном представлении числа k на единицу. Под " |” имеется в виду операция побитового ИЛИ. Для выполнения операции Update(K, D) необходимо прибавить D к элементам массива B с индексами k0, k1, …, kp, где k0 = k, kj+1 = H(kj) = kj | (kj + 1). Цикл добавления D завершается как только kp+1 станет большим N.

Ниже приводится текст процедуры, реализующий операцию Update(K, D).

Procedure Update(k, d: LongInt);

Begin

While (k < N) do

begin

inc(B[k], D);

k: = k or (k + 1);

end;

End;

В силу того, что длина последовательности ki составляет O(logN) в худшем случае, количество итераций цикла While, а значит и время работы процедуры составляет O(logN).

Для построения дерева Фенвика по заданному массиву A достаточно обнулить массив B и N раз выполнить операцию изменения элементов: Update(0, A0), Update(1, A1), …, Update(N−

Вешалка. Папа Карло нашел длинную палку в сарае и решил сделать из нее вешалку для ключей. Для этого он по всей длине забивает в палку гвоздики в разных местах. Папа Карло время от времени считает, сколько он уже забил гвоздиков на разных участках палки. Каждое действие Папы Карло — это либо забивание очередного гвоздика в точке с заданной координатой X, либо подсчет числа забитых гвоздиков на отрезке [X, Y]. Все координаты неотрицательные и не превосходят 109, количество действий не более 105.

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

Если для каждой координаты хранить количество забитых в точку с этой координатой гвоздиков, то подсчет числа гвоздиков на отрезке [X, Y] является запросом Rsq(X, Y) к соответствующему дереву Фенвика. Однако при ограничениях на координаты до 109такой подход не проходит ни по требуемой памяти, ни по времени работы.

Решением проблемы в данном случае является так называемый " метод сжатия координат”. Отсортируем по координате все точки, встречающиеся во входном файле (их количество не превосходит 2 · 105). Тут надо учитывать как точки, в которые забиваются гвоздики, так и концы отрезков, на которых производится подсчет числа гвоздиков.

Перенумеруем точки в соответствии с их позицией в отсортированном массиве. При этом точкам с одинаковыми координатами присвоим одинаковые номера.

После этого, заменив координаты всех точек их номерами, можно решать задачу с помощью дерева Фенвика, поскольку все номера не превосходят величины 2 · 105.