WE NEED TO STORE PREFIX SUM ,IN A PARTICULAR ORDER ,SO THAT WHEN WE DO UPDATE HE NUMBER WHICH IS SMALLER GETS UPDATED IN THE TREE FIRST AND QUERY GETS EXECUTED IN ORDER OF QUESTION ,BUT I AM NOT ABLE TO IMPLEMENT THIS PROPERLY .
PROBLEM LINK>>>SPOJ.com - Problem DCEPC206.
What are you sorting? My implementation would be this.
int totalSum = 0;
for(int &x : A) {
totalSum += bit.get(x - 1);
bit.add(x, x);
}
The array stored as the fenwick tree is the frequency array. (This works only if A_i are small enough to be stored in a frequency array).
Here, bit
is the fenwick tree object, add(int i, int v)
does a +v
to index i
, and get(int r)
returns the prefix sum till index r
.
What was your implementation?
2 Likes
WE NEED TO STORE PREFIX SUM ,IN A PARTICULAR ORDER ,SO THAT WHEN WE DO UPDATE HE NUMBER WHICH IS SMALLER GETS UPDATED IN THE TREE FIRST AND QUERY GETS EXECUTED IN ORDER OF QUESTION ,BUT I AM NOT ABLE TO IMPLEMENT THIS PROPERLY .
What your trying to achieve sounds pretty complicated, and I’m not sure if a fenwick tree can support that.
Also, why call caps?
1 Like
Sorry for caps ,you can check this solution and explain me the logic
,https://github.com/spoj-solution/solution/blob/master/src/DCEPC206.cpp
I dry runned the solution ,things got fit in fenwic tree ,but I coudn’t develop the thought process,I want to develop the thought process behind this ,so that I can solve more problem in future.