Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #define mx 100001
- int arr[mx], tree[mx*3];
- using namespace std;
- int query( int node , int b, int e, int i, int j)
- {
- if(i>e || j<b)
- {
- return mx;
- }
- else if(b>=i && e<=j)
- {
- return tree[node];
- }
- else
- {
- int mid=(b+e)/2;
- int left =node*2;
- int right=node*2+1;
- int la=query(left,b,mid,i,j);
- int ra=query(right,mid+1,e,i,j);
- return min(la,ra);
- }
- }
- void init( int node, int b, int e)
- {
- if(b==e)
- {
- tree[node]=arr[b];
- return ;
- }
- int mid=(b+e)/2;
- int left=node*2;
- int right =node*2+1;
- init(left,b,mid);
- init(right,mid+1,e);
- tree[node]=tree[left]+tree[right];
- }
- int main()
- {
- int n,i,t,p,j,n1,n2,k;
- cin>>t;
- for(i=1;i<=t;i++)
- {
- cin>>n;
- cin>>p;
- for(k=1;k<=n;k++)
- {
- cin>>arr[i];
- }
- init(1,1,n);
- for(j=1;j<=p;j++)
- { cin>>n1>>n2;
- cout<<query(1,1,n,n1,n2)<<endl;
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement