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

Здравствуй, Хабрахабр. Сейчас я хочу рассказать о такой структуре данных как дерево Фенвика. Впервые описанной Питером Фенвиком в 1994 году. Данная структура похожа на дерево отрезков, но проще в реализации.

Что это?


Дерево Фенвика — это структура данных, дерево на массиве, которая обладает следующими свойствами:
• позволяет вычислять значение некоторой обратимой операции F на любом отрезке [L; R] за логарифмическое время;
• позволяет изменять значение любого элемента за O(log N);
• требует памяти O(N);

операция F


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

Простейшая задача


Рассмотрим задачу о нахождения суммы последовательных элементов массива. С учетом того, что будет много запросов, вида (L,R), где требуется найти S(L,R)- сумму всех элементов с a[L] до a[R] включительно.

Простейшим решением данной задачи будет нахождение частичных сумм. После их нахождения запишем эти суммы в массив, в котором sum[i]=a[1]+a[2]...+a[i]. Тогда требуемая в запросе величина S(L,R)=sum[R]-sum[L-1] (sum[0] обычно считают равной нулю, чтобы не рассматривать отдельных случаев).

Недостатки

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

Преимущества

Главным преимуществом данной конструкции является простота реализации и быстрота ответов на запросы (за O(1)).

Применения дерева Фенвика для данной задачи


Введем функцию G(x), которая определена в натуральных числах, и равна x&(x+1) (&- побитовое И). Таким образом, G(x) равна x, если в двоичном разложении x последним стоит 0 (x делится на 2). А если в двоичном разложении x в младших разрядах идет группа единиц, то функция равна x с замененными последними единицами на 0. Можно убедиться на примерах, что это и есть x&(x+1) (смотрите рисунок).
Побитовое И
Теперь будем считать следующие частичные суммы, и записывать их в t[i]=a[G[i]]+a[G[i]+1]…+a[i]. Далее будет показано как находить эти суммы.

Подсчет суммы

Чтобы найти S(L,R), будем искать S(1,L-1) и S(1,R). Напишем функцию, которая при наличии массива t, будет находить S(L,R). В данном случае левый конец не будет включен в сумму, но его легко включить если это требуется в задаче (смотрите код).

const int N=100;
int t[N],a[N];
int sum(int L, int R)
{
	int res=0;
	while (R >= 0) {
		res += t[R];
		R = G( R ) - 1;
	}
	while (L >= 0) {
		res -= t[L];
		L = G(L) - 1;
	}
	return res;
}


Так же стоит заметить, что функция G за каждое применение уменьшает количество единиц в двоичной записи x, как минимум на 1. Из чего следует, что подсчет суммы будет произведен за O(log N).

Модификация элементов

Теперь рассмотрим модификацию элементов. Нам надо научиться быстро изменять частичные суммы в зависимости от того, как изменяются элементы. Мы будем изменять a[k] на величину d. Тогда нам надо изменить элементы массива t[j], для которых верно неравенство G(j)<k<j. Но тут на помощь приходит следующий прием. Утверждается, что все искомые j будут принадлежать последовательности k[i] (смотрите выкладку).
Дерево фенвика
Где под | понимают побитовое ИЛИ.
Побитовое ИЛИ
Несложно заметить, что данная функция строго возрастает и в худшем случае будет применена логарифм раз, так как добавляет каждый раз по одной единице в двоичном разложении числа k.
Напишем функцию, которая будет изменять a[k] элемент на d, и при этом меняет соответствующие частичные суммы.

const int N=100;
int t[N],a[N];
void upd(int k, int d)
{
	a[k]+=d;
	while(k<N)
	{
		t[k]+=d;
		k=(k|(k+1));
	}
}


Инициализация

Теперь заметим, что при первоначальном подсчете массива t, возможна его инициализация нулями. После чего, применяем для каждого из N элементов функцию upd(i,a[i]). Тогда, на первоначальный подсчет уйдет O(N*log N) времени, что больше чем у описанного алгоритма с простыми частичными суммами.

Сравнение с деревом отрезков


Преимущества:
— уже упомянутая простота и скорость
— памяти занимает O(N)

Недостатки:
— функция должна быть обратимой, а это значит, что минимум и максимум это дерево считать не может (за исключением случаев, когда некоторыми данными мы можем пожертвовать).

