There is hardly any need for improving the time complexity of initializing a Binary Indexed Tree (BIT). Anyway I want to share this neat little trick to initialize a BIT in O(N) time.
Let bit[N]
be BIT array and a[N]
be the array we need to initialize our BIT with. Notice that for all i
we need to add a[i]
to positions i
, i + (i & -i)
and so on in the bit
array. Also, a[i + (i & -i)]
will also be added to all these positions except i
. We can add these 2 in the required places together! Take a look at the following code:
int bit[N], a[N];
void initialize(int n)
{
for(int i=1; i<=n; i++)
{
bit[i] += a[i];
if(i + (i & -i) <= n)
bit[i + (i & -i)] += bit[i];
}
}
Really easy and elegant! Although I have not come across any problems that needed this trick, but there might be a situation where N is too large to initialize the array in O(NlogN) while the number of queries are such that O(logN) per query is feasible (maybe in a 2D BIT problem).
The same technique can be for bulk updates (put update value for position i
at a[i]
for all N) and even for bulk queries. By bulk I mean number of updates/queries are O(N). Leaving bulk queries as an exercise for the reader :P (its really easy if you understood the above).