I dont know why update fucntion not working correctly
#include<bits/stdc++.h>
using namespace std;
struct SegmentTree{ int sum,min_sum;};
#define SZ 100006
int a[SZ];
SegmentTree tree[ SZ*4 ];
SegmentTree make_data(int val)
{
SegmentTree re;
re.sum=val;
re.min_sum=0;
return re;
}
SegmentTree merge( SegmentTree a , SegmentTree b)
{
SegmentTree res;
res.sum=max(a.sum,b.sum);
if(res.sum==a.sum)
res.min_sum=max(b.sum,a.min_sum);
else
res.min_sum=max(a.sum,b.min_sum);
return res;
}
void BUILD(int node , int start , int end)
{
if(start == end)
{
tree[node]=make_data(a[start]);
return ;
}
int mid = (start + end )>>1;
int l = node<<1 ;
int r = node<<1|1;
BUILD(l,start,mid);
BUILD(r,mid+1,end);
tree[ node ] = merge( tree[l] ,tree[r]);
}
void update(int node,int start,int end,int pos,int new_value)
{
if(start==end){
tree[node]=make_data(a[start]);
a[start]=new_value;
return;
}
else
{
int mid = (start + end )>>1;
int l = node<<1 ;
int r = node<<1|1;
if(pos>=start&&pos<=mid)
update(l,start,mid,pos,new_value);
else
update(r,mid+1,end,pos,new_value);
tree[node]=merge( tree[l] ,tree[r]);
}
}
SegmentTree Query(int node , int start , int end , int x , int y)
{
if(start == x && end == y)
return tree[node];
int l = node<<1 ;
int r = node<<1|1;
int mid = (start + end )>>1;
// right < mid
if(y <= mid ) return Query(l,start,mid,x,y); // whole side is in left
else if( x > mid ) return Query(r,mid+1,end,x,y) ; // whole side is in right
else
{
return merge( Query(l,start,mid,x,mid) , Query(r,mid+1,end,mid+1,y) ) ; // split in two side so merging
}
}
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
cin>>a[i];
BUILD(1,1,n);
int q;
scanf("%d",&q);
while(q--)
{
char type;int x,y;
cin>>type>>x>>y;
if(type=='Q')
{
SegmentTree r=Query(1,1,n,x,y);
cout<<r.sum+r.min_sum<<endl;
}
else
update(1,1,n,x,y);
}
}