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

   Дерево Фенвика – это структура данных на массиве длины n, которая позволяет совершать следующие операции:

   1. Найти значение некоторой заданной функции f на любом отрезке [L; R] за время O(log₂n);

   2. Изменять значение любого элемента массива за O(log₂n);

   3. Требует O(n) памяти, а именно столько, сколько необходимо для хранения массива из n элементов.

   Далее в качестве  f будем рассматривать функцию суммирования.

   Пусть имеется массив чисел a[0 ... n – 1]. Деревом Фенвика является массив t[0 ... n – 1], в каждом элементе которого хранится сумма некоторых элементов массива а:

где F(i) – некоторая функция. От ее выбора будет зависеть скорость выполнения основных операций (нахождение суммы на отрезке и модификация элемента массива). Нас интересует такой выбор F, при котором указанные операции будут выполняться за логарифмическое время O(log₂n).

   Определим F(x) = x & (x + 1), где через '&' обозначена операция побитового "и". Рассмотрим двоичную запись числа x и посмотрим на его младший бит. Если он равен 0, то F(x) = x. Иначе число x оканчивается группой из одной или нескольких единиц. Заменим все эти единицы на нули и присвоим полученное число значению F(x). 

   Пример 1. В следующей таблице приведены примеры вычисления функции F(x).

   Упражнение 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) можно также записать в виде суммы:

   где r₀ = r, r_i+1 = F(r_i) – 1 = (r_i & (r_i + 1)) – 1.

   Пример 2. Рассмотрим процесс вычисления sum(14):

   Из таблицы следует, что sum(14) = t₁₄ + t₁₃ + t₁₁ + t₇. Или то же самое, что суммируются интервалы: 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] входит в частичную сумму t_k, то есть F(k) ≤ i ≤ k.

   Аналогично можно утверждать, например, что a[2] входит в качестве слагаемого в t₂, t₃, t₇.

   Пример 3. Поскольку F(9) = 8, то t₉ = a[8] + a[9].

   Так как F(11) = 8, то t₁₁ = a[8] + a[9] + a[10] + a[11].

   Упражнение 3. Представить значение t_x в виде суммы элементов массива а, если

a) x = 15;    b) x = 21;    c) x = 47;    d) x = 50;

   Для дальнейшего изложения материала нам понадобится функция H(x) = x | (x + 1), которая заменяет последний 0 в двоичном представлении числа  x на 1. Через '|' здесь обозначена операция побитового "или".

   Пример 4. В следующей таблице приведены примеры вычисления функции H(x).

   Упражнение 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 = 1000₂. Найдем такие k, для которых F(k) ≤ i ≤ k.

   Последовательно заменяя последний 0 в двоичном представлении i на 1, получим числа: 1001₂ = 9,  1011₂ = 11, 1111₂ = 15, 11111₂ = 31, 111111₂ = 63  и так далее. Следовательно a[8] будет содержаться в t₈, t₉, t₁₁, t₁₅, t₃₁t₆₃ и так далее.

   Пусть i = 53 = 110101₂. Аналогично заменяя последовательно по одному последнему нулю, получим числа: 110111₂ = 55,  111111₂ = 63, 1111111₂ = 127  и так далее. Следовательно a[53] содержится в t₅₃, t₅₅, t₆₃, t₁₂₇ и так далее.

   Упражнение 5. Для каждого из следующих значений i найти такие k, для которых F(k) ≤ i ≤ k:

a) i = 4;    b) i = 11;    c) i = 25;

   Для увеличения значения a[i] на delta необходимо добавить delta ко всем t_k, в которые входит a[i] в качестве слагаемого. Например, для увеличения a[8] на 1, необходимо прибавить 1 к t₈, t₉, t₁₁, t₁₅, t₃₁, … .

   Таким образом, для выполнения операции a[i] = a[i] + delta необходимо прибавить delta к

где k₀ = i, k_j+1 = H(k_j) = k_j | (k_j + 1). Цикл добавления delta завершается как только k_p+1 станет большим n – 1.

   Пример 6. Пусть имеется массив чисел а длины n = 100 (ячейки массива пронумерованы от 0 до 99). Необходимо добавить единицу к a[17]. Какие элементы массива t необходимо увеличить на единицу?

   Действуя таким же образом, как и в примере 5, запишем число 17 в двоичном коде: 17 = 10001₂, то есть k₀ = 17, и первым значением которое надо увеличить на 1, будет t₁₇. Остальные шаги алгоритма представлены в таблице:

   Упражнение 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);

}

СПИСОК ЛИТЕРАТУРЫ

1. http://corum.mephist.ru/index.php?showtopic=17160
2. http://e-maxx.ru/algo/fenwick_tree
3. 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.

   sum(5) = t₅ + t₃. Или sum(5) = a[4..5] + a[0..3].

   b) x = 11.

   sum(11) = t₁₁ + t₇. Или sum(11) = a[8..11] + a[0..7].

   c) x = 43.

   sum(43) = t₄₃ + t₃₉ + t₃₁. Или sum(43) = a[40..43] + a[32..39] + a[0..31].

   3. a) F(15) = 0, поэтому t₁₅ = a[0] + a[1] + … + a[14] + a[15].

   b) F(21) = 20, поэтому t₂₁ = a[20] + a[21].

   c) F(47) = 32, поэтому t₄₇ = a[32] + a[33] + … + a[46] + a[47].

   d) F(50) = 50, поэтому t₅₀ = a[50].

4.

5.a) i = 4 = 100₂: 101₂ = 5, 111₂ = 7, 1111₂ = 15, 11111₂ = 31 и так далее.

        a[4] содержится в t₄, t₅, t₇, t₁₅, t₃₁ и так далее.

    b) i = 11 = 1011₂: 1111₂ = 15, 11111₂ = 31 и так далее.

        a[11] содержится в t₁₁, t₁₅, t₃₁ и так далее.

    c) i = 25 = 11001₂: 11011₂ = 27, 11111₂ = 31 и так далее.

        a[25] содержится в t₂₅, t₂₇, t₃₁ и так далее.

6.