The easiest segment tree problem. Lightoj-1082

1082 - Array Queries  

First read about Segment tree in English or In Bangla ডাটা স্ট্রাকচার: সেগমেন্ট ট্রি-১.

 Implemented in C:

#include<stdio.h>
#define mx 100009
int arr[mx];
int tree[mx*3];
void init(int NowNode,int L,int R) /** Building segment tree **/
{
    if(L==R)
    {
        tree[NowNode]=arr[L];
        return;
    }
    int left = NowNode*2;
    int right = NowNode*2+1;

    int mid = (L+R)/2;

    init(left,L,mid);
    init(right,mid+1,R);
    if(tree[left]<tree[right])
        tree[NowNode]=tree[left];
    else
        tree[NowNode]=tree[right];
}

int Query(int NowNode,int L,int R,int p,int q) /** Query **/
{
    if(p>R|| q<L)
    {
        return 9999999;
    }
    if(L>=p && R<=q)
        return tree[NowNode];

    int left = NowNode*2;
    int right = NowNode*2+1;
    int mid = (L+R)/2;
    int p1 = Query(left,L,mid,p,q);

    int p2 = Query(right,mid+1,R,p,q);
    if(p1<p2)
        return p1;
    else
        return p2;
}


int main()
{
    int n,j,m,k,p,q;
    int i,test;

    scanf("%d",&test);
    for(j=1;j<=test;j++)
    {
        getchar();
        scanf("%d%d",&n,&m);

        for(k=1;k<=n;k++)
        {
            scanf("%d",&arr[k]);
        }
        init(1,1,n);
        printf("Case %d:\n",j);
        for(k=1;k<=m;k++)
        {
            scanf("%d%d",&p,&q);
             printf("%d\n",Query(1,1,n,p,q));
        }
    }
    return 0;
}