Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

Segment tree update

Revision en2, by Azin_Ahamed, 2021-09-16 12:00:38

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

Tags #segment tree update, #help, #wrong_answer

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Azin_Ahamed 2021-09-16 12:00:38 21 Tiny change: 'ery.(CSES) \nFor upda' -> 'ery.(CSES)(Using Segment Tree)\nFor upda'
en1 English Azin_Ahamed 2021-09-16 11:24:05 766 Initial revision (published)