[ LightOJ ] 1082- Array Queries

Author            : Anwar Jahid Ruman Hossain 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : [ LightOJ ] 1082- Array Queries
Source            : Light OJ
Category          : Segment Tree
Algorithm         : Segment Tree
Verdict           : Accepted

#include<bits/stdc++.h>  
using namespace std;  
#define ll long long int  
#define mx 100005  
int tree[mx*3];  
int arr[mx];  
void build_segment(int node,int left,int right){  
    if(left==right){  
        tree[node]=arr[left]; //leaf node value set  
        //cout<<"Index "<<node<<": "<<tree[node]<<endl;  
        return;  
    }  
    int mid=(left+right)/2;  
    build_segment(node*2, left, mid); //left subtree build  
    build_segment(node*2 + 1, mid+1, right); //right subtree build  
    tree[node]=min(tree[node*2], tree[node*2 + 1]); //parent min value set  
    //cout<<"IndexMin "<<node<<": "<<tree[node]<<endl;  
}  
int query_seqment(int node,int left,int right,int ia,int ib){  
  
    if(ia>right || ib<left)  
        return INT_MAX;  
    if(left>=ia && right<=ib)  
        return tree[node];  
    int mid=(left+right)/2;  
    int p=query_seqment(node*2, left, mid, ia, ib); //left parent query  
    int q=query_seqment(node*2 + 1, mid+1, right, ia, ib); //right parent query  
    return min(p,q);  
  
  
}  
int main(){  
    //freopen("input.txt","r",stdin);  
    //freopen("output.txt","w",stdout);  
    int t;  
    scanf("%d",&t);  
    for(int tc=1;tc<=t;tc++){  
        int n,q;  
        scanf("%d%d",&n,&q);  
        for(int i=1;i<=n;i++){  
            scanf("%d",&arr[i]);  
        }  
        //root node, left most node, right most node  
        build_segment(1,1,n);  
        int ia,ib;  
        printf("Case %d:\n",tc);  
        for(int i=1;i<=q;i++){  
            scanf("%d%d",&ia,&ib);  
            //root, left most, right most, from node, to node  
            printf("%d\n",query_seqment(1,1,n,ia,ib));  
        }  
    }  
    return 0;  
}