HOW TO SOLVE SPOJ- Its a Murder! - USING FENWIC TREE

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>>>https://www.spoj.com/problems/DCEPC206/#:~:text=DCEPC206%20-%20Its%20a%20Murder!&text=While%20going%20to%20the%20crime,some%20pattern%20in%20those%20numbers.

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 :grinning: :grinning:
,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.