c++ - 线段树build时出错

Question

#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的实例

Answer 1

已經找到了答案，應當build(cur,1,n+1);

因為我建的是左閉右開，要存到n就必須到n+1

Answer 2

肉眼看了一下，main函數裡面cur是一個nullptr，在build函數裡面呼叫cur->left 和 cur->right，肯定段錯誤。

---

樓主搞acm的吧，都開始學習線段樹了，也應該學了蠻長時間了，基本的debug還是要學的，你gdb跟一下其實就知道為什麼了

Answer 3

可能會int越界，注意用long long

struct node
{
    int l,r;
    long long v,lazy;
}a[600000];
int b[200003];
void build(int i,int l,int r)
{
    a[i].l=l,a[i].r=r,a[i].lazy=0;
    if(l==r)
    {
        a[i].v=b[l];
        return;
    }
    int m=(l+r)/2;
    build(2*i,l,m),build(2*i+1,m+1,r);
    a[i].v=a[2*i].v+a[2*i+1].v;
}
void update(int i,int l,int r,long long v)
{
    a[i].v+=((r-l+1)*v);
    if(a[i].l==l && a[i].r==r)
    {
        a[i].lazy+=v;
        return;
    }
    int m=(a[i].l+a[i].r)/2;
    if(r<=m)
        update(2*i,l,r,v);
    else if(l>m)
        update(2*i+1,l,r,v);
    else
        update(2*i,l,m,v),update(2*i+1,m+1,r,v);
}
int query(int i,int l,int r)
{
    if(a[i].l==l && a[i].r==r)
        return a[i].v;
    int m=(a[i].l+a[i].r)/2;
    if(r<=m)
        return (r-l+1)*a[i].lazy+query(2*i,l,r);
    else if(l>m)
        return (r-l+1)*a[i].lazy+query(2*i+1,l,r);
    else
        return (r-l+1)*a[i].lazy+query(2*i,l,m)+query(2*i+1,m+1,r);
}

呼叫的時候build(1,1,n)，表示樹根下標為1