Fenwick tree: initialization in O(N)

Правка en2, от ATSTNG, 2018-05-07 01:20:51

Hi, CodeForces.

Recently I decided to take a closer look at data structure called Fenwick tree or binary indexed tree.

In this blogpost I will only consider Fenwick tree for sum, but everything stated there can be easily generalized for any associative, commutative and inversable operation.

Some implementation

After reading articles about it on e-maxx.ru and neerc.ifmo.ru and asking friends I've got interested by this moment. Both articles (and my friends) use this algorithm to initialize Fenwick tree on given array:

  1. Fenwick tree for array of zeros is array of zeros, we will take it as a basis
  2. We will use tree queries to replace all elements of array with elements we need
void init_vector_classic (vector<int> a) {
    init_empty(a.size());

    for (int i = 0; i < a.size(); i++) inc(i, a[i]);
}

This will work in O(N * logN) where N is length of given array.

Can we do it faster? Definitely can!

By definition of the Fenwick tree each tree element is the sum of continious segment of initial array. Considering that we have no queries to change elements in initialization process, we can use prefix sums to calculate elements of our Fenwick tree. This will require O(N) preprocessing, but will allow to calculate tree elements in O(1). So initialization asymptotic improves to O(N) + O(1) * O(N) = O(N).

void init_vector_linear_prefix (vector<int> a) {
    init_empty(a.size());

    vector<int> prefix_sum;
    prefix_sum.assign(a.size(), 0);
    prefix_sum[0] = a[0];
    for (int i = 1; i < a.size(); i++) prefix_sum[i] = prefix_sum[i-1] + a[i];

    for (int i = 0; i < a.size(); i++) {
        int lower_i = (i & (i+1)) - 1;
        fenwick[i] = prefix_sum[i] - (lower_i >= 0 ? prefix_sum[lower_i] : 0);
    }
}

But in this implementation we get additional O(N) memory to store additional array.

Can we avoid this? Yes, we can!

We can notice that to initialize fenwick[i] we only require such elements of prefix_sum[j] where j ≤ i. This allows to use only one array and, starting from the end, change each element from prefix sum to Fenwick tree element.

void init_vector_linear (vector<int> a) {
    init_empty(a.size());

    fenwick[0] = a[0];
    for (int i = 1; i < a.size(); i++) fenwick[i] = fenwick[i-1] + a[i];

    for (int i = a.size()-1; i > 0; i--) {
        int lower_i = (i & (i+1)) - 1;
        if (lower_i >= 0) fenwick[i] -= fenwick[lower_i];
    }
}

This way we can improve initialization time of Fenwick tree to O(N) using O(1) additional memory.

Of course, in most of the problems amount of queries is not much less than the size of Fenwick tree, so improving initialization time will not improve final asymptotic of your solution. But this optimization gives as ability to improve constant of the part of your solution, that works with Fenwick tree (or trees) with just a few lines of code.

What do you think about this and how do you initialize your Fenwick trees?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
ru6 Русский ATSTNG 2018-11-11 01:04:51 259
en4 Английский ATSTNG 2018-11-11 01:02:56 250
en3 Английский ATSTNG 2018-05-07 01:24:48 0 (published)
ru5 Русский ATSTNG 2018-05-07 01:24:05 0 (опубликовано)
en2 Английский ATSTNG 2018-05-07 01:20:51 2 Tiny change: ' can!\n\nWE can notic' -> ' can!\n\nWe can notic'
ru4 Русский ATSTNG 2018-05-07 01:14:12 4 Мелкая правка: 'етим, что инициализ' -> 'етим, что для инициализ'
en1 Английский ATSTNG 2018-05-07 01:10:34 3881 Initial revision for English translation (saved to drafts)
ru3 Русский ATSTNG 2018-05-07 00:39:31 4 Мелкая правка: 'ации._\n\n\n<spoiler' -> 'ации._\n\n****\n<spoiler'
ru2 Русский ATSTNG 2018-05-07 00:36:50 482 Мелкая правка: 'ет за $O(N\log{} N)$ от дл' -> 'ет за $O(N log N)$ от дл'
ru1 Русский ATSTNG 2018-05-07 00:13:55 4358 Первая редакция (сохранено в черновиках)