Министерство образования и науки Российской Федерации
Министерство образования Саратовской области
Национальный исследовательский Саратовский государственный университет имени Н.Г. Чернышевского
Саратовский областной институт развития образования
Комитет по информатизации Саратовской области
Комитет по образованию администрации муниципального образования «Город Саратов»
Автономная некоммерческая организация «Информационные технологии в образовании»
Автономная некоммерческая организация «Научно-исследовательский центр «Образование. Качество. Отрасль»»
IX Всероссийская (с международным участием) научно-практическая конференция
«Информационные технологии в образовании»
«ИТО-Саратов-2017»
2-3 ноября 2017 года, г. Саратов

Дерево Фенвика для решения олимпиадных задач

Саратовский Государственный Университет им. Н.Г. Чернышевского
Рассматривается устройство такой структуры данных, как дерево Фенвика, его применение в решении олимпиадных задач. Описываются особенности реализации, а так же приводится сравнение работы программ с деревом Фенвика и деревом отрезков для решения определенного класса задач.

Дерево Фенвика для решения олимпиадных задач

Курылев Дмитрий Петрович, студент 6 курса, Компьютерная безопасность КНиИТ

Портенко Марина Сергеевна, старший преподаватель КНиИТ

 

Дерево Фенвика - это структура данных, двоичное индексированное дерево на массиве, позволяющее быстро изменять значения в массиве и находить некоторые функции от элементов массива. Впервые описано Питером Фенвиком в 1994 году. [1]

Дерево Фенвика позволяет вычислять значение некоторой обратимой операции на любом отрезке массива за время O (log N), при этом позволяет изменять значение любого элемента также за O (log N). В отличие от других структур данных, например, дерева отрезков, дерево Фенвика требует меньше памяти, а именно ровно столько же, сколько и массив из N элементов. Помимо этого дерево Фенвика легко обобщается на случай многомерных массивов.[2]

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

Пусть дан массив A[0..N-1]. Дерево Фенвика - массив T[0..N-1], в каждом элементе которого хранится сумма некоторых элементов массива A:

Ti = сумма Aj для всех F(i) <= j <= i, где F(i) - некоторая функция.

Рассмотрим псевдокод для двух функций, первая из которых будет вычислять сумму на отрезке [0; R], а вторая изменять значение (увеличивать в ячейке массива).

Несложно посмотреть, как работает функция получения суммы. Вместо того чтобы итерироваться по всем элементам массива A, она движется по массиву T, делая своеобразные «прыжки» через отрезки там, где это возможно. Сначала она прибавляет к ответу значение суммы на отрезке [F(R); R], затем берёт сумму на отрезке [F(F(R)-1); F(R)-1], и так далее, пока не дойдёт до нуля.

int sum (int r)

{

            int result = 0;

            while (r >= 0) {

                        result += t[r];

                        r = f(r) - 1;

            }

            return result;

}

Функция увеличения значения в ячейке массива движется в обратную сторону - в сторону увеличения индексов, обновляя значения суммы Tj только для тех позиций, для которых это нужно, то есть для всех j, для которых F(j) <= i <= j.

void inc (inti, int delta)

{

            для всех j, для которых F(j) <= i<= j

            {

                        t[j] += delta;

            }

}

Очевидно, что от выбора функции F будет зависеть скорость выполнения обеих операций. Сейчас мы рассмотрим функцию, которая позволит достичь логарифмической производительности в обоих случаях.

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

Этому довольно сложному описанию соответствует очень простая формула:

F(X) = X & (X+1), где & - это операция побитового логического "И".

Нетрудно убедиться, что эта формула соответствует словесному описанию функции, данному выше.

Нам осталось только научиться быстро находить такие числа j, для которых F(j) <= i <= j.

Однако нетрудно убедиться в том, что все такие числа j получаются из i последовательными заменами самого правого (самого младшего) нуля в двоичном представлении. Например, для i = 10 мы получим, что j = 11, 15, 31, 63 и т.д.

