Help in coordinate compression SPOJ fenwic tree problem .Help me in debugging

1

Problem link :SPOJ.com - Problem SGIFT
Code link:my code link >> Online Compiler and IDE - GeeksforGeeks

Constraints are till 10^9

I am facing problem in coordinate compression in fenwic tree .
Like example:10 30 20 10 50 20 20

STEP1: I FISRT SORTED THE ARRAY :10 10 20 20 20 30 50

STEP2: I compressed it as 1 1 2 2 3 5 (10>1, 20>2 ,30>3, 50>4) with help of map in c++;

means new value for arr[i] = map[arr[i]] and I am updating BIT tree at index map[arr[i]] with value arr[i].

PROBLEM : ocuurs when I get query l=20 and r =40 ( query in this range) >>>query(map[40] ) -query(map[20]-1)

map[40] is not defined above since I have not taken input in the array which will be problem .What to do now ???

DIAGRAM FOR IMAGINATION FOR THIS PROBLEM :

Screenshot 2020-07-24 at 10.30.43 AM
Screenshot 2020-07-24 at 10.30.43 AM900×449 23.6 KB

2

I don’t think you need to make a BIT here…just sort the array and calculate the prefix array…next for query(a, b):

idx1 = upper_bound(arr.begin(), arr.end(), b) - arr.begin()
idx2  = lower_bound(arr.begin(), arr.end(), a) - arr.begin()
Find the sum of elements in range [idx1, idx2-1] using prefix array in O(1)
Overall Complexity: (N*log(N) + Q*log(N))

Accepted Solution : 4ck4lz - Online C++0x Compiler & Debugging Tool - Ideone.com

1 Like
3

On the initial array, do a binary search to find the closest value. Now update the endpoint in the query to that value, since there are no items between them. Answer this updated query.

On a side note, I’d just use prefix sums with this logic.

1 Like