P3372 【模板】线段树 1

题目链接：

题目：

题目描述

如题，已知一个数列，你需要进行下面两种操作：

1.将某区间每一个数加上x

2.求出某区间每一个数的和

输入格式

第一行包含两个整数N、M，分别表示该数列数字的个数和操作的总个数。

第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。

接下来M行每行包含3或4个整数，表示一个操作，具体如下：

操作1： 格式：1 x y k 含义：将区间[x,y]内每个数加上k

操作2： 格式：2 x y 含义：输出区间[x,y]内每个数的和

输出格式

输出包含若干行整数，即为所有操作2的结果。

输入输出样例

输入 #1

5 51 5 4 2 32 2 41 2 3 22 3 41 1 5 12 1 4

输出 #1

11820

说明/提示

时空限制：1000ms,128M

数据规模：

对于30%的数据：N<=8，M<=10

对于70%的数据：N<=1000，M<=10000

对于100%的数据：N<=100000，M<=100000

（数据已经过加强^_^，保证在int64/long long数据范围内）

样例说明：

 

 

//// Created by hanjinyu on 19-9-2.//#include
      
       using namespace std;typedef long long ll;const int maxn=1e6+10;int input[maxn];struct Node{    ll left;    ll right;    ll num;    ll lazy;}tree[maxn*4];void PushUp(int root){    tree[root].num=tree[root<<1].num+tree[root<<1|1].num;}void PushDown(int root){    if(tree[root].lazy>0)    {        tree[root<<1].lazy+=tree[root].lazy;        tree[root<<1|1].lazy+=tree[root].lazy;        tree[root<<1].num+=tree[root].lazy*(tree[root<<1].right-tree[root<<1].left+1);        tree[root<<1|1].num+=tree[root].lazy*(tree[root<<1|1].right-tree[root<<1|1].left+1);        tree[root].lazy=0;    }}void Build(int root,int l,int r){    tree[root].left=l;    tree[root].right=r;    if(l==r)    {        tree[root].num=input[l];        return;    }    int mid=(l+r)>>1;    Build(root<<1,l,mid);    Build(root<<1|1,mid+1,r);    PushUp(root);}void change(int root,int l,int r,int k){    if(tree[root].left>=l&&tree[root].right<=r)    {        tree[root].num+=k*(tree[root].right-tree[root].left+1);        tree[root].lazy+=k;        return;    }    PushDown(root);    if(l<=tree[root<<1].right)        change(root<<1,l,r,k);    if(r>=tree[root<<1|1].left)        change(root<<1|1,l,r,k);    PushUp(root);}ll Q(int root,int l,int r){    ll ans=0;    if(tree[root].left>=l&&tree[root].right<=r)    {        return tree[root].num;    }    PushDown(root);    if(l<=tree[root<<1].right)        ans+=Q(root<<1,l,r);    if(r>=tree[root<<1|1].left)        ans+=Q(root<<1|1,l,r);    return ans;}int main(){    int n,m;    scanf("%d%d",&n,&m);    for(int i=1;i<=n;i++)    {        scanf("%d",&input[i]);    }    Build(1,1,n);    int a,x,y,k;    for(int i=0;i