Issue in implementation of Segment Trees

Question

I am trying to implement Segment Trees for extracting min value from a given interval in an array.[Reference - http://www.geeksforgeeks.org/segment-tree-set-1-range-minimum-query/ ]

The following is the code for the same.

//This code inplements segment trees for extracting min from a given interval of an array

#include "iostream"
#include "vector"
#include "cmath"
#include "climits"
using namespace std;


class segmentTree
{
private:
    int /* $$$ float $$$ */ *tree;
    int n,h;    //h represents height of tree
    std::vector<int /* $$$ float $$$ */> timeForStick;  //vector to store the input array first
public:
    segmentTree(int noOfNodes)
    {
        n=noOfNodes;
        h=(int)(ceil(log2(n)));
        tree = new int /* $$$ float $$$ */ [(int)(2*pow(2,h))-1];
    }


    int getMid(int segmentStart, int segmentEnd)
    {
        return segmentStart+(segmentEnd-segmentStart)/2;
    }

    int /* $$$ float $$$ */ getMin(int/* $$$ float $$$ */ a, int/* $$$ float $$$ */ b)
    {
        return (a>b)? b: a;
    }


    void getInput(int n)
    {
        for (int i = 0; i < n; ++i)
        {
            float /* $$$ float $$$ */ temp;
            cin>>temp;
            timeForStick.push_back(temp);   //the input array is stored in a vector timeForStick
        }
    }

    int /* $$$ float $$$ */ constructST(int segmentStart, int segmentEnd, int currentIndex)
    {
        if (segmentEnd==segmentStart)
        {
            tree[currentIndex]=timeForStick[segmentEnd];
            return timeForStick[segmentEnd];
        }

        int mid=getMid(segmentStart,segmentEnd);
        tree[currentIndex]=getMin(constructST(segmentStart,mid,2*currentIndex+1),constructST(mid+1,segmentEnd,2*currentIndex+2));
    }


    void printSegmentTreeArray()
    {
        for (int i = 0; i < (int)(2*pow(2,h))-1; ++i)
        {
            cout<<i<<"="<<tree[i]<<endl;    //print the value at each node(array element) along with indes
        }
        cout<<"-----------------"<<endl;
    }
};


int main(int argc, char const *argv[])
{
    int n,l,r;
    float min;
    cout<<"Enter n";
    cin>>n;

    segmentTree st(n);
    st.getInput(n);     //function to get input array from user

    st.constructST(0,n-1,0);
    st.printSegmentTreeArray();

    cin.get();
    cin.get();
    return 0;
}

If I am constructing an int tree (i.e. using an integer array for storing the nodes of the Segment Tree), everything works fine. But as soon as I change the type to float, something mischievous happens and indices 0-7 and index 11 of the array representing the segment tree show the value nan; while nothing of this sort happens in the case of int tree. The function printSegmentTreeArray() is for printing the value stored at each location of the array representing the tree.

NOTE:-

1.In the code, the changes required for correctly changing the data type of tree from int to float are indicated by the commented block /* $$$ float $$$ */ in front of the int to be replaced.

2.I did write the function for extracting Min from queried interval but removed it out since the constructST() function was behaving weird.

3.I have tested my code with the following input for both the cases.

18
3 4 2 1 5 7 9 7 10 5 12 3 1 1 2 1 3 2

Can someone please point out the reason for this?

Answer 1

The function constructST never returns anything. If you update that to return tree[currentIndex] you will stop getting NaNs in your results. The fact that it worked with ints was merely a lucky coincidence.

float constructST(int segmentStart, int segmentEnd, int currentIndex)
{
    if (segmentEnd==segmentStart)
    {
        tree[currentIndex]=timeForStick[segmentEnd];
        return timeForStick[segmentEnd];
    }

    int mid=getMid(segmentStart,segmentEnd);
    tree[currentIndex]=getMin(constructST(segmentStart,mid,2*currentIndex+1),constructST(mid+1,segmentEnd,2*currentIndex+2));
    return tree[currentIndex];
}