Help needed on Persistent Segment Tree

I was implementing the most basic question I could found on Persistent Segment Tree. It is giving a wrong answer, please help !!!

Code Link : IDEONE

Question link : PSEGTREE

I also cross checked my result using the algorithm given on cp-algorithm.com

Also share some questions for practice.

you should add the latest value of that index in every update

Vertex * update(Vertex * root, int tl, int tr, int idx, int v){
if( tl == tr ){
assert(tl == idx);
return new Vertex(v+query(seg[last], 0, nn-1, idx, idx));
}
if( idx <= (tl+tr)/2 )
return new Vertex( update(root->l, tl, (tl+tr)/2, idx, v), root->r);
else
return new Vertex( root->l, update(root->r, (tl+tr)/2+1, tr, idx, v));
}

1 Like

in 49th line