Заключение


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

Похожие публикации

Комментарии 37
    +4
    Спасибо за статью, действительно, реализация проще дерева отрезков.

    Одного не понял: почему код в картинках? Чтобы не копировали, а сами писали?
      0
      Просто я тут еще не совсем разобрался, и то как вставляется код мне не понравилост (не отыскал подсветку синтаксиса), да и впрочем кода там 5 строк=)
        +6
        Тем не менее читать размазанный код с jpg — занятие не самое приятное.
          +5
          Согласен) Признаю ошибку)
          +4
          <source lang="cpp">
          //Your code goes here
          </source>
          
            +4
            Спасибо, теперь буду знать.
          0
          я ее пытался осилить раз пять, но не смог. вопрос, вводящий меня в ступор: почему оно дерево?
            0
            ваш вопрос логичен) ну можно сказть что эту структуру назвали деревом потому как есть некая связь между элементами массива, и в связи с этим его называют деревом.
              +2
              www.cs.ubc.ca/local/reading/proceedings/spe91-95/spe/vol24/issue3/spe884.pdf

              на третьей странице становится понятно, почему оно дерево =)
                0
                Да, мне когда объясняли дерево Фенвика рисовали похожую картинку.

                Без неё сложно понять, какой вид и смысл имеет функция G.
            0
            Минимум и максимум необратимые операции и их нельзя использовать в качестве операции F.
            А ещё не указан огромный плюс дерева Фенвика: всё это обобщается на многомерные массивы (то есть задачи типа вычислить сумму чисел в прямоугольнике) вообще без усилий.
              0
              Про многомерность я с вами соглашусь а вот по поводу нахождения и максимума и минимуму, мне кажется что вы не правы.
                0
                Я не прав в том, что они необратимы или в том, что нельзя?
                У вас написана формула S(L,R)=sum[R]-sum[L-1]. Перепишите её, пожалуйста, для максимума.
                  0
                  Вы не правы по поводу того что нельзя. Вот тут вроде понятно описано.
                    0
                    Ну там немного другой алгоритм описан. Естественно, можно так модифицировать. Однако, там тоже написано, что для максимума уменьшать значения нельзя.
                  0
                  Кроме того, если вы увеличиваете какой-то элемент, то всё для максимума сработает. А если уменьшаете — нет. То есть если мы хотим вычислять только максимум на начальных отрезках массива и элементы только увеличиваются, то всё сработает. Если нет, то нет. Поправьте, если что.
                –4
                Не хочется критиковать, поэтому попробую конкретный вопрос: а какие функции можно считать на этом дереве, кроме суммы? Что требуется для использования этой структуры для подсчета, например, синуса угла?
                  0
                  Не совсем понятно в каком виде вы хотите считать синус?
                    –2
                    Дерево Фенвика — это структура данных, дерево на массиве, которая обладает следующими свойствами:
                    • позволяет вычислять значение некоторой обратимой операции F на любом отрезке [L; R]

                    Я не сильно математик, но — можем ли мы считать синус, а если нет, то почему?

                    PS. Минус в карму за вопрос, да, это, наверное, правильный подход.
                      0
                      Хорошо вы можете сказать чему будет равен ваш синус от отрезка к примеру (1,2,3,4,1), и тогда я смогу ответить сможет ли данная структура его считать.
                        0
                        Ммм, а отрезок — это именно произвольный набор цифр в интервале, или все-таки есть в нем какая-нибудь логика? Из того, что на википедии написано, я понял, что это именно последовательность чисел от одного конца отрезка до другого. Т.е. если имелся ввиду отрезок от 1 до 4, то это будет 1,2,3,4.

                        Продолжая свои попытки приспособить эту структуру под собственные нужды, к примеру, для подсчета синуса — что насчет такого подхода:

                        Если отрезок это [a,b], то можно ли считать функцию sin(b-a)? Давайте разберемся с возможностью, для начала.

                        PS. Это математический форум? Я кого-то оскорбляю? Я не пытаюсь вести конструктивный диалог, в меру своих сил? Минусовать комментарии и карму — хамство.
                  0
                  t[i]=a[G[i]]+…+a[i]

                    0
                    Извиняюсь, ентер сработал не там.

                    В формуле t[i]=a[G[i]]+…+a[i], возможно, стоит добавить хотя бы член a[G[i] + 1], а то не совсем очевидно, что многоточие означает.

                    В анализе сложности вычисления суммы не совсем верно написано. Функция G, конечно, уменьшает количество единиц. Однако потом отнимается единица и количество единиц опять увеличивается. Так что либо количество единиц в G[x] — 1 больше, чем у x и мы заканчиваем, когда G[x] — 1 = -1, либо количество нулей у G[x — 1] больше, чем у x.
                      0
                      Так всё-таки, какова формула для заполнения массива частичных сумм t? Что должно быть вместо многоточия? А то действительно не очень понятно.
                        0
                        Я же вроде бы добавил еще один элемент к последовательности.
                        t[i]=a[G[i]]+a[G[i]+1]…+a[i] (сумма всех элементов начиная a[G[i]] и до a[i])/
                    0
                    Вообще не очень понятно, что именно имеется в виду под обратимой операцией. По идее, операцией op может быть любая, для которой:
                    op(a, b) = op(op(a, c), op(c + 1, b)). То есть, если мы знаем результаты операций для подотрезков, мы однозначно считаем результат для отрезка. Сумма под это подходит, максимум — минимум подходят, к примеру. Можно хоть произведение считать.
                    А чтобы посчитать сумму в прямоугольнике(2мерный случай), например, надо использовать принцип включения-исключения.
                      0
                      да, такие операции ассоциативными называются
                        +1
                        Обратимость операции означает, что найдётся такая операция F', что a = F'(F(a, b), b). То есть для сложения это вычитание. Для умножения это деление. А вот для максимума и минимума операция F' есть не для всех значений a и b. Например, если я знаю max(a, b) и знаю b, то a всё равно не смогу вычислить, если b = max(a, b).
                        Поэтому, во-первых, алгоритм надо менять, чтобы не использовать фомулу S(L,R)=sum[R]-sum[L-1]: для максимума её нет. А во-вторых, нельзя уменьшать значения, потому что пересчитать массив t мы в таком случае не сможем.
                        0
                        Можно было ещё указать преимущества и недостатки в сравнении с деревом отрезков:

                        Преимущества:
                        — уже упомянутая простота и скорость
                        — памяти занимает не просто O(N), а даже ровно N, то есть нет дополнительных затрат памяти

                        Недостатки:
                        — функция должна быть обратимой, а это значит, что минимум и максимум это дерево считать не может (исправьте определение функции F)

                        Ну и чтобы не дублировать код, можно было представить sum(L, R) в виде разности sum® — sum(L-1) (почти)
                          0
                          sum( R ) // хабрапарсер жжет
                            0
                            Сумма обратима, т.к. зная s+x и x можно вычислить s = (s+x) — x
                            Максимум/минимум не обратим, т.к. зная max(s, x) и x нельзя вычислить s (в общем случае)

                            Примеры обратимых функции: *, xor
                            Необратимых: &, |, min, max
                              0
                              Сейчас подправлю.
                            +4
                            У вас сложный код, как суммы, так и модификации :)
                            Это же все то же самое можно в несколько строчек записать, если чуть видоизменить операцию перехода. Тогда она, тем более, становится одинаковой для обоих циклов — запоминать проще.

                            Сумма на отрезке [1; X]:
                            int sum(int X) {
                                int ans = 0;
                                for (int i = X; i > 0; i -= i & -i)
                                    ans += t[i];
                                return ans;
                            }
                            


                            Обновление в точке A[X] += V:
                            void update(int X, int V) {
                                for (int i = X; i <= N; i += i & -i)
                                    t[i] += V;
                            }
                            

                              –1
                              Посути ничего нового вы не написали, но за другой вариант спасибо.
                                0
                                А я сколько пытался запомнить — каждый раз заново вывожу формулу перехода.

                                Тем более она бывает разной в зависимости от того, как индексировать отрезок: с 0 или с 1.
                              • НЛО прилетело и опубликовало эту надпись здесь
                                  +2
                                  Есть классная статья про деревья Фенвика с картинками (sic!) на топкодере, правда, на английском.

                                Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                Самое читаемое