Мне было интересно, можно ли изменить дерево Fenwick Tree (или двоичное индексированное дерево) на:
1) Увеличьте частоту всех элементов в диапазоне на определенную величину
2) Запросить частоту элемента одиночного.
Это в отличие от традиционного дерева Fenwick, где обновления выполняются на одном элементе, и запросы выполняются в диапазоне (вроде как обратное дерево Fenwick).
Конечно!
Дерево 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].