Segment tree update function

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);
	
}

}

For those who are willing to look upon, Properly Formatted code of above snippet. Note that it is same code as above ( I just formatted it to make it more readable )

#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);
    }
}
6 Likes

Try this

void update(int node,int start,int end,int pos,int new_value){

if(pos<start || pos >end)
{
    return;
}

if(start==end){
    tree[node]=make_data(a[start]);
    a[start]=new_value;
    return;
}

int mid = (start + end )>>1;
int l = node<<1 ;
int r = node<<1|1;
update(l,start,mid,pos,new_value);
update(r,mid+1,end,pos,new_value)
tree[node]=merge( tree[l] ,tree[r]);

}

no bro, this is also giving wrong ans, i dont know why:
**Input:
** 5
1 2 3 4 5
6
Q 2 4
Q 2 5
U 1 6
Q 1 5
U 1 7
Q 1 5
Output:
7
9
11
12

but i am getting this:
7
9
9
11

@harry_122 , In your update function just change the following line:

tree[node]=make_data(a[start]); to tree[node]=make_data(new_value);

1 Like

yes thanks this worked and sorry for this silly mistake, next time, i will debug proper

1 Like