Binary-Indexed Tree

A Binary-Indexed Tree is a standard array with extra range indexes, and looks like the following:

bit

Each single cell (shown as an empty square on each row) is an array item, indexed from [1, n]. Each vertical bar (striped part + non-striped top cell) is an index range.

Index Ranges and Responsibility:
Each index range is named after it’s top cell, and its responsibility is given by the last 1-digit (and following 0s). Range 01100 has responsibility 100, meaning it covers from 01100 down to 01100 - 100 + 1. In other words, take the last 1 and move it to the end e.g. 01010 to 01001, 10000 to 00001, 00111 to 00111.

Then, to add into any range, start by adding to each index range that lies completely within the add range. To add X to delim{[}{00001, 10000}{]}, well, that’s covered completely by delim{[}{00001, 10000}{]} itself, so X gets added to range 10000, fini. To add X to delim{[}{00111, 01000}{]}, that’s covered by delim{[}{00111, 00111}{]} union delim{[}{01000, 01000}{]}. The latter — delim{[}{01000, 01000}{]} — is not a valid range! How’s that handled?

Index Values Too
Each item in the structure is both a range and an individual item, and its actual value is a sum of this item along with all responsible (covering) ranges. E.g. the value of item 01001 is its individual value + range values 01001, 01010, 01100, 10000. (Draw a line from the item straight left and see which ranges are hit.)

So, to answer the previous question, when we encounter our invalid range delim{[}{01000, 01000}{]} we simply add our value to item 01000 itself; that’s the best we can do.

This implementation is suitable for:

– adding values to all indices across a range
– setting individual values
– querying individual values

Not suitable for:
– querying sum totals across a range

Interface:
int64 get(id) O(lg n)
void set(id, int64 value) O(lg n)
void add(ida, idb, int64 value) O(lg n)

Reference: TopCoder – Binary Indexed Trees
N.B. This reference enables a cumulative-sum query from individual inserts/additions. My implementation flips this, enabling addition to entire ranges with querying kept to individual values. (I’ll work on the former soon.)

My implementation is in git and below:

Leave a Reply