Быстрый переход Новости Основы файлового ввода вывода Структуры данных Теория графов Геометрия - основы планиметрии Математические алгоритмы Геометрия - основы стереометрии

• Новости
• Алгоритмы
  • Структуры данных
  • Теория графов
  • Геометрия
  • Стереометрия
  • Математика

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

Дан массив чисел
Необходимо ответить на запросы о состоянии массива (например сумма элементов с i по j) и обработать события по его изменению (увеличить на x i-тый элемент)

Создадим дополнительный массив p. Пусть p[i] равно сумме всех элементов массива с i - I[i] + 1 по i, где I[x] - максимальная степень двойки, являющаяся делителем x.

I[0] = 1
I[1] = 1
I[2] = 2
I[3] = 1
I[4] = 4
...

p[0] = a[0]
p[1] = a[1]
p[2] = a[1] + a[2]
...
p[10] = a[9] + a[10]
p[11] = a[11]
p[12] = a[9] + a[10] + a[11] + a[12]
...


Несложно увидить, что сумму элементов от 0 по i можно найти так:
while (i >= 0)
{
    sum += p[i];
    i -= I[i];
}

Если мы увеличим на x i-тый элемент, то необходимо увеличить все p[j], которые содержат a[i]. Рассмотрев примеры можно прийти к выводу, что последовательность всех j строится следующим образом:
j₀ = i
j₁ = j₀ + I[j₀]
j₂ = j₁ + I[j₁]
...

Очевидно, что и запрос и обработка события имеют асимптотику O(log n).
Замечу, что дерево Фенвика можно легко реализовать на двумерный случай. Для этого необходимо просто добавить в функции обработки запроса и события ещё одну переменную (x, y) и работать с ними аналогично.


Листинг С++

class fenwick_tree
{
private :
   int n;
   int *I;
   int *p;
   
public:   
   fenwick_tree (int _n = 1)
   {
      int i, j;
      n = _n;
      
      I = new int[n];
      I[0] = 1;
      for (i = 1; i < n; ++ i)
         if (i & 1)
            I[i] = 1;
         else
            I[i] = I[i >> 1] << 1;
      
      p = new int[n];
      for (i = 0; i < n; ++ i)
         p[i] = 0;
   }
   
   int sum (int r)
   {
      int s = 0;
      int i = r;
      while (i >= 0)
      {
         s += p[i];
         i -= I[i];
      }
      return s;
   }
   
   int sum (int l, int r)
   {
      return sum (r) - (l == 0 ? 0 : sum (l - 1));
   }
   
   void add (int _i, int x)
   {
      int i = _i;
      if (i == 0)
      {
         p[0] += x;
         return ;
      }
      while (i < n)
      {
         p[i] += x;
         i += I[i];
      }
   }
};

13:55
04.02.2010