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 at of O(N). Leaving bulk queries at left as an exercise for the reader :P (its really easy if you understood the above).