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[];
}*root=NULL;
void input()
{
scanf("%d",&n);
for(long long int i=;i<=n;++i)
scanf("%d",&sz[i]);
}
void update(node *cur)
{
cur->val=cur->child[]->val+cur->child[]->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=;
if(l==r)
{
cur->child[]=cur->child[]=NULL;
cur->val=sz[l];
return;
}
long long int mid=(l+r)/;
bulid(cur->child[],l,mid);
bulid(cur->child[],mid+,r);
update(cur);
}
void down(node *cur)
{
if(cur->child[])
{
long long int l1=cur->child[]->l,r1=cur->child[]->r;
cur->child[]->val+=(r1-l1+)*cur->delta;
cur->child[]->delta+=cur->delta;
}
if(cur->child[])
{
long long int l1=cur->child[]->l,r1=cur->child[]->r;
cur->child[]->val+=(r1-l1+)*cur->delta;
cur->child[]->delta+=cur->delta;
}
cur->delta=;
}
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+)*x;
cur->delta+=x;
return ;
}
if(cur->delta) down(cur);
long long int mid=(cur->l+cur->r)/;
if(l<=mid) add(cur->child[],l,r,x);
if(r>mid) add(cur->child[],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=,mid=(cur->l+cur->r)/;
if(l<=mid) ans+=query(cur->child[],l,r);
if(r>mid) ans+=query(cur->child[],l,r);
return ans;
}
int main()
{
input();
bulid(root,,n);
scanf("%d",&q);
while(q--)
{
scanf("%d",&x);
if(x==)
{
scanf("%d%d%d",&a,&b,&c);
add(root,a,b,c);
}
else {
scanf("%d%d",&a,&b);
printf("%lld\n",query(root,a,b));
}
}
return ;
}
teacher's
代码自己尝试写了一下
/*数据类型必须用long long才能过*/
#include<cstdio>
#include<iostream>
using namespace std;
long long n,m;
long long sz[];
struct node
{
long long val,delta,l,r;
node * ch[];
}*root=NULL;
long long sv(node * cur)
{
return cur?cur->val:;
}
void update(node * cur)
{
cur->val=sv(cur->ch[])+sv(cur->ch[]);
}
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=;
if(l==r)
{
cur->val=sz[l];
cur->ch[]=cur->ch[]=NULL;
}
else
{
long long mid=(l+r)/;
build(cur->ch[],l,mid);
build(cur->ch[],mid+,r);
update(cur);
}
}
void down(node * cur)
{
if(cur->ch[])
{
cur->ch[]->delta+=cur->delta;
cur->ch[]->val+=cur->delta*(cur->ch[]->r-cur->ch[]->l+);
}
if(cur->ch[])
{
cur->ch[]->delta+=cur->delta;
cur->ch[]->val+=cur->delta*(cur->ch[]->r-cur->ch[]->l+);
}
cur->delta=;
}
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+);
}
else
{
if(cur->delta)down(cur);
long long mid=(cur->l+cur->r)/;
if(l<=mid)add(cur->ch[],l,r,x);
if(r>mid)add(cur->ch[],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)/;
long long ans=;
if(l<=mid)ans+=query(cur->ch[],l,r);
if(r>mid)ans+=query(cur->ch[],l,r);
return ans;
}
}
int main()
{
long long i;
cin>>n;
for(i=;i<=n;i++)scanf("%lld",&sz[i]);
build(root,,n);
cin>>m;
for(i=;i<m;i++)
{
long long a,b,c,d;
scanf("%lld",&a);
if(a==)
{
scanf("%lld%lld%lld",&b,&c,&d);
add(root,b,c,d);
}
else if(a==)
{
scanf("%lld%lld",&b,&c);
printf("%lld\n",query(root,b,c));
}
}
return ;
}
mine