线段树类所占内存
来源：9-7 更多线段树相关的话题
慕姐8741563
2018-09-20
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;
}
我觉得很困惑，因为类占很大的内存吗？希望您能解答下我的困惑，如果有什么我没说明白的地方，请指出一下，多谢。
1回答
-
liuyubobobo
2018-09-20
哎 典型的ACM竞赛式的问题。和判题系统的操作系统有关也和判题逻辑中如何判断MLE有关。
因为在全局申请的空间是在编译时申请的放在全局静态区而在类里的变量在进行类初始化的时候放在了系统栈中。由于系统设置原因系统栈无法容纳这么多内容但全局静态区可以。
可以测试一下这个问题如果线段树的空间用指针new出来的话看是不是会MLE此时这个空间在系统堆上来测试一下OJ的运行环境。当然也可以直接给OJ管理员发邮件问具体参数。
另外对于这个问题由于M远远小于N所以其实整棵线段树不需要完全建出来可以随着查询操作一点一点建出来。整体解决这M个操作的问题应该远远不需要4N个节点。我在课程中提过一嘴也就是创建一个链式的动态线段树。有兴趣可以试试看
加油
30
相似问题