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

Дерево Фенвіка — це структура даних, дерево неявно втілене на масиві, що має такі властивості:

1. Дозволяє обчислювати значення деякої оборотної операції G на будь-якому відрізку [L; R] за час O(log N);
2. Дозволяє змінювати значення будь-якого елемента за O(log N);
3. Вимагає O(N) пам'яті, а точніше, рівно стільки ж, скільки і масив з N елементів;
4. Легко узагальнюється на випадок багатовимірних масивів.

Структура даних нагадує дерево відрізків, однак простіша в реалізації.

Найпоширеніше застосування дерева Фенвіка — обчислення суми на відрізку, тобто функція G (X1, …, Xk) = X1 + … + Xk.

Дерево Фенвіка було вперше описано в статті «A new data structure for cumulative frequency tables» (Peter M. Fenwick, 1994).

Опис алгоритму

Для простоти опису ми припускаємо, що операція G, за якою ми будуємо дерево — це сума.

Нехай дано масив A[0..N-1]. Дерево Фенвіка — масив T[0 .. N-1], в кожному елементі якого зберігається сума деяких елементів масиву A:

T_i = сума A_j для всіх F(i)<=j<=i

де F(i) — деяка функція, яку ми визначимо трохи пізніше.

Тепер ми вже можемо написати псевдокод для функції обчислення суми на відрізку [0;R] і для функції зміни осередки:

int sum (int r)
{
	int result = 0;
	while (r >= 0) {
		result += t[r];
		r = f(r) - 1;
	}
	return result;
}

void inc (int i, int delta)
{
	для всіх j, для яких F(j) <= i <= j
	{
		t[j] += delta;
	}
}

Функція sum працює таким чином. Замість того щоб йти по всіх елементах масиву A, вона рухається по масиву T, роблячи «стрибки» через відрізки там, де це можливо. Спочатку вона додає до відповіді значення суми на відрізку [F(R);R], потім бере суму на відрізку [F(F(R)-1);F(R)-1], і так далі, поки не дійде до нуля.

Функція inc рухається у зворотний бік — у бік збільшення індексів, оновлюючи значення суми T_j тільки для тих позицій, для яких це потрібно, тобто для всіх j, для яких F(j)<=i<=j.

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

Визначимо значення F(X) наступним чином. Розглянемо двійкову запис цього числа і подивимося на його молодший біт. Якщо він дорівнює нулю, то F(X)=X. Інакше двійкове подання числа X закінчується на групу з однієї або декількох одиниць. Замінимо всі одиниці з цієї групи на нулі, і привласнимо отримане число значенню функції F(X).

Цьому досить складного опису відповідає дуже проста формула:

F(X) = X & (X+1)

де & — це операція побітового логічного «І» (кон'юнкція).

Втілення дерева Фенвіка для суми для одновимірного випадку

vector<int> t;
int n;

void init (int nn)
{
	n = nn;
	t.assign (n, 0);
}

int sum (int r)
{
	int result = 0;
	for (; r >= 0; r = (r & (r+1)) - 1)
		result += t[r];
	return result;
}

void inc (int i, int delta)
{
	for (; i < n; i = (i | (i+1)))
		t[i] += delta;
}

int sum (int l, int r)
{
	return sum (r) - sum (l-1);
}

void init (vector<int> a)
{
	init ((int) a.size());
	for (unsigned i = 0; i < a.size(); i++)
		inc (i, a[i]);
}

Втілення дерева Фенвіка для мінімуму для одновимірного випадку

Слід відразу зазначити, що, оскільки дерево Фенвіка дозволяє знайти значення функції в довільному відрізку [0;R], то ми ніяк не зможемо знайти мінімум на відрізку [L;R], де L>0. Далі, всі зміни значень повинні відбуватися тільки у бік зменшення (знову ж, оскільки ніяк не вийде звернути функцію min). Це значення обмежене.

vector<int> t;
int n;

const int INF = 1000*1000*1000;

void init (int nn)
{
	n = nn;
	t.assign (n, INF);
}

int getmin (int r)
{
	int result = INF;
	for (; r >= 0; r = (r & (r+1)) - 1)
		result = min (result, t[r]);
	return result;
}

void update (int i, int new_val)
{
	for (; i < n; i = (i | (i+1)))
		t[i] = min (t[i], new_val);
}

void init (vector<int> a)
{
	init ((int) a.size());
	for (unsigned i = 0; i < a.size(); i++)
		update (i, a[i]);
}

Втілення дерева Фенвіка для суми для двовимірного випадку

Як уже зазначалося, дерево Фенвіка легко узагальнюється на багатовимірний випадок.

vector <vector <int> > t;
int n, m;

int sum (int x, int y)
{
	int result = 0;
	for (int i = x; i >= 0; i = (i & (i+1)) - 1)
		for (int j = y; j >= 0; j = (j & (j+1)) - 1)
			result += t[i][j];
	return result;
}

void inc (int x, int y, int delta)
{
	for (int i = x; i < n; i = (i | (i+1)))
		for (int j = y; j < m; j = (j | (j+1)))
			t[i][j] += delta;
}

Посилання

• Дерево Фенвика — MAXimal [Архівовано 1 серпня 2016 у Wayback Machine.] (рос.)