We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Functional Programming
  3. Functional Structures
  4. Range Minimum Query
  5. Discussions

Range Minimum Query

  • skr
     + 0 comments

    I am getting timeout for test cases 5, 6, 7. When I debugged with the inputs I've seen that my timeout occurs while creating the Segmentation Tree.

    I have been looking into the code for 2 days and I still could not figure out what is the cause of this.

    You can find my tree construction code below. Any help is appreciated.

    def makeTree(ll:List[Int], l:Int, r:Int): Tree[Int] = {   
        if (r==l) {
            Leaf(ll(l), l, r)
        }
        else {
            var left = makeTree(ll, l, (l+r)/2)
            var right = makeTree(ll, (l+r)/2+1, r)
            //println(l,r,List(left.value, right.value).min)
            Node(left, right, List(left.value, right.value).min, l, r)
        }               
    }

    ll is the input array. Leaf and Node needs no explainations I believe.