BINARY INDEX TREE SPREAD DOUBT

general
,
1

i have trouble in the following editorial
http://discuss.codechef.com/questions/4161/spread-editorial

**my doubt is in the read function…
acc. to question we have to find the no. of elements in a particular heap.

so acc. to TOPCODER the read() will give cumulative frequency , and not frequency at that index…
but i am getting WA on using read(ind)-read(ind - 1) but ALL ACCEPED submssions use read(ind)…

please explain what wrong i am thinking.**

1 Like
2

@ac_cOder In TOPCODER tutorial,he stored the cumulative frequency,but for this problem in the initial array we are storing the difference in frequency of consecutive elements i.e, the initial array ‘A’ is
A[i]=freq.[i]-freq[i-1]. The read() gives the cumuative freq. of this array in this problem i.e,
read(i)=A[i]+A[i-1]+…A[1]=freq.[i]-freq[0].So,read(i)=freq.(i) (Since,freq[0]=0).
So, read(i) gives u the frequency of ith element.
Hope,this helps…!!

3

@upendra1234 sir,
this is my solution…GQGgTx - Online C++ Compiler & Debugging Tool - Ideone.com which is giving WA…
i have commented in it what i an doing

1 Like
4

@ac_c0der

I have seen your solution.
Your update function is good but your read function was wrong.

you have already mentioned correct read function in your code. That is completely right function

But i have updated your read function you can see here link

You your declared sum = tree[idx]

but sometime for some input cases it may have 0 value and after you decrease the sum = sum-tree[idx]

at this you can do

sum = 0;
then sum = sum + tree[idx];

So update your read function by this:

LL read(int idx){
        LL sum = 0; 
        while (idx){ 
                sum += tree[idx]; 
                idx -= (idx & -idx);
        }
return sum;
}

Tell me if you have any doubt in this.

Happy Coding!!!

5 Likes
5

You can think of a Binary Indexed Tree as supporting two operations.

  1. Get the sum of a[1] + a[2] + … + a[n].
  2. Update the element a[i] (this of course updates the entire array from i + 1 … n accordingly)

Now to extend this to the above task. You want a[1] + a[2] + … a[k] to be the number of stones on the kth pile, for this you should simply increase a[k] by the number of stones on the kth pile, and
decrease a[k + 1] by the same number.

Now for range updating. Suppose you want to increase all the stones from piles i … j by some given number x. What you do is update a[i] by x (ie call update(i, +x)), and this increases every element from i … n (because from some number k > i, a[k] is defined as a[1] + a[2] + … + a[i] + a[i + 1] + … + a[k]). So now you have to decrease everything in range from j + 1 … n by -x, that is call update(j + 1, -x), this results in you only increasing elements in range from i … j by x.

We defined a[1] + a[2] + … + a[k] to be the number of stones on the kth pile, so for querying just query the cumulative sum on the kth pile, ie output query(k).

To recap the algorithm is as follows :

  1. Read the array and for every x[i] from the call update(i, x[i]) and update(i + 1, -x[i]).
  2. Read queries and for every update query call update(i, value) and update(j + 1, -value).
  3. For every query that asks you to ouput number of stones on the kth pile pile output cumulative sum
    a[1] + a[2] + … + a[k], which we defined to be the number of stones on the kth pile, ie call query(k).

Here a[] is binary indexed tree, and x[] is the initial array of stone piles.

PS Your algorithm just isn’t correct what you are simply outputting is a[k] (or tree[k] in your case), which is nothing. You don’t need a function read() for it you can just simply write cout << tree[k] << endl; you’re going to get the same result. You need to output tree[1] + tree[2] + … + tree[k].

I’m a bit drunk from last night so excuse any spelling errors.

1 Like
6

@dragan2241 i am now a bit confused about what to find…
let me take an example.
no. of heaps=8
let C=0 initially
add 1 [3 to 5]
add 1 [3 to 7]
add 1 [2 to 6]
query : heap 5
what we get finally is: 1 2 4 4 4 2 2 1
ans: 4

according to me: read function will give 4(i.e the actual frequency==cum.freq.(5)-cum.freq.(4)).
BUT you are saying to calculate 1+2+4+4+4(cumulative frequency) ?

when we add 1 from 3 to 5 ORIGINAL FREQ. become 1 1 2 2 2 1 1 1
and CUMULATIVE FREQ. become 1 2 4 6 8 9 10 11

please tell if i am wrong.

1 Like
7

@ac_c0der please share your solution link

8

@upendra1234 i have given it below as an answer

9

thankyou very much sir and time you spent for clearing my doubt.