17. Дерево Фенвика
Из предыдущего раздела видно, что дерево отрезков программируется достаточно сложно. Еще больших сложностей требует реализация без применения рекурсии. Затраты памяти хотя и пропорциональны величине 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):
ki | f(ki) | ki+1 = f(ki) – 1 |
14 = 11102 | 11102 = 14 | 13 |
13 = 11012 | 11002 = 12 | 11 |
11 = 10112 | 10002 = 8 | 7 |
7 = 1112 | 0002 = 0 | стоп |
Из таблицы следует, что 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−1, AN − 1). Таким образом, построение дерева Фенвика требует O(N logN) времени и O(N) памяти.
Дерево Фенвика достаточно легко обобщается на двумерный, а вообще говоря, и на k-мерный случай. Рассмотрим пример использования дерева Фенвика.
Вешалка. Папа Карло нашел длинную палку в сарае и решил сделать из нее вешалку для ключей. Для этого он по всей длине забивает в палку гвоздики в разных местах. Папа Карло время от времени считает, сколько он уже забил гвоздиков на разных участках палки. Каждое действие Папы Карло — это либо забивание очередного гвоздика в точке с заданной координатой X, либо подсчет числа забитых гвоздиков на отрезке [X, Y]. Все координаты неотрицательные и не превосходят 109, количество действий не более 105.
Буратино, узнав, в чем дело, решил помочь Папе Карло. Буратино подробно записал все действия Папы Карло в процессе изготовления вешалки и теперь хочет проверить расчеты по числу гвоздиков на разных интервалах, сделанные во время работы. Помогите ему в этом. Требуется выдать результаты всех расчетов по числу гвоздиков на разных интервалах.
Если для каждой координаты хранить количество забитых в точку с этой координатой гвоздиков, то подсчет числа гвоздиков на отрезке [X, Y] является запросом Rsq(X, Y) к соответствующему дереву Фенвика. Однако при ограничениях на координаты до 109 такой подход не проходит ни по требуемой памяти, ни по времени работы.
Решением проблемы в данном случае является так называемый “метод сжатия координат”. Отсортируем по координате все точки, встречающиеся во входном файле (их количество не превосходит 2 · 105). Тут надо учитывать как точки, в которые забиваются гвоздики, так и концы отрезков, на которых производится подсчет числа гвоздиков.
Перенумеруем точки в соответствии с их позицией в отсортированном массиве. При этом точкам с одинаковыми координатами присвоим одинаковые номера.
После этого, заменив координаты всех точек их номерами, можно решать задачу с помощью дерева Фенвика, поскольку все номера не превосходят величины 2 · 105.
Задачи для самостоятельного решения
17.1. Инверсии (6)
Задана некоторая перестановка X = (X1, X2, …, XN) чисел от 1 до N. Требуется найти количество инверсий в этой перестановке, то есть количество пар чисел (i, j) таких, что i < j, а Xi > Xj.
Ввод из файла INPUT. TXT. В первой строке задано число N (1 £ N £ 60000). Во второй строке заданы через пробел элементы перстановки X1, X2, …, XN.
Вывод в файл OUTPUT. TXT. В единственной строке выводится количество инверсий.
Пример
Ввод
5
4 3 1 5 2
Вывод
6
17.2. Палиндром (9)
Палиндромом называют слово, которое одинаково читается слева направо и справа налево. Требуется по заданному слову найти минимальное число обменов соседних букв, переводящих это слово в палиндром.
Ввод из файла INPUT. TXT. В первой строке задана длина слова N (1 £ N £ 106). Во второй строке задано слово из N заглавных латинских букв.
Вывод в файл OUTPUT. TXT. В единственной строке должно быть минимальное число перестановок соседних символов, необходимых для получения палиндрома. Если это невозможно, вывести -1.
Пример
Ввод
ABBYY
Вывод
13
Пояснение. К палиндрому приводит следующая последовательность преобразований:
ABBYY
BABYY
BAYBY
BYABY
BYABY
Подсказка
В данной задаче справедливо жадное решение. Если первая и последняя буквы не совпадают, то нужно обменять одну из них на ближайшую к ней букву, которая совпадает с другой буквой. После этого размерность задачи уменьшается на 2.
Это решение имеет трудоемкость O(N2). На самом деле обмены не требуются. Достаточно помечать буквы признаком удаления. Применение дерева Фенвика позволяет добиться трудоемкости O(N log N).
17.3. Красные и синие точки (9)
На плоскости имеются точки красного и синего цвета. Найти минимальный квадрат с параллельными координатным осям сторонами, содержащий точки обоих цветов.
Ввод из файла INPUT. TXT. В первой строке находятся через пробел два числа M и N (1 £ M, N £ 100000) – количество красных и синих точек соответственно. В следующих M строках задаются координаты красных точек в виде двух целых чисел через пробел. Далее в N строках аналогично задаются координаты синих точек. Все координаты не превосходят по модулю 106.
Вывод в файл OUTPUT. TXT. В единственной строке выводится длина стороны минимального квадрата, содержащего точки обоих цветов.
Пример
Ввод
2 3
0 0
3 5
2 3
4 -1
3 2
Вывод
2
Подсказка
Будем двигать вдоль оси X полосу шириной D, параллельную оси Y. При попадании синей точки в полосу будем делать запрос, есть ли в полосе красные точки, отличающиеся по координате Y от данной синей точки не более, чем на D. Для этого введем массив F, каждый элемент которого определяет количество красных точек с определенной ординатой в текущей полосе. Построим дерево Фенвика, соответствующее массиву F. Как его использовать? Как найти минимальное значение D?
