JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums Tutorial Discussions Binary Indexed Trees Binary Indexed Trees - Questions
 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?
 Forums Tutorial Discussions Binary Indexed Trees Binary Indexed Trees - Questions Previous Thread  |  Next Thread