SPOJ GSS1 - solution

test1.cpp

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
 
void construct(int tree[],int arr[],int index,int start,int end){
	int mid,max1;
	if(start == end){
		tree[index] = arr[start];
	}
	else{
		mid = (start+end)/2;
		construct(tree,arr,2*index,start,mid);
		construct(tree,arr,(2*index)+1,mid+1,end);
		max1 = max(tree[2*index],tree[(2*index)+1]);
		tree[index] = max(max1,tree[2*index]+tree[(2*index)+1]);
	}
}
 
int query(int tree[],int index, int i, int j, int start, int end){
	int mid,left,right;
	if(i <= start && j>= end){
		return tree[index];
	}
	mid = (start+end)/2;
	if(j<= mid){
		return query(tree,2*index,i,j,start,mid);
	}
	else if(i > mid){
		return query(tree,(2*index)+1,i,j,mid+1,end);
	}
	else{
		left = query(tree,2*index,i,j,start,mid);
		right = query(tree,(2*index)+1,i,j,mid+1,end);
		return max(left,right);
	}
}
 
int main() {
	int height,n,elem,m,x,i,j;
	int arr[50001];
	height = int(ceil(log(50001)/log(2)));
	int tree[int(pow(2,height+1))];
	cin>>n;
	for(int elem=0; elem<n; elem++){
		cin>>x;
		arr[elem] = x;
	}
	construct(tree,arr,1,0,n-1);
	cin>>m;
	for(int quer=0; quer<m; quer++){
		cin>>i>>j;
		cout<<query(tree,1,i-1,j-1,0,n-1)<<endl;
	}
	return 0;
}