I am trying out this problem on Hackerearth, I am getting Memory Limit Exceeded. I am using Segment Trees and I don't know where to optimize.
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
void build(vector<int>&tree,vector<int>A,ll node, ll start, ll end){
if(start==end){
tree[node]=A[start];
return;
}
ll mid=start+(end-start)/2;
build(tree,A,2*node,start,mid);
build(tree,A,2*node+1,mid+1,end);
tree[node]=__gcd(tree[2*node],tree[2*node+1]);
}
ll query(vector<int>tree,ll node, ll start, ll end, ll left, ll right){
if(start >right|| end <left )
return 1;
if(start>=left && right<=end){
// this node is completely within the range
// return it as a partial answer
return tree[node];
}
ll mid=start+(end-start)/2;
int leftAnswer=query(tree,2*node,start,mid,left,right);
int rightAnswer=query(tree,2*node+1,mid+1,end,left,right);
return __gcd(leftAnswer,rightAnswer);
}
// ll fib(ll n){
// if(n==0){
// return 0;
// }
// if(n==1 || n==2)
// {
// return 1;
// }
// if(n%2==0){
// k=n/2;
// return (2*fib(k-1)+fib(k))*fib(k);
// }
// return fib(k)*fib(k)+fib(k-1)*fib(k-1);
// }
int main(){
ll N,Q;
cin>>N>>Q;
vector<int>tree(2*N+1);
vector<int>A(N+1);
for(ll i=1;i<=N;i++) {
cin>>A[i];
}
build(tree,A,1,1,N);
for(ll i=0;i<Q;i++){
ll left,right;
cin>>left>>right;
ll index=query(tree,1,1,N,left,right);
cout<<index<<endl;
}
}