codevs 1082 线段树练习 3
时间限制: 3 s
空间限制: 128000 KB
题目等级 : 大师 Master
题目描述 Description
给你N个数，有两种操作：
1：给区间[a,b]的所有数增加X
2：询问区间[a,b]的数的和。
输入描述 Input Description
第一行一个正整数n，接下来n行n个整数，
再接下来一个正整数Q，每行表示操作的个数，
如果第一个数是1，后接3个正整数，
表示在区间[a,b]内每个数增加X,如果是2，
表示操作2询问区间[a,b]的和是多少。
pascal选手请不要使用readln读入
输出描述 Output Description
对于每个询问输出一行一个答案
样例输入 Sample Input
3
1
2
3
2
1 2 3 2
2 2 3
样例输出 Sample Output
9
数据范围及提示 Data Size & Hint
数据范围
1<=n<=200000
1<=q<=200000
#include<iostream> using namespace std; #include<cstdio> #define N 200001 long long int sz[N],n,q,a,b,c,x; struct node{ long long int l,r,val,delta; node *child[2]; }*root=NULL; void input() { scanf("%d",&n); for(long long int i=1;i<=n;++i) scanf("%d",&sz[i]); } void update(node *cur) { cur->val=cur->child[0]->val+cur->child[1]->val; } void bulid(node *&cur,long long int l,long long int r) { if(l>r) return ; cur=new node; cur->l=l;cur->r=r; cur->delta=0; if(l==r) { cur->child[0]=cur->child[1]=NULL; cur->val=sz[l]; return; } long long int mid=(l+r)/2; bulid(cur->child[0],l,mid); bulid(cur->child[1],mid+1,r); update(cur); } void down(node *cur) { if(cur->child[0]) { long long int l1=cur->child[0]->l,r1=cur->child[0]->r; cur->child[0]->val+=(r1-l1+1)*cur->delta; cur->child[0]->delta+=cur->delta; } if(cur->child[1]) { long long int l1=cur->child[1]->l,r1=cur->child[1]->r; cur->child[1]->val+=(r1-l1+1)*cur->delta; cur->child[1]->delta+=cur->delta; } cur->delta=0; } void add(node *cur,long long int l,long long int r,long long int x) { if(l<=cur->l&&cur->r<=r) { cur->val+=(cur->r-cur->l+1)*x; cur->delta+=x; return ; } if(cur->delta) down(cur); long long int mid=(cur->l+cur->r)/2; if(l<=mid) add(cur->child[0],l,r,x); if(r>mid) add(cur->child[1],l,r,x); update(cur); } long long int query(node *cur,long long int l,long long int r) { if(l<=cur->l&&cur->r<=r) { return cur->val; } if(cur->delta) down(cur); long long int ans=0,mid=(cur->l+cur->r)/2; if(l<=mid) ans+=query(cur->child[0],l,r); if(r>mid) ans+=query(cur->child[1],l,r); return ans; } int main() { input(); bulid(root,1,n); scanf("%d",&q); while(q--) { scanf("%d",&x); if(x==1) { scanf("%d%d%d",&a,&b,&c); add(root,a,b,c); } else { scanf("%d%d",&a,&b); printf("%lld ",query(root,a,b)); } } return 0; }
代码自己尝试写了一下
/*数据类型必须用long long才能过*/ #include<cstdio> #include<iostream> using namespace std; long long n,m; long long sz[200010]; struct node { long long val,delta,l,r; node * ch[2]; }*root=NULL; long long sv(node * cur) { return cur?cur->val:0; } void update(node * cur) { cur->val=sv(cur->ch[0])+sv(cur->ch[1]); } void build(node * &cur,long long l,long long r) { if(l>r)return; cur=new node; cur->l=l;cur->r=r;cur->delta=0; if(l==r) { cur->val=sz[l]; cur->ch[0]=cur->ch[1]=NULL; } else { long long mid=(l+r)/2; build(cur->ch[0],l,mid); build(cur->ch[1],mid+1,r); update(cur); } } void down(node * cur) { if(cur->ch[0]) { cur->ch[0]->delta+=cur->delta; cur->ch[0]->val+=cur->delta*(cur->ch[0]->r-cur->ch[0]->l+1); } if(cur->ch[1]) { cur->ch[1]->delta+=cur->delta; cur->ch[1]->val+=cur->delta*(cur->ch[1]->r-cur->ch[1]->l+1); } cur->delta=0; } void add(node * cur,long long l,long long r,long long x) { if(l<=cur->l&&cur->r<=r) { cur->delta+=x; cur->val+=x*(cur->r-cur->l+1); } else { if(cur->delta)down(cur); long long mid=(cur->l+cur->r)/2; if(l<=mid)add(cur->ch[0],l,r,x); if(r>mid)add(cur->ch[1],l,r,x); update(cur);/*注意这个不能更少，当前区间val应该加多少，未知，要先加完他的左右孩子，再回来的时候更新它*/ } } long long query(node * cur,long long l,long long r) { if(l<=cur->l&&cur->r<=r)return cur->val; else { down(cur); long long mid=(cur->l+cur->r)/2; long long ans=0; if(l<=mid)ans+=query(cur->ch[0],l,r); if(r>mid)ans+=query(cur->ch[1],l,r); return ans; } } int main() { long long i; cin>>n; for(i=1;i<=n;i++)scanf("%lld",&sz[i]); build(root,1,n); cin>>m; for(i=0;i<m;i++) { long long a,b,c,d; scanf("%lld",&a); if(a==1) { scanf("%lld%lld%lld",&b,&c,&d); add(root,b,c,d); } else if(a==2) { scanf("%lld%lld",&b,&c); printf("%lld ",query(root,b,c)); } } return 0; }