Databases
StackOverflow2013
Postsdbo
POIssue in implementation of Segment Trees
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POIssue in implementation of Segment Trees
    text
    copied!<p>I am trying to implement Segment Trees for extracting min value from a given interval in an array.[Reference - <a href="http://www.geeksforgeeks.org/segment-tree-set-1-range-minimum-query/" rel="nofollow">http://www.geeksforgeeks.org/segment-tree-set-1-range-minimum-query/</a> ]</p> <p>The following is the code for the same.</p> <pre><code>//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&lt;int /* $$$ float $$$ */&gt; 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&gt;b)? b: a; } void getInput(int n) { for (int i = 0; i &lt; n; ++i) { float /* $$$ float $$$ */ temp; cin&gt;&gt;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 &lt; (int)(2*pow(2,h))-1; ++i) { cout&lt;&lt;i&lt;&lt;"="&lt;&lt;tree[i]&lt;&lt;endl; //print the value at each node(array element) along with indes } cout&lt;&lt;"-----------------"&lt;&lt;endl; } }; int main(int argc, char const *argv[]) { int n,l,r; float min; cout&lt;&lt;"Enter n"; cin&gt;&gt;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; } </code></pre> <p>If I am constructing an <code>int</code> 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 <code>float</code>, something mischievous happens and <strong>indices 0-7 and index 11</strong> of the array representing the segment tree show the value <strong><code>nan</code></strong>; while nothing of this sort happens in the case of <code>int</code> tree. The function <code>printSegmentTreeArray()</code> is for printing the value stored at each location of the array representing the tree.</p> <p>NOTE:-</p> <p>1.In the code, the changes required for correctly changing the data type of tree from <code>int</code> to <code>float</code> are indicated by the commented block <code>/* $$$ float $$$ */</code> in front of the <code>int</code> to be replaced.</p> <p>2.I did write the function for extracting Min from queried interval but removed it out since the <code>constructST()</code> function was behaving weird.</p> <p>3.I have tested my code with the following input for both the cases.</p> <pre><code>18 3 4 2 1 5 7 9 7 10 5 12 3 1 1 2 1 3 2 </code></pre> <p>Can someone please point out the reason for this?</p>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload