I am trying to learn segment tree through https://www.topcoder.com/community/data-science/data-science-tutorials/range-minimum-query-and-lowest-common-ancestor/ After Understanding the basics of segment trees I tried to solve this question. But only one test case is passed and on the second one, I am getting tle. On further inspection comparing the two answers using filediff I found out there are wrong answers. I am unable to find any errors. Please help.
this code is for creating and updating segment tree.
Variables - node = starting index in segment tree which is 1. b = lower limit, e = upper limit
static void preProcess(int node, int b, int e, int[] segTree, int[] arr) {
if(b == e){ //base case
segTree[node] = b;
return;
}
preProcess(node << 1, b, (b+e)>>1, segTree, arr);
preProcess((node << 1) + 1, ((b+e)>>1) + 1, e, segTree, arr);
if(arr[segTree[node<<1]] <= arr[segTree[(node << 1) + 1]]) {
segTree[node] = segTree[node<<1];
return;
}
segTree[node] = segTree[(node<<1) + 1];
}
Now, this code is for querying the minimum index from the tree.
static int query(int node, int b, int e, int[] segTree, int[] arr, int i, int j) {
// System.out.println(i+" "+j);
// System.out.println(b+" "+e);
if(i > e || j < b) {
return -1;
}
if(b >= i && e <= j) {
return segTree[node];
}
int p1 = query(node<<1, b, (b+e)>>1, segTree, arr, i, j);
int p2 = query((node << 1) + 1, ((b+e)>>1) + 1, e, segTree, arr, i , j);
if(p1 == -1) {
segTree[node] = p2;
return p2;
}
if( p2 == -1) {
segTree[node] = p1;
return p1;
}
if(arr[p1] <= arr[p2]) {
segTree[node] = p1;
return p1;
}
segTree[node] = p2;
return p2;
}
and this for updating an index in the original array.
static void updateIndex(int index, int value, int[] arr) {
arr[index - 1] = value;
}
I am using the segment array from 1st index. For full code refer here
Now I have changed bit of my code in case of if update happens after seeing from here but now I am getting Wrong ans -:
static void afterUpdate(int node, int b, int e,int index, int y,int[] segTree, int[] arr) {
if(b == e){
segTree[node] = index;
return;
}
int mid = ((b+e)>>1);
if(b <= index && mid >= index){
afterUpdate((node<<1),b,mid,index,y,segTree,arr);
}
else {
afterUpdate((node<<1)+1,mid+1,e,index,y,segTree,arr);
}
if(arr[segTree[node<<1]] <= arr[segTree[(node<<1)+1]]){
segTree[node] = segTree[node<<1];
}
else
segTree[node] = segTree[(node << 1)+1];
}
For updated full code refer here