tomnjerry18's blog

By tomnjerry18, history, 5 weeks ago, In English

Hi guys, I have been learning segment trees from Segment Trees Hackerearth .

I am trying to solve the problem range minimum query problem given in the end the topic. I am getting wrong answer in the second input in which n = 10^5 and number queries are also 10^5.

Can anyone help me to debug the code? Link to my code Online C++ Compiler.

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it
	int arr[3*n];

Can u change size of segment tree to 4*n and then submit the solution once. It should pass :)

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    void update_segment_tree(int *arr, int *a, int node, int start, int end, int idx, int new_value)
    {
    	if(start == end)
    	{
    		a[idx] = new_value;
    		arr[node] = new_value;
    		return;
    	}	
    	int mid = (start+end)/2;
    	if(idx<=mid)
    	{
    		update_segment_tree(arr, a, 2*node+1, start, mid, idx, new_value);
    	}
    	else
    	{
    		update_segment_tree(arr, a, 2*node+2, mid+1, end, idx, new_value);
    	}
    	arr[node] = min(arr[2*node+1], arr[2*node+2]);
    }
    

    There was a bug in "update_segment_tree" implementation. I have corrected and now it is working.