### sdnr1's blog

By sdnr1, history, 6 years ago,

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).

• +67

| Write comment?
 » 6 years ago, # |   +21 3/4 of your blogs are about BITs, you must be very fond of them :)
 » 6 years ago, # | ← Rev. 2 →   +5 This is really cool trick, but it rarely improves solution significantly.Some time ago I've describes another way of constructing BITs in O(N) here. And Jakube pointed to this StackOverflow question with answer that describes your approach.Some thoughs over your exercise: General approach to perform bulk operations of single typeThere are better data structures to perform single-typed queries. Usual arrays are ideal for changing single elements. Prefix sums is the choice to calculate range sums without modifications.We know how to construct BIT over given array in O(N) and how to recover usual array from given BIT in O(N). We also know how to calculate prefix sums in O(N).So, in case when number of queries is high enough, we can switch data representation type to operate all queries with better complexity and switch data representation back. (This approach reminds me of FFT.)Performing Q modification queries in O(N + Q) time: Recover usual array Perform all modifications Construct BIT over modified array Performing Q sum queries in O(N + Q) time: Recover usual array Calculate prefix sums Answer all queries with prefix sums Probably there are better approaches with better memory consumption and better constant factor.
 » 4 years ago, # |   0 This might be a very stupid question, but is it not possible that since i+(i&-i) <=n we may go out of bounds of array bit or a?
•  » » 4 years ago, # ^ |   0 I believe the assumption is that both bit and a are 1-indexed (i.e. the zero-index is ignored). BITs are conventionally 1-indexed as it makes the math easier.
 » 4 years ago, # | ← Rev. 2 →   +1 Can we use this for online update ?vector bit, a; inline void add() { int n = a.size() + 1; a.resize(n); cin >> a[n]; bit.push_back(a[n]); if (int t = i + (i & -i); t <= n) bit[i + (i & -i)] += bit[i]; }