线段树动态开点

核心思路

对于线段树这种暴力结构，其空间效率是比较底下的 O(4∗n) 。因此，我们想到一个方法来优化——动态开点。
也就是说，其实我们不需要一上来就把所有的节点全部建立起来，只需要在用到一个节点的时候再建立一个节点就可以了。

使用动态开点线段树的话，节点的下标将是无序的，因此必须建立结构体或用两个数组来分别保存一个节点的左右子节点

核心代码

int t[maxn<<1],lson[maxn<<1],rson[maxn<<1];//一个节点的值，一个节点的左儿子的下标，一个节点的右儿子的下标
int cnt;//用于记录已使用的节点的数量
inline void Pushup(int k){t[k]=t[lson[k]]+t[rson[k]];}
inline void update(int &k,int l,int r,int v,int x){
    /* 	函数功能：将数列中的第v个数修改为x
    	变量解释：&k:传入的数据是lson[k]或rson[k]，如果对应的下标未确定，就
    	        将在这个函数中确定。为了能修改对应变量的值，此处要使用引用参数
    	        （其实指针参数也行，但是太麻烦）
    	        l:当前节点的左边界
    	        r:当前节点的右边界
    	        v:目标点的序号
    	        x:值    */
    if(!k)k=++cnt;//如上文所说，如果该节点不存在，就建立这个节点
    if(l==r){//找到目标节点
        t[k]=x;//修改值
        return;//返回
    }
    int mid=(l+r)>>1;//二分
    if(v<=mid)update(lson[k],l,mid,v,x);//更新左儿子
    else update(rson[k],mid+1,r,v,x);//更新右儿子
    Pushup(k);//自更新
}
inline int query(int k,int L,int R,int l,int r){
    /*  函数功能：查询数列中[L,R]区间内所有数之和
    	变量解释：k:从update()中可以知道，如果一个节点不存在，那么它的左右儿子
    			必然不存在，也就是说如果一个节点不存在，那它的值就是0而在查询时
    			不需要新建节点，所以此处的k不需要引用
    		    L、R:需要查询的区间[L,R]
    		    l、r:当前节点的区间[l,r]    */
    if(!k)return 0;//如上文，如果一个节点不存在就返回0
    if(L<=l&&R>=r)return t[k];//线段树知识
    int mid=(l+r)>>1;
    int ans=0;//返回值
    if(L<=mid)ans+=query(lson[k],L,R,l,mid);//查询左儿子
    if(R>mid)ans+=query(rson[k],L,R,mid+1,r);//查询右儿子
    return ans;
}

洛谷线段树模板1示例代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
typedef long long ll;
ll t[maxn<<1],lazy[maxn<<1];//因为是区间修改所以需要lazy
int lson[maxn<<1],rson[maxn<<1];
int cnt=1;
int n,m;
inline void Pushup(int &k){t[k]=t[lson[k]]+t[rson[k]];}
inline void Pushdown(int k,int l,int r){
    if(lazy[k]){
        if(!lson[k])lson[k]=++cnt;
        if(!rson[k])rson[k]=++cnt;
        //动态开点的Pushdown就这两句不一样——如果这个节点的子节点没有开，就把他申请开
        lazy[lson[k]]+=lazy[k];
        lazy[rson[k]]+=lazy[k];
        int mid=(l+r)>>1;        
        t[lson[k]]+=(mid-l+1)*lazy[k];
        t[rson[k]]+=(r-mid)*lazy[k];
        lazy[k]=0;
    }
}
inline void build(int &k,int l,int r,int v,int x){//用单点修改的方式来建树
    if(!k)k=++cnt;
    if(l==r)t[k]=x;
    else{
        int mid=(l+r)>>1;
        if(v<=mid)build(lson[k],l,mid,v,x);
        else build(rson[k],mid+1,r,v,x);
        Pushup(k);
    }
}
inline void update(int &k,int l,int r,int L,int R,int x){
    if(!k)k=++cnt;
    if(L<=l&&R>=r){
        lazy[k]+=x;t[k]+=(r-l+1)*x;
    }else{
        Pushdown(k,l,r);
        int mid=(l+r)>>1;
        if(L<=mid)update(lson[k],l,mid,L,R,x);
        if(R>mid)update(rson[k],mid+1,r,L,R,x);
        Pushup(k);
    }
}
inline ll query(int k,int l,int r,int L,int R){
    if(!k)return 0;
    if(L<=l&&R>=r)return t[k];
    Pushdown(k,l,r);
    int mid=(l+r)>>1;
    ll ans=0;
    if(L<=mid)ans+=query(lson[k],l,mid,L,R);
    if(R>mid)ans+=query(rson[k],mid+1,r,L,R);
    return ans;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        int x;int temp=1;
        scanf("%d",&x);
        build(temp,1,n,i,x);
    }
    for(int i=1;i<=m;i++){
        int q;
        scanf("%d",&q);
        if(q==1){
            int L,R,x;
            scanf("%d%d%d",&L,&R,&x);
            int temp=1;
            update(temp,1,n,L,R,x);
        }else{
            int L,R;
            scanf("%d%d",&L,&R);
            printf("%lld\n",query(1,1,n,L,R));
        }
    }
    return 0;
}