0

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

2
  • works for me, I get the same output as on the linked page 1 1 2 1 Commented Sep 9, 2017 at 10:34
  • that is working but at the submission of the code it is giving me tle. my o/p vs expected o/p Commented Sep 9, 2017 at 10:36

1 Answer 1

2

You are updating the segment tree in case of querying the minimum index. Remove it and the code is working fine. In case of query the segTree should not be changed.

Sign up to request clarification or add additional context in comments.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.