Armyx's blog

Binary indexed tree — initialization
By Armyx, 9 years ago, In English

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 ?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

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];
}
→ Reply