线段树类所占内存
bobo老师好，不好意思，上个问题出了点bug，我是基于hdu oj上面的1754http://acm.hdu.edu.cn/showproblem.php?pid=1754来提出的这个问题，其实这个问题之前也碰到过，但这次wa了十几发，所以想问个清楚。以下是我照着您的课题写的代码，Memory Limit Exceeded 了十几次。
`#include
#include
using namespace std;
int a[200010];
template
class SegmentTree
{
public:
T data;
T Tree;
int size;
SegmentTree(T arr,int n)
{
data=arr;
Tree=new T[3n];
size=n;
buildSegmentTree(0,0,size-1);
}
~SegmentTree()
{
delete(Tree);
}
T get(int index)
{
return data[index];
}
int leftChild(int index)
{
return 2index+1;
}
int rightChild(int index)
{
return 2index+2;
}
void buildSegmentTree(int index,int l,int r)
{
// cout<<index<<" “<<l<<” "<<r<<endl;
if(lr)
{
Tree[index]=data[l];
return;
}
int leftTreeIndex=leftChild(index);
int rightTreeIndex=rightChild(index);
int mid=l+(r-l)/2;
buildSegmentTree(leftTreeIndex,l,mid);
buildSegmentTree(rightTreeIndex,mid+1,r);
if(Tree[leftTreeIndex]>Tree[rightTreeIndex])
{
Tree[index]=Tree[leftTreeIndex];
}
else
{
Tree[index]=Tree[rightTreeIndex];
}
// Tree[index]=max(Tree[leftTreeIndex],Tree[rightTreeIndex]);
// cout<<Tree[index]<<endl;
}
T query(int queryL,int queryR)
{
// cout<<“Hello”<<endl;
return query(0,0,size-1,queryL,queryR);
}
T query(int index,int l,int r,int queryl,int queryr)
{
// cout<<index<<" “<<l<<” “<<r<<” "<<endl;
if(lqueryl&&rqueryr)
{
return Tree[index];
}
int mid=l+(r-l)/2;
int leftTreeIndex=leftChild(index);
int rightTreeIndex=rightChild(index);
if(queryl>=mid+1)
{
return query(rightTreeIndex,mid+1,r,queryl,queryr);
}
else if(queryr<=mid)
{
return query(leftTreeIndex,l,mid,queryl,queryr);
}
else
{
T leftResult=query(leftTreeIndex,l,mid,queryl,mid);
T rightResult=query(rightTreeIndex,mid+1,r,mid+1,queryr);
int ret;
if(leftResult>rightResult)
{
ret=leftResult;
}
else
{
ret=rightResult;
}
return ret;
}
}
void Set(int index,T e)
{
if(index<0||index>size){cout<<“failed”<<endl;}
data[index]=e;
Set(0,0,size-1,index,e);
}
void Set(int treeindex,int l,int r,int index,T e)
{
// cout<<treeindex<<" “<<l<<” “<<r<<” "<<endl;
if(lr) {
Tree[treeindex]=e;
// cout<<Tree[7]<<endl;
return;
}
int mid=l+(r-l)/2;
int leftTreeIndex=leftChild(treeindex);
int rightTreeIndex=rightChild(treeindex);
if(index>=mid+1){Set(rightTreeIndex,mid+1,r,index,e);}
else {Set(leftTreeIndex,l,mid,index,e);}
if(Tree[leftTreeIndex]>Tree[rightTreeIndex])
{
// cout<<leftTreeIndex<<" "<<rightTreeIndex<<endl;
Tree[treeindex]=Tree[leftTreeIndex];
}
else
{
// cout<<leftTreeIndex<<" "<<rightTreeIndex<<" "<<treeindex<<endl;
Tree[treeindex]=Tree[rightTreeIndex];
//cout<<Tree[1]<<endl;
}
}
};
int main()
{
int n,m;
while(scanf("%d %d",&n,&m)!=EOF)
{
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
SegmentTree <int>*segmenttree=new SegmentTree <int>(a,n);
char c;
int d,e;
for(int i=0;i<m;i++)
{
getchar();
scanf("%c%d%d",&c,&d,&e);
if(c=='Q')
{
int ans= segmenttree->query(d-1,e-1);
printf("%d\n",ans);
}
if(c=='U')
{
segmenttree->Set(d-1,e);
// cout<<segmenttree.Tree[3]<<endl;
}
}
}
return 0;
}`
在万分走投无路的情况下，我把函数从类里面拿出来了， 以下是AC代码
#include
#include
using namespace std;
int a[200010];
int Tree=new int[800000];
int n,m;
int get(int index)
{
return a[index];
}
int leftChild(int index)
{
return 2index+1;
}
int rightChild(int index)
{
return 2*index+2;
}
void buildSegmentTree(int index,int l,int r)
{
// cout<<index<<" “<<l<<” "<<r<<endl;
if(lr)
{
Tree[index]=a[l];
return;
}
int leftTreeIndex=leftChild(index);
int rightTreeIndex=rightChild(index);
int mid=l+(r-l)/2;
buildSegmentTree(leftTreeIndex,l,mid);
buildSegmentTree(rightTreeIndex,mid+1,r);
if(Tree[leftTreeIndex]>Tree[rightTreeIndex])
{
Tree[index]=Tree[leftTreeIndex];
}
else
{
Tree[index]=Tree[rightTreeIndex];
}
}
int query(int index,int l,int r,int queryl,int queryr)
{
// cout<<index<<" “<<l<<” “<<r<<” “<<queryl<<” "<<queryr<<endl;
if(lqueryl&&r==queryr)
{
// cout<<Tree[index]<<endl;
return Tree[index];
}
int mid=l+(r-l)/2;
int leftTreeIndex=leftChild(index);
int rightTreeIndex=rightChild(index);
if(queryl>=mid+1)
{
return query(rightTreeIndex,mid+1,r,queryl,queryr);
}
else if(queryr<=mid)
{
return query(leftTreeIndex,l,mid,queryl,queryr);
}
int leftResult=query(leftTreeIndex,l,mid,queryl,mid);
// cout<<leftResult<<endl;
int rightResult=query(rightTreeIndex,mid+1,r,mid+1,queryr);
// cout<<rightResult<<endl;
int ret;
if(leftResult>rightResult)
{
ret=leftResult;
}
else
{
ret=rightResult;
}
return ret;
}
int query(int queryL,int queryR)
{
// cout<<“Hello”<<endl;
return query(0,0,n-1,queryL,queryR);
}
void Set(int treeindex,int l,int r,int index,int e)
{
// cout<<treeindex<<" “<<l<<” “<<r<<” "<<endl;
if(l==r) {
Tree[treeindex]=e;
// cout<<Tree[7]<<endl;
return;
}
int mid=l+(r-l)/2;
int leftTreeIndex=leftChild(treeindex);
int rightTreeIndex=rightChild(treeindex);
if(index>=mid+1){Set(rightTreeIndex,mid+1,r,index,e);}
else {Set(leftTreeIndex,l,mid,index,e);}
if(Tree[leftTreeIndex]>Tree[rightTreeIndex])
{
// cout<<leftTreeIndex<<" "<<rightTreeIndex<<endl;
Tree[treeindex]=Tree[leftTreeIndex];
}
else
{
// cout<<leftTreeIndex<<" "<<rightTreeIndex<<" "<<treeindex<<endl;
Tree[treeindex]=Tree[rightTreeIndex];
//cout<<Tree[1]<<endl;
}
}
void Set(int index,int e)
{
if(index<0||index>n){cout<<"failed"<<endl;}
a[index]=e;
Set(0,0,n-1,index,e);
}
int main()
{
while(scanf("%d %d",&n,&m)!=EOF)
{
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
buildSegmentTree(0,0,n-1);
char c;
int d,e;
for(int i=0;i<m;i++)
{
getchar();
scanf("%c%d%d",&c,&d,&e);
if(c=='Q')
{
int ans= query(d-1,e-1);
printf("%d\n",ans);
}
if(c=='U')
{
Set(d-1,e);
// cout<<segmenttree.Tree[3]<<endl;
}
}
}
return 0;
}
我觉得很困惑，因为类占很大的内存吗？希望您能解答下我的困惑，如果有什么我没说明白的地方，请指出一下，多谢。
正在回答 回答被采纳积分+3
1回答
相似问题
登录后可查看更多问答，登录/注册
