jeudi 4 avril 2019

unable to find error sement tree : minimum in subarray

i am new to Data structures and algo , and unable to find error in my code for the question

Range Minimum Query

Given an array A of size N, there are two types of queries on this array. 1) q l r: In this query you need to print the minimum in the sub-array A[l:r]. 2) u x y: In this query you need to update A[x]=y.

Input: First line of the test case contains two integers, N and Q, size of array A and number of queries.

Second line contains N space separated integers, elements of A. Next Q lines contain one of the two queries.

Output: For each type 1 query, print the minimum element in the sub-array A[l:r]. Contraints: 1≤N,Q,y≤10^5 1≤l,r,x≤N

include

using namespace std;

long a [100001]; //global array to store input

long tree[400004];
//global array to store tree

// FUNCTION TO BUILD SEGMENT TREE //////////

void build(long i,long start,long end) //i = tree node

{

if(start==end)

{
    tree[i]=a[start];

    return;

}

long mid=(start+end)/2;

build(i*2,start,mid);

build(i*2+1,mid+1,end);

tree[i] = min(tree[i*2] , tree[i*2+1]);

}

// FUNCTION TO UPDATE SEGMENT TREE //////////

void update (long i,long start,long end,long idx,long val)

//idx = index to be updated

// val = new value to be given at that index

{

if(start==end)

    tree[i]=a[idx]=val;

else
{
    int mid=(start+end)/2;

    if(start <= idx and idx <= mid)

        update(i*2,start,mid,idx,val);

    else

        update(i*2+1,mid+1,end,idx,val);

    tree[i] = min(tree[i*2] , tree[i*2+1]);

}

}

// FUNCTION FOR QUERRY

long querry(long i,long start,long end,long l,long r)
{ if(start>r || end end)

    return INT_MAX;
else

    if(start>=l && end<=r)

    return tree[i];

long mid=(start+end)/2;

long ans1 = querry(i*2,start,mid,l,r);

long ans2 = querry(i*2+1,mid+1,end,l,r);

return min(ans1,ans2);

}

int main()

{

long n,q;

cin>>n>>q;

for(int i=0 ; i<n ; i++)

    cin>>a[i];

//for(int i=1 ; i<2*n ; i++)    cout<<tree[i]<<"  ";   cout<<endl;

build(1,0,n-1);

//for(int i=1 ; i<2*n ; i++)    cout<<tree[i]<<"  ";    cout<<endl;


while(q--)
{
        long l,r;


        char ch;

        cin>>ch>>l>>r;

        if(ch=='q')

            cout<<querry(1,0,n-1,l-1,r-1)<<endl;

        else

            update(1,0,n-1,l,r);

}

return 0;

}

example :input

5 15

1 5 2 4 3

q 1 5

q 1 3

q 3 5

q 1 5

q 1 2

q 2 4

q 4 5

u 3 1

u 3 100

u 3 6

q 1 5

q 1 5

q 1 2

q 2 4

q 4 5

Expected Output

1

1

2

1

1

2

3

1

1

1

4

3

Aucun commentaire:

Enregistrer un commentaire