JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
Binary Indexed Trees - Questions | Reply
There are some things not clearly defined. I have some questions:

idx is some index of BIT. r is a position in idx of the last digit 1 (from left to right) in binary notation. tree[idx] is sum of frequencies from index (idx-2^r + 1) to index idx (look at the Table 1.1 for clarification). We also write that idx is responsible for indexes from (idx - 2^r + 1) to idx (note that responsibility is the key in our algorithm and is the way of manipulating the tree).

1. is r 0-based or 1-based? The article doesn't define it clearly. F[] is 1 based and this should be consistent through the article unless it is defined.
2. what do you mean by last digit 1 from left to right? if idx = 5, what is the r? 1 or 3? or 0 or 2?
3. why tree[5] = 1? What is the range of sum?
RSS