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);
}
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;
}
}
I won't spend more than 20 seconds looking at the code because you put no effort in cleaning it up.
In any case, it's pretty obvious that you copy tree on every recursive call to query because you're passing a vector and not a reference to that vector. I don't know if that's the only mistake but it looks like a good candidate.
I have edited the code and cleaned it up as you suggested. Could you please help me out now ?
Was it not what I mentioned? When you pass vectors as function parameters they get copied. If you insist on passing them instead of keeping them global, you must use references as you did for tree in build to avoid copying the whole container. Seems to me that is the most likely source of MLE.
Additionally to copying a lot of vectors, your tree array is too small too. If you want to have at least $$$N$$$ leaves in a regular segment tree it's best to expect a size of up to 4*N. Imagine for example $$$N=33$$$ would yield a tree with 64 leaves and hence 127 nodes.