Azin_Ahamed's blog

By Azin_Ahamed, history, 6 weeks ago, In English

I'm trying to solve dynamic range minimum query(CSES).(Using Segment Tree) For updating, I am going from child to parent, eventually root.

//updating segment

void update(int st[],int idx)
{
	st[idx]=min(st[2*idx+1],st[2*idx+2]);
	if(idx==0)return;
	update(st,(int)((idx-1)/2));
}
//main part
   int arr[n];
   int hight=ceil(log2(n));
   int size=(1<<(hight+1))-1;
   int st[size]; //segment tree
   //both arr and st 0 based
   //pos->the index to be updated, newvalue->the updated value
    arr[pos]=newvalue;
    int idx=(1<<hight)-1+pos; st[idx]=newvalue;
    if(idx)
      update(st,(int)((idx-1)/2));

Note: I got ac by updating from parent to node recursively.But,getting wrong answer doing this way. Kindly help

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

»
6 weeks ago, # |
Rev. 3   Vote: I like it +1 Vote: I do not like it

You should read to this blog to solve the problem in iterative (Which is what you are trying to do): https://codeforces.com/blog/entry/18051

-QuangBuiYT