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 ?
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.
Yes, it is easy. Just do partial sums and then for a position i you add sum[i]-sum[i-lsb(i)].
initialization:
if you use BIT 1 based
if you use BIT 0 based