线段树（模板）

题目： P3372 【模板】线段树 1

线段树：存线段
除建树外，其余操作的复杂度大部分都为O(lgn)
建一个叶子，首先要访问这个叶子，访问一个叶子的复杂度为O(lgn)
所以建n个叶子的复杂度为O(nlgn)
所以建树的复杂度为O(nlgn)

相对于差分，线段树可以边修改边查询
二叉树的性质可以简单推导，不用记

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int const N=1e5+7;
int n,m;
int a[N];
int lazy[N<<2];  //懒标记 
ll tree[N<<2];

void bulid(int p,int l,int r){
    if(l==r){ tree[p]=a[l];return ; }
    int mid=(l+r) >> 1;       //l加上r，再除以2 
    bulid(p*2,l,mid);
    bulid(p*2+1,mid+1,r);
    tree[p]=tree[p*2]+tree[p*2+1];
}

void pushdown(int p,int len){
    lazy[p*2]+=lazy[p];
    lazy[p*2+1]+=lazy[p];
    tree[p*2]+=(len-len/2)*lazy[p];
    tree[p*2+1]+=(len>>1)*lazy[p];   
    lazy[p]=0;
} 

void add(int p,int l,int r,int x,int y,int z){
    if(x<=l&&r<=y){  //(x,y)包含(l,r)，即(x,y)更大  像这样：(x (l,r) y) 
        lazy[p]+=z;
        tree[p]+=( (long long) (r-l+1) )*z;
        return ;
    }
    if(lazy[p]!=0) pushdown(p,r-l+1);
    int mid=(l+r) >> 1;
    if(x<=mid) add(p*2,l,mid,x,y,z) ;       // x<=mid 代表有左边（左子树），就进左边 
    if(y>=mid+1) add(p*2+1,mid+1,r,x,y,z);  // y>mid 代表有右边（右子树），就进右边 
    tree[p]=tree[p*2]+tree[p*2+1]; 
}

ll ask(int p,int l,int r,int x,int y){
    if(x<=l&&r<=y) return tree[p];
    if(lazy[p]!=0) pushdown(p,r-l+1);
    int mid=(l+r)>>1;
    //第一种搜索方法 
    ll res=0;
    if(x<=mid) res+=ask(p*2,l,mid,x,y);
    if(y>=mid+1) res+=ask(p*2+1,mid+1,r,x,y); 
    return res;
    /*以下是第二种搜索方法，为了方便和统一，以后线段树区间访问都用第一种 
    if(y<=mid) return find(p*2,l,mid,x,y);
    if(x>=mid+1) return find(p*2+1,mid+1,r,x,y); 
    return find(p*2,l,mid,x,mid)+find(p*2+1,mid+1,r,mid+1,y);
    */
}

int main(){
    cin >> n >> m;
    for(int i=1;i<=n;++i) cin >> a[i];
    bulid(1,1,n);
    while(m--){
        int a;
        cin >> a;
        if(a==1){
            int b,c,d;cin >> b >> c >> d;  
            add(1,1,n,b,c,d);   //第一个1表示从根（第一个点）开始搜索目标区间，然后修改，tree的一号位置表示(1,n)的状态，所以区间是1到n 
        }
        else{
            int b,c;cin >> b >> c;
            cout << ask(1,1,n,b,c) << endl;
        }
  }
  return 0; 
}