1 #include <fstream>                 //点更新 2 #include <iostream> 3 #include <cstdio> 4  5 using namespace std; 6  7 const int N=10000; 8 int n,m,a[N]; 9 struct node10 {11     int left,right;12     int max_,sum_;13 }tree[4*N];14 15 void build(int id,int l,int r);//建一棵线段树16 int query_sum(int id,int l,int r);//查询区间和17 int query_max(int id,int l,int r);//查询区间最大值18 void update(int id,int pos,int val);//更新位置pos的值增加val19 20 int main()21 {22     //freopen("D:\\input.in","r",stdin);23     //freopen("D:\\output.out","w",stdout);24     int bo,t1,t2;25     scanf("%d%d",&n,&m);26     for(int i=1;i<=n;i++)27         scanf("%d",&a[i]);28     build(1,1,n);29     for(int i=1;i<=m;i++)30     {31         scanf("%d%d%d",&bo,&t1,&t2);32         if(bo)//更新(这里指增加)33             update(1,t1,t2);34         else35             printf("%d\n",query_sum(1,t1,t2));36     }37     return 0;38 }39 void build(int id,int l,int r)40 {41     tree[id].left=l;42     tree[id].right=r;43     if(l==r)44     {45         tree[id].sum_=a[l];46         tree[id].max_=a[l];47     }48     else49     {50         int mid=(l+r)/2;51         build(2*id,l,mid);52         build(2*id+1,mid+1,r);53         tree[id].sum_=tree[2*id].sum_+tree[2*id+1].sum_;54         tree[id].max_=max(tree[2*id].max_,tree[2*id+1].max_);55     }56 }57 int query_sum(int id,int l,int r)58 {59     if(tree[id].left==l&&tree[id].right==r)60         return tree[id].sum_;61     else62     {63         int mid=(tree[id].left+tree[id].right)/2;64         if(r<=mid)  return query_sum(2*id,l,r);65         else if(l>mid)  return query_sum(2*id+1,l,r);66         else67             return query_sum(2*id,l,mid)+query_sum(2*id+1,mid+1,r);68     }69 }70 int query_max(int id,int l,int r)71 {72     if(tree[id].left==l&&tree[id].right==r)73         return tree[id].max_;74     else75     {76         int mid=(tree[id].left+tree[id].right)/2;77         if(r<=mid)  return query_max(2*id,l,r);78         else if(l>mid)  return query_max(2*id+1,l,r);79         else80             return max(query_max(2*id,l,mid),query_max(2*id+1,mid+1,r));81     }82 }83 void update(int id,int pos,int val)84 {85     if(tree[id].left==tree[id].right)86     {87         tree[id].sum_+=val;//假如修改而不是增加，就把+=改为=。88         tree[id].max_+=val;89     }90     else91     {92         int mid=(tree[id].left+tree[id].right)/2;93         if(pos<=mid)    update(2*id,pos,val);94         else update(2*id+1,pos,val);95         tree[id].sum_=tree[2*id].sum_+tree[2*id+1].sum_;96         tree[id].max_=max(tree[2*id].max_,tree[2*id+1].max_);97     }98 }

  1 #include <fstream>  2 #include <iostream>  3 #include <cstdio>  4   5 using namespace std;  6   7 const int N=100005;  8 int n,m,a[N];  9 struct node 10 { 11     int left,right; 12     long long lazy,sum_; 13 }tree[4*N]; 14  15 void build(int id,int l,int r);//建一棵线段树 16 long long query_sum(int id,int l,int r);//查询区间和 17 void update(int id,int p1,int p2,int val);//更新区间[p1,p2]的值增加val 18  19 int main() 20 { 21     //freopen("D:\\input.in","r",stdin); 22     //freopen("D:\\output.out","w",stdout); 23     int bo,t1,t2,t3; 24     scanf("%d%d",&n,&m); 25     for(int i=1;i<=n;i++) 26         scanf("%d",&a[i]); 27     build(1,1,n); 28     for(int i=1;i<=m;i++) 29     { 30         scanf("%d%d%d",&bo,&t1,&t2); 31         if(bo)//更新(这里指增加) 32         { 33             scanf("%d",&t3); 34             update(1,t1,t2,t3); 35         } 36         else 37             printf("%lld\n",query_sum(1,t1,t2)); 38     } 39     return 0; 40 } 41 void build(int id,int l,int r) 42 { 43     tree[id].left=l; 44     tree[id].right=r; 45     tree[id].lazy=0; 46     if(l==r) 47     { 48         tree[id].sum_=a[l]; 49     } 50     else 51     { 52         int mid=(l+r)/2; 53         build(2*id,l,mid); 54         build(2*id+1,mid+1,r); 55         tree[id].sum_=tree[2*id].sum_+tree[2*id+1].sum_; 56     } 57 } 58 long long query_sum(int id,int l,int r) 59 { 60     if(tree[id].left==l&&tree[id].right==r) 61         return tree[id].sum_; 62     else 63     { 64         int mid=(tree[id].left+tree[id].right)/2; 65         if(tree[id].lazy) 66         { 67             update(2*id,tree[id].left,mid,tree[id].lazy); 68             update(2*id+1,mid+1,tree[id].right,tree[id].lazy); 69             tree[id].lazy=0; 70         } 71         if(r<=mid)  return query_sum(2*id,l,r); 72         else if(l>mid)  return query_sum(2*id+1,l,r); 73         else 74             return query_sum(2*id,l,mid)+query_sum(2*id+1,mid+1,r); 75     } 76 } 77 void update(int id,int p1,int p2,int val) 78 { 79     if(tree[id].left==p1&&tree[id].right==p2) 80     { 81         tree[id].lazy+=val; 82         tree[id].sum_+=val*(p2-p1+1); 83     } 84     else 85     { 86         int mid=(tree[id].left+tree[id].right)/2; 87         if(tree[id].lazy) 88         { 89             update(2*id,tree[id].left,mid,tree[id].lazy); 90             update(2*id+1,mid+1,tree[id].right,tree[id].lazy); 91             tree[id].lazy=0; 92         } 93         if(p2<=mid) 94             update(2*id,p1,p2,val); 95         else if(p1>mid) 96             update(2*id+1,p1,p2,val); 97         else 98         { 99             update(2*id,p1,mid,val);100             update(2*id+1,mid+1,p2,val);101         }102         tree[id].sum_=tree[2*id].sum_+tree[2*id+1].sum_;103     }104 }