JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
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 on

the effect of this will be

(tree[idx] + tree[idx-(idx&-idx)]...) / c

it 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 NlogN
We 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)
RSS