Light OJ -- 1082(Array Queries)

 criteria to solve the problem:segment tree

In bangla:http://www.shafaetsplanet.com/?p=1557

In english:https://cp-algorithms.com/data_structures/segment_tree.html

tree node=(2*n)+1;

///Bismillahir Rahmanir Rahim

///Author:Tanvir Ahmmad

///CSE,Islamic University,Bangladesh

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<string>

#include<cstring>

#include<sstream>

#include<cmath>

#include<cstring>

#include<vector>

#include<queue>

#include<map>

#include<set>

#include<stack>

#include<vector>

#include<iterator>

#include <functional> ///sort(arr,arr+n,greater<int>()) for decrement of array

/*every external angle sum=360 degree

  angle find using polygon hand(n) ((n-2)*180)/n*/

///Floor[Log(b)  N] + 1 = the number of digits when any number is represented in base b

using namespace std;

typedef long long ll;

#define hi 100009

void seg_tree(int node, int low,int high,int arr[],int tree[])

{

    while(high==low)

    {

        tree[node]=arr[low];

        return;

    }

    int left=node*2;

    int right=(node*2)+1;

    int mid=(low+high)/2;

    seg_tree(left,low,mid,arr,tree);

    seg_tree(right,mid+1,high,arr,tree);

    tree[node]=min(tree[left],tree[right]);

}

int query(int node, int low,int high,int arr[],int tree[],int beg,int qu)

{

    if(beg>high || qu<low) return hi;

    if(beg<=low && high<=qu) return tree[node];

    int left=node*2;

    int right=(node*2)+1;

    int mid=(low+high)/2;

    int p1=query(left,low,mid,arr,tree,beg,qu);

    int p2=query(right,mid+1,high,arr,tree,beg,qu);

    return min(p1,p2);

}

int main()

{

    int tst,n,q,beg,qu,ca=1;

    scanf("%d",&tst);

    while(tst--)

    {

        printf("Case %d:\n",ca++);

        scanf("%d%d",&n,&q);

        int arr[n+2];

        int tree[n*4];

        for(int i=1; i<=n; i++) scanf("%d",&arr[i]);

        seg_tree(1,1,n,arr,tree);

        for(int i=1;i<=q;i++)

        {

            scanf("%d%d",&beg,&qu);

            cout<<query(1,1,n,arr,tree,beg,qu)<<endl;

        }

    }

    return 0;

}

///Alhamdulillah

problem link:https://lightoj.com/problem/array-queries