【CODEVS1082】线段树练习3

题目描述 Description

给你N个数，有两种操作：

1：给区间[a,b]的所有数增加X

2：询问区间[a,b]的数的和。

输入描述 Input Description

第一行一个正整数n，接下来n行n个整数，

再接下来一个正整数Q，每行表示操作的个数，

如果第一个数是1，后接3个正整数，

表示在区间[a,b]内每个数增加X,如果是2，

表示操作2询问区间[a,b]的和是多少。

输出描述 Output Description

对于每个询问输出一行一个答案

样例输入 Sample Input

1 2 3 2

2 2 3

样例输出 Sample Output

数据范围及提示 Data Size & Hint

数据范围

1<=n<=200000

1<=q<=200000

#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=2000000;
int tot=0;
long long a[3000000];
struct treetype
{
    int Left,Right; //区间[Left,Right) 
    int lptr,rptr;
    long long sum;
    long long bj;
}t[4*maxn];
void buildtree(int ll,int rr)
{
    int cur=++tot; // cur要在每层中新定义,或者用一个新变量存一下这层cur的值 
    t[cur].Left=ll; 
    t[cur].Right=rr;
    if(ll!=rr-1)
    {
        t[cur].lptr=tot+1;
        buildtree(ll,(ll+rr)/2);
        t[cur].rptr=tot+1;
        buildtree((ll+rr)/2,rr);
        t[cur].sum=t[t[cur].lptr].sum+t[t[cur].rptr].sum;
    }else t[cur].sum=a[ll];
}
void update(int k)
{
    t[t[k].lptr].sum+=t[k].bj*(t[t[k].lptr].Right-t[t[k].lptr].Left);
    t[t[k].rptr].sum+=t[k].bj*(t[t[k].rptr].Right-t[t[k].rptr].Left);
    t[t[k].lptr].bj+=t[k].bj;
    t[t[k].rptr].bj+=t[k].bj; 
    t[k].bj=0;
}
void change(int k,int ll,int rr,long long delta)
{
    if (ll<=t[k].Left&&rr>=t[k].Right)
    {
        t[k].sum+=delta*(t[k].Right-t[k].Left);
        t[k].bj+=delta;
    }
    else
    {
        if(t[k].bj) update(k);
        if (ll<(t[k].Left+t[k].Right)/2) 
            change(t[k].lptr,ll,rr,delta);
        if (rr>(t[k].Left+t[k].Right)/2)
            change(t[k].rptr,ll,rr,delta);
        t[k].sum=t[t[k].lptr].sum+t[t[k].rptr].sum;
    }
}
long long query(int k,int ll,int rr)
{
    if (ll<=t[k].Left&&rr>=t[k].Right) return t[k].sum;
    if (t[k].bj) update(k);
    long long ans=0;
    if (ll<(t[k].Left+t[k].Right)/2) ans+=query(t[k].lptr,ll,rr);
    if (rr>(t[k].Left+t[k].Right)/2) ans+=query(t[k].rptr,ll,rr);
    return ans;
}
int main()
{
    int n;
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%lld",&a[i]);
    buildtree(1,n+1);
    scanf("%d",&n);
    int at,x,y;
    long long p;
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&at);
        if (at==1){
            scanf("%d%d%lld",&x,&y,&p);
            change(1,x,y+1,p);
        }
        if (at==2){
            scanf("%d%lld",&x,&p);
            printf("%lld
",query(1,x,p+1));
        }
    }
    return 0;
}