|
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? |