#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
肉眼看了一下,main函数里面cur是一个nullptr,在build函数里面调用cur->left 和 cur->right,肯定段错误。
楼主搞acm的吧,都开始学习线段树了,也应该学了蛮长时间了,基本的debug还是要学的,你gdb跟一下其实就知道为什么了
可能会int越界,注意用
long long
调用的时候
build(1,1,n)
,表示树根下标为1