I am getting TLE in spoj platform [ https://www.spoj.com/problems/UPDATEIT/ ] . This is the code that i have written
Could you please suggest what i am missing ?
I am trying to solve this issue using fenwick tree .
SPOJ question Update the array ! [UPDATEIT]
Hey @S18APP-OL0003
Your code is simple array code. It is not a BIT tree. Please read BIT once.
If your doubt is resolved please mark it as closed.
Hello @Aarnav-Jindal-1059677350830863 ,
In BIT the key point to traverse the BIT array from current index to the last index is
index += (index & (-index));
but by traversing the array like this it skips some of the indexes between range l to r . And its not helping in solve the issue
That’s why i tried to traverse the array incrementally by 1 count . this solves the issue but seems like its failing for higher input .
Could you please suggest how should i implement the BIT for it .
Use this code once https://www.geeksforgeeks.org/binary-indexed-tree-or-fenwick-tree-2/
You’ll understand it better.
I have modified the code in above link and tried to implement it in BIT way but still i am getting TLE .
Please , have a look .
Actually this is not a BIT question. This is a preprocessing based question. When you update l,r,val.
Do
BIT[r] += val;
BIT[l-1] -= val;
Before processing q queries, do for i = 1 to N : BIT[i] += BIT[i-1];
The for each query output BIT[index]
I need bit clarification
Do i need to do
BIT[r] += val; or BIT[l] += val;
Same in the case of
BIT[l-1] -= val or BIT[r-1] -= val;
-
Because in Array we need to update indexes from l to r . So from l to r it should be +val and after r to last index it should be -val .
-
How should i traverse the array while updating the val , incrementally (i++) or i += (i & (-i));
-
I didn’t understood this logic => “Before processing q queries, do for i = 1 to N : BIT[i] += BIT[i-1];”
Why we need to do it ?
Hello @Aarnav-Jindal-1059677350830863 - i have written the code as mentioned in above link but still its failing with TLE.
Your code is perfect. Issue might be unnecessary function calls and declaring new array for each test case. And don’t worry about TLE on SPOJ. Their bounds are sometimes unnecessarily tight. Your code is perfect. It is 0(n).
1 Like
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.
Hi @Aarnav-Jindal-1059677350830863 - This page could not be found https://online.codingblocks.com/feedback/d/17603
Could you please also let me know is there any programming contest which current algo++ batch is following as it was the case earlier.
If you know then could you please send me the same .