Инкрементный диапазон с использованием дерева Фенвика

Мне было интересно, можно ли изменить дерево Fenwick Tree (или двоичное индексированное дерево) на:

1) Увеличьте частоту всех элементов в диапазоне на определенную величину

Это в отличие от традиционного дерева Fenwick, где обновления выполняются на одном элементе, и запросы выполняются в диапазоне (вроде как обратное дерево Fenwick).

Ответы

Ответ 1

Конечно!

Дерево Fenwick позволяет выполнять эти операции в O (log n):

update(x, delta)   => increases value at index x by delta
query(x)           => returns sum of values at indices 0,1,2,...,x

Здесь простая реализация дерева Фенвика в С++:

int F[MAX];

void update( int x, int delta ) {
  for( ++x; x < MAX; x += x&-x ) F[x] += delta;
}

int query( int x ) {
  int sum = 0;
  for( ++x; x > 0; x -= x&-x ) sum += F[x];
  return sum;
}

Теперь забудьте о внутренностях дерева Фенвика и сосредоточьтесь на проблеме. При использовании дерева Фенвика просто представьте, что он буквально хранит массив частот и как-то волшебным образом выполняет обе операции в O (log n). Обновление функции изменяет частоту одного элемента, и запрос возвращает сумму частот первых элементов x.

Итак, в "традиционной" проблеме у вас были следующие операции:

void incFreqAt( int index ) {
  update( index, 1 );
}

int getFreqAt( int index ) {
  return query( index ) - query( index-1 );
}

Теперь, вместо сохранения частоты каждого отдельного элемента, сохраните различия между частотами соседних элементов.

Это новые операции:

void incFreqFromTo( int a, int b, int delta ) {
  update( a, delta );
  update( b+1, -delta );
}

int getFreqAt( int index ) {
  return query( index );
}

При увеличении частот в диапазоне [a..b], просто увеличивайте разницу по индексу a и разность декрементов при индексе b + 1. Это также похоже на высказывание: увеличивайте все частоты в диапазоне [a..infinity] и уменьшите все частоты в диапазоне [b + 1..infinity].

Чтобы получить частоту элемента в индексе x, просто суммируйте все различия частот в диапазоне [0..x].