вторник, 1 февраля 2011 г.

Дерево Фенвика (Fenwick tree)

Изумительная структура данных. Классический пример гениальной мысли.

Дерево Фенвика позволяет за O(log(N)) определять значение обратимой функции на интервале массива [L,R].

Обратимая функция:
1) Сумма на интервале    [L,R]
2) Минимум на интервале 
3) Максимум на интервале

Теория:

1) Статья Алексея Лахно
2) Статья Максима Иванова.

Осознать сам подход поможет это изображение:

Запомним два правила.
1) При добавлении нового элемента делаем подъем вверх

2) При подсчете суммы элементов в интервале [0,X] делаем спуск вниз

Реализация:

  1. vector<int> b(MAX_VALUE+1);
  2.  
  3. void add(int x, int delta) {
  4.   for (; x <= MAX_VALUE; x = x | (x + 1))
  5.     b[x] += delta;
  6. }
  7.  
  8. int sum(int x) {
  9.   int res = 0;
  10.   for (; x >= 0; x = (x & (x + 1)) - 1)
  11.     res += b[x];
  12.   return res;
  13. }
* This source code was highlighted with Source Code Highlighter.

Практика:
Задача: 1028 (acm.timus.ru)
Решение: здесь

P.S: Не забываем, что дерево Фенвика легко интерпретируется на многомерный случай

Комментариев нет:

Отправить комментарий