Блог пользователя Armyx

Binary indexed tree — initialization
Автор Armyx, 9 лет назад, По-английски

I have learned this awesome data structure. It's clear for me that operations like add and sum works in O(log n) time, but is there any known trick to reduce complexity of initialization ? Let's say I want to start with an array array[] = { 2,4,5,7,0,0,1,6 } instead of 0's . Now I have to iterate through array and call add(array[i]) on each element which require O(log n) time, so the total complexity will be O(n log n). Can we do it better ?

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Increase size of the array to power of two, so n = 2^k (just append zeros). Then build the segment tree with sums and write all left nodes during in-order traverse of the tree. Note that you can do it without building segment tree explicitly.

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Yes, it is easy. Just do partial sums and then for a position i you add sum[i]-sum[i-lsb(i)].

→ Ответить
»
9 лет назад, # |
← Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

initialization:

if you use BIT 1 based

for (int i = 1; i <= n; i++) {
    int j = (i + (i & -i));
    F[i] += a[i];
    if (j <= n) F[j] += F[i];
}

if you use BIT 0 based 

for (int i = 0; i < n; i++) {
    int j = (i | (i + 1));
    F[i] += a[i];
    if (j < n) F[j] += F[i];
}
→ Ответить