### sudddddd's blog

By sudddddd, history, 3 years ago, Hello, this is my first problem on segment tree. I have used segment tree to solve this problem but I am getting Wrong Answer on a test case. Can you point out what is wrong. Thank you

Problem Statement

My Code Comments (3)
 » 3 years ago, # | ← Rev. 2 →   Your query function was not correct as it was not returning required answer when the search was out of range as the new node with values -15000 was made and querying using it was creating a problem. Also it modified the tree sometimes. Here is how you should query on the segment tree : list* query(list* tree[],int node,int low,int high,int l,int r) { if(low==l && high==r) return tree[node]; int p1 = 2*node+1, p2 = 2*node+2, mid = (low+high)/2; if(r<=mid) return query(tree,p1,low,mid,l,r); if(l>mid) return query(tree,p2,mid+1,high,l,r); list *a=query(tree,2*node+1,low,(high+low)/2,l,mid); list *b=query(tree,2*node+2,(high+low)/2+1,high,mid+1,r); list *n; long w=a->sum+b->sum; long x=max(max(a->bestsum,b->bestsum),a->right+b->left); long y=max(a->left,a->sum+b->left); long z=max(a->right+b->sum,b->right); n=make_new_node(w,x,y,z); return n; } I replaced your query function with the above function and got AC. Here is the link to the AC code.
•  » » Thank You very much
•  » » Can you please give me a test case where my code is wrong? (I understood that I should not have updated the tree in query function)