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 Scale by constant factor
 Scale by constant factor | Reply In BIT tutorial there is a section on "Scale then entire tree by a constant factor". I am not able to understand this section. Can someone help me understand this section?Thanks in advance.
 Re: Scale by constant factor (response to post by rollingstone) | Reply Hi, what i think is that scale by a constant factor is reduce (or augment) all the values of the BIT (and as a result the cumulative frecuency) by a factor c that you have... i think this is helpfull when you are working with big numbers and you want to reduce the values to make them more tractable... then when you update every value in tree[idx] for some idx like in the code presented in the article:void scale(int c){ for (int i = 1 ; i <= MaxVal ; i++) tree[i] = tree[i] / c;}then when you make read(idx) this will read:tree[idx]/c + tree[idx-(idx&-idx)]/c ... and so onthe effect of this will be(tree[idx] + tree[idx-(idx&-idx)]...) / cit means that all the cumulative frecuency of an index is reduced (or augmented) by this factor c :)
 Re: Scale by constant factor (response to post by WRBH) | Reply What does the readSingle(i) method in the below function do? and why is i updated with "-(c-1) * readSingle(i)" ?void scale(int c){ for (int i = 1 ; i <= MaxVal ; i++) update(-(c - 1) * readSingle(i) / c , i);}
 Re: Scale by constant factor (response to post by rollingstone) | Reply The procedure readsingle(i) return the frequency of element i.Then as the author said: "then each index idx should be updated by -(c - 1) * readSingle(idx) / c (because f[idx] - (c - 1) * f[idx] / c = f[idx] / c)" this mean if you update the frequency of each idx by -(c - 1) * readSingle(idx) / c... the effect of this is that the result frequency in that index is the same as before but this time is divided by c...And this is applied to every element in the array, it means we are dividing every element by c... all we want is to transform all the frequencies by the same factor
 Re: Scale by constant factor (response to post by rollingstone) | Reply The procedure readsingle(i) return the frequency in the position i.Then as the author said: "then each index idx should be updated by -(c - 1) * readSingle(idx) / c (because f[idx] - (c - 1) * f[idx] / c = f[idx] / c)" this mean if you update the frequency of each idx by -(c - 1) * readSingle(idx) / c... the effect of this is that the result frequency in that index is the same as before but this time is divided by c...And this is applied to every element in the array, it means we are dividing every element by c... all we want is to transform all the frequencies by the same factor
 Re: Scale by constant factor (response to post by WRBH) | Reply What is the complexity of building the BIT? Isn't it O(n^2)?
 Re: Scale by constant factor (response to post by rollingstone) | Reply Nope, it is NlogNWe are calculating N values of tree[] and each one will take at most logN steps (as number of 'on' bits in a number is < logN)
 Forums Tutorial Discussions Binary Indexed Trees Scale by constant factor Previous Thread  |  Next Thread