首页 > 开发 > C++ > 正文

线段树build时出错

2017-09-11 21:34:52  来源: 网友分享
#include <iostream>using namespace std;struct Node{    int left;    int right;    int delta;    int sum;    Node *lc;    Node *rc;};void build(Node *cur,int l,int r){    cur->left=l;    cur->right=r;    cur->sum=0;    if(l+1<r){        cur->lc = new Node;        cur->rc = new Node;        build(cur->lc,l,(l+r)/2);        build(cur->rc,(l+r)/2,r);    }    else cur->lc = cur->rc = NULL;}void update(Node *cur){    cur->lc->sum+=cur->delta*(cur->lc->right - cur->lc->left);    cur->rc->sum+=cur->delta*(cur->rc->right - cur->rc->left);    cur->lc->delta+=cur->delta;    cur->rc->delta+=cur->delta;    cur->delta=0;}void change(Node *cur,int l,int r,int delta){    if(l<=cur->left&&r>=cur->right){        cur->sum+=delta*(cur->right - cur->left);        cur->delta+=delta;    }    else{        if(cur->delta!=0) update(cur);        if(l<(cur->left+cur->right)/2) change(cur->lc,l,r,delta);        if(r>(cur->left+cur->right)/2) change(cur->rc,l,r,delta);        cur->sum=cur->lc->sum+cur->rc->sum;    }}int query(Node *cur,int l,int r){    if(l<=cur->left&&r>=cur->right)        return cur->sum;    else{        if(cur->delta!=0)            update(cur);        int ans=0;        int t=(cur->left+cur->right)/2;        if(l<t) ans+=query(cur->lc,l,r);        if(r>t) ans+=query(cur->rc,l,r);        return ans;    }}int n,g,m;int a,b,c,d;int main(){    Node *cur;    cin>>n;    build(cur,1,n);    for(int i=1;i<=n;i++){        cin>>g;        change(cur,i,i+1,g);    }    cin>>m;    for(int i=1;i<=m;i++){        cin>>a;        if(a==1){            cin>>b>>c>>d;            change(cur,b,c+1,d);        }        else{            cin>>b>>c;            cout<<query(cur,b,c+1);        }    }    return 0;}

build时出错。
Program received signal SIGSEGV,Segmentation fault.

build的问题已解决,把Node *cur改为Node *cur=new Node就行了
但是change第三次时出错,是wikioi的实例

解决方案

已经找到了答案,应当build(cur,1,n+1);

因为我建的是左闭右开,要存到n就必须到n+1