线段树

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1E5+7; 
ll arr[N];
ll tree[N+N+N];
//如果我们的tree从0开始，那么左儿子为2*node+1，右儿子为2*node+2; 
//从1开始的话，左二子就是2*node,右儿子是2*node+1;
//在此我们都从0开始； 
void buid_tree(ll node,ll start,ll end){//建树 
    if(start==end){
        tree[node]=arr[end];
        return ;
    }
    ll mid=(start+end)>>1;
    ll left_node  =2*node+1;
    ll right_node =2*node+2;
    buid_tree(left_node ,start,mid);
    buid_tree(right_node,mid+1,end);
    tree[node]=tree[left_node]+tree[right_node];
}


void update_tree(ll node,ll start,ll end,ll idx,ll value){//节点更新 
    
    if(start==end) {
        arr[idx]+=value;
        tree[node]+=value;
        return ;
    }
    ll mid=(start+end) / 2 ;
    ll left_node=2*node+1;
    ll right_node=2*node+2;
    if(idx>=start && idx<=mid)    update_tree(left_node,start,mid,idx,value);
    else update_tree(right_node,mid+1,end,idx,value);
    tree[node]=tree[left_node]+tree[right_node];
}

ll  query_tree(ll node,ll start,ll end,ll l,ll r){//查询函数 
    
    
    if(l>end||r<start) return 0;
    else if(l<=start&&end<=r) return tree[node];
    else if(start==end) return tree[node];
    
    
    
    ll mid=(start+end)/2;
    ll left_node=2*node+1;//左儿子 
    ll right_node=2*node+2;//右儿子 
    ll sum_left=query_tree(left_node,start,mid,l,r);
    ll sum_right=query_tree(right_node,mid+1,end,l,r);
    return sum_left+sum_right;
}

int main(){
    ios::sync_with_stdio(false);
    ll n,m;
    cin>>n>>m;
    for(ll i=0;i<n;i++) cin>>arr[i];
    buid_tree(0,0,n-1);
    for(ll i=1;i<=m;i++){
        ll t ;
        cin>>t;
        if(t==1){
            ll x,y,value;
            cin>>x>>y>>value;
            //由于是单点更新，只能是一个点一个点的更新 
            for(ll j=x;j<=y;j++) update_tree(0,0,n-1,j-1,value);
        }
        
        else {
            ll  x,y;
            cin>>x>>y;
            x--,y--;
            cout<<query_tree(0,0,n-1,x,y)<<endl;
        }
    }
    return 0;
}
 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=5E5+7;
ll arr[N];
//对于本题，我们要用到区间更新，区间跟新与单点更新的区别之一就是区间更新用结构体，多了一个mark，用来标记
//某个节点是否需要跟新
//还有就是要在结构体中加l,r即当前节点维护的区间和，因为我们是累加的当前节点的增加的数值应该是当前值乘以区间长度；（有的不是，
//具体情况具体分析）
 
struct stu{
    ll l,r; 
    ll now;
    ll mark;
}tree[N];
void buid_tree(ll node,ll start,ll end){
    tree[node].mark=0;
    tree[node].l=start;
    tree[node].r=end;
    if(start==end){
        tree[node].now=arr[end];
        return ;
    }
    ll mid=(start+end)/2;
    ll left_node=2*node+1;
    ll right_node=2*node+2;
    buid_tree(left_node,start,mid);
    buid_tree(right_node,mid+1,end);
    tree[node].now=tree[left_node].now+tree[right_node].now;
}

void pushdown(ll root){
    ll left_node =root*2+1;
    ll right_node=root*2+2; 
    if(tree[root].mark!=0){
        tree[left_node].mark  +=tree[root].mark;
        tree[right_node].mark +=tree[root].mark;        
        tree[left_node].now   +=tree[root].mark*(tree[left_node].r-tree[left_node].l+1);
        tree[right_node].now  +=tree[root].mark*(tree[right_node].r-tree[right_node].l+1);
        tree[root].mark=0;
    }
}
void update_tree(ll node,ll start,ll end,ll l,ll r,ll value){
    if(end<l||start>r) return ;
    
    else if(start>=l&&end<=r) {
        tree[node].mark +=value;
        tree[node].now  +=value*(end-start+1);
        return ;
    }
    
    pushdown(node);//以当前节点为根节点往下延伸 
    ll mid=(start+end) / 2;
    ll left_node=2*node+1;
    ll right_node=2*node+2;
    
    update_tree(left_node,start,mid,l,r,value);
    update_tree(right_node,mid+1,end,l,r,value);    
    tree[node].now=tree[left_node].now+tree[right_node].now;    
}


ll query_tree(ll node,ll start,ll end,ll l,ll r){
    
    
    if(end<l||start>r) return 0;
    else if(start>=l&&end<=r) return tree[node].now;
    
    pushdown(node);//延伸处理； 
    ll mid=(start+end)/2;
    ll left_node=2*node+1;
    ll right_node=2*node+2;
    ll sum_left=query_tree(left_node,start,mid,l,r);
    ll sum_right=query_tree(right_node,mid+1,end,l,r);
    return sum_left+sum_right;
}
int main(){
    memset(tree,0,sizeof tree);
    ll n,m;
    cin>>n>>m;
    for(ll i=0;i<n;i++)    cin>>arr[i];
    
    buid_tree(0,0,n-1);    
    for(ll i=0;i<m;i++){
        ll t;
        cin>>t;
        if(t==1){
            ll l,r,value;
            cin>>l>>r>>value;
            l--,r--;
            update_tree(0,0,n-1,l,r,value);
        }
        else{
            ll x,y;
            cin>>x>>y;
            x--,y--;
            cout<<query_tree(0,0,n-1,x,y)<<endl;
        }
    }
    return 0;
}