Дерево Фенвіка (RUS)
Дерево Фенвика – это структура данных на массиве длины n, которая позволяет совершать следующие операции:
1. Найти значение некоторой заданной функции f на любом отрезке [L; R] за время O(log2n);
2. Изменять значение любого элемента массива за O(log2n);
3. Требует O(n) памяти, а именно столько, сколько необходимо для хранения массива из n элементов.
Далее в качестве f будем рассматривать функцию суммирования.
Пусть имеется массив чисел a[0 ... n – 1]. Деревом Фенвика является массив t[0 ... n – 1], в каждом элементе которого хранится сумма некоторых элементов массива а:
где F(i) – некоторая функция. От ее выбора будет зависеть скорость выполнения основных операций (нахождение суммы на отрезке и модификация элемента массива). Нас интересует такой выбор F, при котором указанные операции будут выполняться за логарифмическое время O(log2n).
Определим F(x) = x & (x + 1), где через '&' обозначена операция побитового "и". Рассмотрим двоичную запись числа x и посмотрим на его младший бит. Если он равен 0, то F(x) = x. Иначе число x оканчивается группой из одной или нескольких единиц. Заменим все эти единицы на нули и присвоим полученное число значению F(x).
Пример 1. В следующей таблице приведены примеры вычисления функции F(x).
x | бинарное представление числа x | бинарное представление числа F(x) | F(x) |
14 | 1110 | 1110 | 14 |
31 | 11111 | 00000 | 0 |
47 | 101111 | 100000 | 32 |
75 | 1001011 | 1001000 | 72 |
Упражнение 1. Вычислить F(x), где
a) x = 16; b) x = 19; c) x = 25; d) x = 119; e) x = 127;
Рассмотрим функцию sum(r), которая вычисляет сумму элементов массива a на отрезке [0 .. r]. Вместо того чтобы двигаться по всем элементам массива а, будем двигаться по массиву t, совершая прыжки через отрезки там, где это возможно. Поскольку
t[r] = a[F(r)] + a[F(r) + 1] + … + a[r],
то
sum(r) = (a[0] + a[1] + … + a[F(r) – 1]) + (a[F(r)] + a[F(r) + 1] + … + a[r]) =
= sum(F(r) – 1) + t[r] =
sum(F(F(r) – 1) – 1) + t[F(r) – 1] + t[r] = …
Указанная сумма расписывается до тех пор, пока значение F(…(F(F(r) – 1) – 1) …) не станет равным нулю. То есть sum(r) состоит из сумм элементов массива а на отрезках [F(r); r], [F(F(r) – 1); F(r) – 1] и так далее.
Значение sum(r) можно также записать в виде суммы:
где r0 = r, ri+1 = F(ri) – 1 = (ri & (ri + 1)) – 1.
Пример 2. Рассмотрим процесс вычисления sum(14):
ri | F(ri) | ri+1 = F(ri) – 1 |
14 = 11102 | 11102 = 14 | 13 |
13 = 11012 | 11002 = 12 | 11 |
11 = 10112 | 10002 = 8 | 7 |
7 = 1112 | 0002 = 0 | стоп |
Из таблицы следует, что sum(14) = t14 + t13 + t11 + t7. Или то же самое, что суммируются интервалы: sum(14) = a[14..14] + a[12..13] + a[8..11] + a[0..7].
Упражнение 2. Расписать значение sum(x) в виде суммы
где
a) x = 5; b) x = 11; c) x = 43;
Представить sum(x) в виде суммы интервалов массива а как показано в примере 2.
Следующий рисунок показывает, что хранится в массиве t (дереве Фенвика). Клетка i - ой строки и k - го столбца черная, если a[i] входит в частичную сумму tk, то есть F(k) ≤ i ≤ k.
Аналогично можно утверждать, например, что a[2] входит в качестве слагаемого в t2, t3, t7.
Пример 3. Поскольку F(9) = 8, то t9 = a[8] + a[9].
Так как F(11) = 8, то t11 = a[8] + a[9] + a[10] + a[11].
Упражнение 3. Представить значение tx в виде суммы элементов массива а, если
a) x = 15; b) x = 21; c) x = 47; d) x = 50;
Для дальнейшего изложения материала нам понадобится функция H(x) = x | (x + 1), которая заменяет последний 0 в двоичном представлении числа x на 1. Через '|' здесь обозначена операция побитового "или".
Пример 4. В следующей таблице приведены примеры вычисления функции H(x).
x | бинарное представление числа x | бинарное представление числа x + 1 | H(x) |
14 | 1110 | 1111 | 11112 = 15 |
9 | 1001 | 1010 | 10112 = 11 |
43 | 101011 | 101100 | 1011112 = 47 |
47 | 101111 | 110000 | 1111112 = 63 |
15 | 1111 | 10000 | 111112 = 31 |
Упражнение 4. Вычислить H(x), где
a) x = 16; b) x = 21; c) x = 31; d) x = 60; e) x = 1;
Рассмотрим, как имея число i, быстро находить такие числа k, что F(k) ≤ i ≤ k. Все такие числа k получаются из i последовательными заменами самого правого (младшего) нуля в двоичном представлении.
Пример 5. Пусть i = 8 = 10002. Найдем такие k, для которых F(k) ≤ i ≤ k.
Последовательно заменяя последний 0 в двоичном представлении i на 1, получим числа: 10012 = 9, 10112 = 11, 11112 = 15, 111112 = 31, 1111112 = 63 и так далее. Следовательно a[8] будет содержаться в t8, t9, t11, t15, t31t63 и так далее.
Пусть i = 53 = 1101012. Аналогично заменяя последовательно по одному последнему нулю, получим числа: 1101112 = 55, 1111112 = 63, 11111112 = 127 и так далее. Следовательно a[53] содержится в t53, t55, t63, t127 и так далее.
Упражнение 5. Для каждого из следующих значений i найти такие k, для которых F(k) ≤ i ≤ k:
a) i = 4; b) i = 11; c) i = 25;
Для увеличения значения a[i] на delta необходимо добавить delta ко всем tk, в которые входит a[i] в качестве слагаемого. Например, для увеличения a[8] на 1, необходимо прибавить 1 к t8, t9, t11, t15, t31, … .
Таким образом, для выполнения операции a[i] = a[i] + delta необходимо прибавить delta к
где k0 = i, kj+1 = H(kj) = kj | (kj + 1). Цикл добавления delta завершается как только kp+1 станет большим n – 1.
Пример 6. Пусть имеется массив чисел а длины n = 100 (ячейки массива пронумерованы от 0 до 99). Необходимо добавить единицу к a[17]. Какие элементы массива t необходимо увеличить на единицу?
Действуя таким же образом, как и в примере 5, запишем число 17 в двоичном коде: 17 = 100012, то есть k0 = 17, и первым значением которое надо увеличить на 1, будет t17. Остальные шаги алгоритма представлены в таблице:
j | kj | kj+1 = H(kj) = kj | (kj + 1) | увеличиваемое значение |
0 | 17 = 100012 | 19 = 100112 | t17 |
1 | 19 = 100112 | 23 = 101112 | t19 |
2 | 23 = 101112 | 31 = 111112 | t23 |
3 | 31 = 111112 | 63 = 1111112 | t31 |
4 | 63 = 1111112 | 127 = 11111112 | t63 |
5 | 127 = 11111112 | cтоп, так как k5 = 127 > 99 = n – 1 |
Упражнение 6. Пусть имеется массив чисел а длины n = 150 (ячейки массива пронумерованы от 0 до 149). Необходимо добавить единицу к a[41]. Какие элементы массива t необходимо увеличить на единицу?
Далее представлены функции, работающие с деревом Фенвика.
vector < int > t;
int n;
// инициализация массива t - дерева Фенвика
void init (int nn)
{
n = nn;
t.assign (n, 0);
}
// a[0] + a[1] + ... + a[r]
int sum (int r)
{
int result = 0;
for (; r >= 0; r = (r & (r+1)) - 1)
result += t[r];
return result;
}
// a[i] = a[i] + delta
void inc (int i, int delta)
{
for (; i < n; i = (i | (i+1)))
t[i] += delta;
}
// a[l] + a[l+1] + ... + a[r]
int sum (int l, int r)
{
return sum (r) - sum (l-1);
}
СПИСОК ЛИТЕРАТУРЫ
- http://corum.mephist.ru/index.php?showtopic=17160
- http://e-maxx.ru/algo/fenwick_tree
- http://informatics.mccme.ru/moodle/mod/book/view.php?id=491
ОТВЕТЫ К УПРАЖНЕНИЯМ
1.a) 16, b) 16, c) 24, d) 112, e) 0.
2.a) x = 5.
ri | F(ri) | ri+1 = F(ri) – 1 |
5 = 1012 | 1002 = 4 | 3 |
3 = 112 | 002 = 0 | стоп |
sum(5) = t5 + t3. Или sum(5) = a[4..5] + a[0..3].
b) x = 11.
ri | F(ri) | ri+1 = F(ri) – 1 |
11 = 10112 | 10002 = 8 | 7 |
7 = 1112 | 0002 = 0 | стоп |
sum(11) = t11 + t7. Или sum(11) = a[8..11] + a[0..7].
c) x = 43.
ri | F(ri) | ri+1 = F(ri) – 1 |
43 = 1010112 | 1010002 = 40 | 39 |
39 = 1001112 | 1000002 = 32 | 31 |
31 = 111112 | 000002 = 0 | стоп |
sum(43) = t43 + t39 + t31. Или sum(43) = a[40..43] + a[32..39] + a[0..31].
3. a) F(15) = 0, поэтому t15 = a[0] + a[1] + … + a[14] + a[15].
b) F(21) = 20, поэтому t21 = a[20] + a[21].
c) F(47) = 32, поэтому t47 = a[32] + a[33] + … + a[46] + a[47].
d) F(50) = 50, поэтому t50 = a[50].
4.
x | бинарное представление числа x | бинарное представление числа x + 1 | H(x) |
16 | 10000 | 10001 | 100012 = 17 |
21 | 10101 | 10110 | 101112 = 23 |
31 | 11111 | 100000 | 1111112 = 63 |
60 | 111100 | 111101 | 1111012 = 61 |
1 | 1 | 10 | 112 = 3 |
5.a) i = 4 = 1002: 1012 = 5, 1112 = 7, 11112 = 15, 111112 = 31 и так далее.
a[4] содержится в t4, t5, t7, t15, t31 и так далее.
b) i = 11 = 10112: 11112 = 15, 111112 = 31 и так далее.
a[11] содержится в t11, t15, t31 и так далее.
c) i = 25 = 110012: 110112 = 27, 111112 = 31 и так далее.
a[25] содержится в t25, t27, t31 и так далее.
6.
j | kj | kj+1 = H(kj) = kj | (kj + 1) | увеличиваемое значение |
0 | 41 = 1010012 | 43 = 1010112 | t41 |
1 | 43 = 1010112 | 47 = 1011112 | t43 |
2 | 47 = 1011112 | 63 = 1111112 | t47 |
3 | 63 = 1111112 | 127 = 11111112 | t63 |
4 | 127 = 11111112 | 255 = 111111112 | t127 |
5 | 255 = 111111112 | cтоп, так как k5 = 255 > 149 = n – 1 |