Дерево фенвика решение задач

Дерево Фенвика с модификацией на отрезке

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

1. Постановка задачи

1. Модификация — прибавить d к каждому элементу отрезка [l, r]
2. Сумма — вычислить сумму элементов отрезка [l, r]

2. Описание решения

Нетрудно заметить, что оба вида запросов можно «облегчить» до отрезка [0, r], разбивая отрезок [l, r] на два префикса. Как и для дерева отрезков, заведём второй массив, в котором будем хранить сколько надо прибавить ко всем числам этого отрезка.

Создадим класс Fenwick с прототипами будущих методов.

В первом конструкторе достаточно выделить память и обнулить элементы массива. А во втором ещё пройдёмся по массиву a и прорелаксируем значения в дереве.

Fenwick::Fenwick(int n) < N = n; m = new int[N]; mt = new int[N]; memset(m, 0, sizeof(int)*N); memset(mt, 0, sizeof(int)*N); >Fenwick::Fenwick(int a[], int n) < N = n; m = new int[N]; mt = new int[N]; memset(m, 0, sizeof(int)*N); memset(mt, 0, sizeof(int)*N); for(int i=0;i> 

Рассмотрим теперь операцию изменения. Предположим пришёл запрос «прибавить 1 к элементам отрезка [0, 9]». Этот отрезок полностью покрывается непересекающимися отрезками [0, 7] и [8, 9], поэтому в 7 и 9 элементы массива mt прибавляем 1. Но есть отрезки, содержащие [0, 9] (или его часть) в качестве подотрезка. Все они располагаются справа. Для них необходимо изменить значение в массиве m на столько, сколько элементов отрезка [0, 9] они содержат. То есть в m[11] прибавить 2, а к m[15] — 10.

Из рисунка видно, что перемещения происходят по тем же законам, что и в тривиальной реализации дерева Фенвика, поэтому сразу перейдём к коду.

void Fenwick::add_range(int r, int d)< if(r<0) return ; for(int i=r;i>=0;i=(i&(i+1))-1) mt[i] += d; for(int i=r|(r+1);i void Fenwick::add_range(int l, int r, int d)

Для суммы на префиксе подойдёт та же картинка с тем лишь пояснением, что для зелёных элементов необходимо прибавить и m, и mt, а для синих только mt (то есть учесть большие накрывающие отрезки).

int Fenwick::sum(int r)< if(r<0) return 0; int res = 0; for(int i=r;i>=0;i=(i&(i+1))-1) res += m[i] + mt[i]*(i-(i&(i+1))+1); for(int i=r|(r+1);i int Fenwick::sum(int l, int r)

3. Итоги

Нам удалось получить структуру данных с инициализацией за O(N), модификацией и суммой на отрезке за O(logN). На рандомном тесте с 10000000 элементов и 10000000 запросов получил такие цифры:

Структура данных	Инициализация	Модификация	Сумма
Fenwick	0.13 с	9.12 с	8.90 с
RSQ (реализация с e-maxx)	0.25 с	17.13 с	13.53 с

Источник

Дерево Фенвика для максимума

Про дерево Фенвика многие знают. Многие его используют. Однако считается, что деревом Фенвика нельзя находить максимум/минимум.
Мол, эта операция не имеет обратной. Однако небольшие изменения алгоритма позволяют нам решить и эту задачу тоже.
NB: Статья написана для тех, кто знает, что такое дерево Фенвика и описывает его модификацию для максимума.Тем, кто не знает, что такое дерево Фенвика, рекомендуется прочитать об этом где-нибудь, хоть в Кормене, хоть в статье на хабре.

1.Постановка задачи

Есть массив. К нему выполняется много много запросов как на нахождение максимума на интервале, так и на увеличение значения в одной из ячеек.
Да, именно на увеличение. Значение в ячейке уменьшать нельзя, иначе алгоритм не работает.

2.Собственно алгоритм

Создадим класс — FenwickTree, который будет иметь два метода — Update(int i,double cost) и Max(int left,int right) — соответственно апдейт значения в i-ой ячейке и поиск максимума на интервале.
Как всегда в дереве Фенвика, нам понадобится k-минимальное число, такое что pow(2,k)>=a.size()
Хранить дерево будем в массиве.

Главное отличие от обычного дерева Фенвика

Нам понадобятся два массива, а не один, как в обычном дереве Фенвика, назовем их left и right
В i-й ячейке массива left будем хранить максимум на отрезке [i-G(i)+1,i], в i-й ячейке массива right— максимум на отрезке [i,i+G(i)-1] при i

class FenwickTree < private: vectora; vector left; vector right; public: void PreProc(); double Max(int left,int right); void Update(int i,double cost); >; 

Функция PreProc() нужна, чтобы добавить в дерево наши первоначальные данные и выглядит ужасающе сложно:

Обращаю внимание, именно i+1, т.к. наша функция перехода в массивах G(x) = x-(x&(x-1)) работает для x>0
Теперь напишем функцию Update:

void FenwickTree::Update(int r,double cost) < a[r-1]=cost; int i=r; while(i<=pow(2.0,double(k))) < left[i]=max(left[i],cost); i=i+G(i); >i=r; while(i>0) < right[i]=max(right[i],cost); i=i-G(i); >> 

double FenwickTree::Max(int l,int r) < double res=0; int i=l; while(i+G(i)<=r) < res=max(res,right[i]); i=i+G(i); >if(a[i-1]>res) ans=i; res=max(res,a[i-1]); i=r; while(i-G(i)>=l) < res=max(res,left[i]); i=i-G(i); >return res; > 

Как видите, дерево Фенвика для максимума можно написать очень просто и очень быстро(что иногда критично).

Источник

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

Здравствуй, Хабрахабр. Сейчас я хочу рассказать о такой структуре данных как дерево Фенвика. Впервые описанной Питером Фенвиком в 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.
Напишем функцию, которая будет изменять a[k] элемент на d, и при этом меняет соответствующие частичные суммы.

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

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

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

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

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

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

Заключение

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

Источник