Как ни странно, такой операции (замена самого младшего нуля на единицу) также соответствует очень простая формула:

H(X) = X | (X+1), где | - это операция побитового логического "ИЛИ".

Тогда рассмотрим, насколько лаконичная реализация получается с использованием описанной функции – псевдокод описанных выше двух функций.[3]

int sum (int r)

{

            int result = 0;

            for (; r >= 0; r = (r & (r+1)) - 1)

                        result += t[r];

            return result;

}

 

void inc (inti, int delta)

{

            for (; i< n; i = (i | (i+1)))

                        t[i] += delta;

}

Сравним время вычисления суммы на разных отрезках массива с помощью дерева Фенвика и дерева отрезков. [4]

Так выглядит участок кода для вычисления запросов и замера времени на языке С++:

for (inti = 0; i< n; i++)

            {

                        a[i] = i;

                        inc(i, a[i]);

            }

 

            int res = 0;

            long long  time = clock();

            int m = 5000000;

            for (inti = 0; i< n; i++) {

                        int a = sum(i);

                        res += a;

            }

 

            time = (clock() - time);

            cout<< time <<endl;

            time = clock();

            for (inti = 0; i< n; i++) {

                        int a = getSum(0, 0, n - 1, 0, i);

                        res += a;

            }

 

time = (clock() - time);

Здесь sum– функция для вычисления суммы в дереве фенвика, getSum–функция для вычисления суммы в дереве отрезков.

 

Размер массива

Время выполнения дерева Фенвика, мс

Время выполнения дерева отрезков, мс

100000

10

21

1000000

32

246

5000000

184

1368

 

Характеристики компьютера: AMDAthlon™ || X2 240 Processor2.80 GHz, ОЗУ8 ГБ.

Можно увидеть, что дерево Фенвика выигрывает в скорости, благодаря своей нерекурсивной структуре, простоте операций и меньшему объему памяти.

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

Список использованных источников
  1. Peter M. Fenwick (1994). «A new data structure for cumulative frequency tables». Software: PracticeandExperience 24 (3): 327-336. DOI:10.1002/spe.4380240306
  2. 2. А. Лахно Дерево Фенвика. Курс «Структуры данных», Московский центр непрерывного математического образования. [Режим доступа] http://informatics.mccme.ru/moodle/course/view.php?id=18
  3. 3. Лисичкин В. Дерево Фенвика [Режим доступа] https://habrahabr.ru/post/112828
  4. 4. Демина Н.А., Портенко М.С.. Использование дерева отрезков для нахождения значений ассоциативной функции на подмассиве. Информационные технологии в образовании: Материалы VII Всерос. научно-практ. конф. – Саратов: ООО «Издательский центр «Наука»», 2015. - С. 39-42. ISBN 978-5-9758-1610-8.
Вид представления доклада  Устное выступление и публикация
Ключевые слова  Дерево Фенвика, Структуры данных, Олимпиадное программирование, Binary Indexed Trees

В статусе «Черновик» Вы можете производить с тезисами любые действия.

В статусе «Отправлено в Оргкомитет» тезисы проходят проверку в Оргкомитете. Статус «Черновик» может быть возвращен тезисам либо если есть замечания рецензента, либо тезисы превышают требуемый объем, либо по запросу участника.

В статусе «Рекомендован к публикации» тезис публикуется на сайте. Статус «Черновик» может быть возвращен либо по запросу участника, либо при неоплате публикации, если она предусмотрена, либо если тезисы превышают требуемый объем.

Статус «Опубликован» означает, что издана бумажная версия тезиса и тезис изменить нельзя. В некоторых крайне редких ситуацих участник может договориться с Оргкомитетом о переводе тезисов в статус «Черновик».

Статус «Отклонен» означает, что по ряду причин, которые указаны в комментариях к тезису, Оргкомитет не может принять тезисы к публикации. Из отклоненных тезис в «Черновики» может вернуть только Председатель программного или председатель оргкомитета.