洛谷p13825题目链接：P13825 【模板】线段树 1.5 - 洛谷

阅读本文需要有维护普通线段树的前置知识，如果还不会的可以先去我以前的文章了解如何维护普通的线段树，有超详细的图解及代码解析，链接：https://blog.csdn.net/h_a_o777oah/article/details/158577964

注：为了方便代码书写，这里的所有代码的 long long 都用 ll 来代替。

一，普通线段树痛点

我们可以知道，线段树是一个非常好用的数据结构。但是，普通的线段树需要我们开一个比原来数组还要多整整四倍的空间才能保证能完全存下所有数据。在面对数据量不大，如$10^5$的时候还好，如果数据量大，比如$10^9$，问题就出现了。先不论空间，我们仅仅是建树操作build就已经超时了，因为建树的操作是O(n)。

再看看内存空间，比赛一般都会限制使用128MB，在C/C++的标准中，我们的结构体是有两个long long类型和两个int类型的，一个结构体占了24个字节，如果我们开$10^9$大小的数组，就要大小约22888MB的内存，换算一下就大约是22.9GB（不知道算得对不对，如有错误请提出），更别说我们要开四倍空间。这么做必然爆内存！

就像洛谷p13825这道题，看上去和原来的洛谷p3372区别不大，但是仔细看就能发现，他的n的数据量是$10^9$，如果套用p3372代码肯定只能收获满屏WA（悲）。

那我们回想一下洛谷p3372的维护普通线段树的代码，我们开了四倍的空间。可是实际上呢？我们这么多次查找和修改，其实有一些地方的节点根本没用到，可是我们却把他们提前开好存进数组。这也太浪费内存了！那我们当然也不傻，这节点不用我干嘛要开出来？等我用到再开出来吧。这就是动态开点优化的核心思想：只开用得到的节点，用不到的就暂时不管。

二，动态开点实现思路

那我们也要定义一个结构体，但是这次的条件不一样了。以前普通的用4倍空间存储的线段树是堆式存储数据的，我们访问当前节点 p 的左子节点可以p<<1，右子节点可以(p<<1)+1，这个是利用了完全二叉树的性质；但为了省内存，这次我们必须放弃掉这个完全二叉树的性质了，转而在结构体中存左子节点和右子节点的索引，像指针一样来查找子节点。

struct node
{
    ll sum,lazy;//区间和与懒标记
    int l,r;//l是左子节点的索引，r是右子节点的索引
}

但是一个重要的问题出现了，我们总要开一个数组来存储树的节点，那我们要开多少呢？

正常来说，按照惯性思维，感觉这个树的节点数组大小肯定只和我要维护的数组大小有关吧？但是并非如此，我们动态开点是为了应付别人的查找和修改的，所以，我们还需要关注一下有多少次询问？每次询问我要开几个节点？

我们来看看，每次询问我们会最多开几个节点？先明确一下树的高度是 logn ，在最坏情况下，每次递归都新开两个节点，一直到达底部叶子节点，那每次最坏情况下，新开的树节点数量就是 logn × 2。我们一共要查询 m 次，那公式就是 m × logn × 2。根据洛谷p13825题目，n=$10^9$，m=$10^5$，那 logn 大概是29.9，约等于30。所以数组大小就很明显了。

#define maxn 100005
struct node
{
    ll sum,lazy;
    int l,r;
}tr[maxn*60];

那就有个疑问了：开这么大数组，还是可能有溢出风险啊！万一之后我算错了呢？开大了MLE了呢？要不我用个vector数组来偷偷懒得了。但事实上，最好别这么干。vector数组内部源码是扩容机制的，达到上限就会倍增扩容，这个数组在内存中的地址会变化，是非固定的。先不说后续的修改 chag 代码很难操作，就万一你的vector数组到70MB了，vector这傻子自动就扩容扩大两倍，那就140MB了，已经超越了题目限制128MB。

以洛谷p13825题目为例，注意题目条件给了初始条件数组是以1为开头的等差数列，不要看漏了（我第一次做的时候真没注意到），我们以 n=4 ，维护数组1，2，3，4为例子。

因为这个数组是等差数列，所以我们先写一个getsum函数来方便以后获取区间值。

ll getsum(int l,int r)
{
    if(l>r) return 0;
    return (ll)(l+r)*(r-l+1)/2;
}

既然要动态开点，那我们肯定不能像之前一样build一整个树，但是我们还是要先建一个根节点，按习惯分配编号为1。

这个区间[1,4]就是我们要维护的整个数组大小了。其实节点维护的区间可以不必在结构体内显式表达，在函数里面传参也可以做到知道这个节点维护哪个大小的区间。我在这里写出来是为了更清晰表达，旁边的 l 和 r 分别是指左节点和右节点的编号索引。

三，chag修改区间和

既然不要build了，那就直接开始修改和查找吧！先说修改chag，比如，我们要让区间 [1,3] 的所有值都加5。

我们从根节点往下，这个区间大小我们两边子节点都要走一下，所以要开出两边子节点并初始化。

这时候左边到了子区间[1,2]，直接修改加懒标记return了，但右边还要往下走，我们开出来子节点4。

以下图是节点4已更新的样子

然后就是经典的更新父节点了。但有个问题必须注意，在之前我们更新直接是 左子节点sum+右子节点sum 。但在这里更新节点3的时候，我们的右子节点还没创建出来！！！所以不能像之前一样直接取用子节点sum值了，而是要加入一个判断：子节点索引为0，说明还没修改过，我们直接使用它的初始值（也就是getsum的区间值）；如果索引不为0，那就可以直接取用sum值了。后面代码使用三目运算符会更加简洁。

修改完成后如下

到这里就修改成功了！我们可以看到，我们这次修改仅仅开了三个新点。和普通线段树比起来，我们“阉割”了那些用不上的点，极大地节省了内存（在这次区间修改很明显比普通线段树节省了一半内存）。

由于和普通线段树在pushdown懒标记，更新父节点等等操作都一样，这里只演示一次动态开点的过程，后面不再演示。不会的可以在开头链接去看上期普通线段树操作，会有更详细的演示。

在代码中，我们用 cnt 变量来给每个节点赋值编号。

以下是chag函数代码：

void chag(int &p,int l,int r,int chgl,int chgr,ll val)
{
    if(!p)//如果该节点不存在，即为0，那要马上创造一个出来
    {
        p=++cnt;//分配编号
        tr[p].sum=getsum(l,r);//初始化区间值
        tr[p].lazy=0;
    }
    if(chgl<=l&&chgr>=r)//到达子区间，不用往下了，修改区间值，打上懒标记就return
    {
        tr[p].sum+=val*(r-l+1);
        tr[p].lazy+=val;
        return;
    }
    pushdown(p,l,r);//下放懒标记
    int mid=l+((r-l)>>1);//不要再写(l+r)>>1,数据量大可能会溢出，使用这个优化写法
    //以下递归和普通版本线段树基本相同
    if(chgl<=mid) chag(tr[p].l,l,mid,chgl,chgr,val);
    if(chgr>mid) chag(tr[p].r,mid+1,r,chgl,chgr,val);
    //出现区别：动态开点线段树的左右子节点都有可能没有被创建
    ll lval= tr[p].l==0 ? getsum(l,mid) : tr[tr[p].l].sum;
    ll rval= tr[p].r==0 ? getsum(mid+1,r) : tr[tr[p].r].sum;
    tr[p].sum=lval+rval;
}

在这里，函数参数p是指当前节点，l 和 r 分别指的是该节点维护的区间大小，为了区分开，我把修改的总区间命名为 chgl 和 chgr ，val 是要增加或者减少的值。其实和普通线段树基本相同。

要注意参数 p ，使用了引用&，等于是将指针传入函数，可以修改参数 p 的值。因为开点要给节点赋值编号，所以必须传入指针。这也是为什么我们不能使用vector数组，因为vector数组的内存地址可能不停在改变，而传引用指向的内存地址是不变的，一旦vector触发扩容，内存地址改变，那引用的 p 就会读到垃圾值。（当然可以不用引用写法，这里不做讨论）

四，pushdown下放懒标记

接下来看看pushdown函数的书写，l 和 r 是节点 p 管理的区间左边界和右边界。

void pushdown(int p,int l,int r)
{
    if(!tr[p].lazy) return;
    int mid=l+((r-l)>>1);
    if(!tr[p].l)//检查左子节点是否存在，不存在就创建
    {
        tr[p].l=++cnt;
        tr[tr[p].l].sum=getsum(l,mid);
        tr[tr[p].l].lazy=0;
    }
    //这里和普通线段树一样下放懒标记
    tr[tr[p].l].sum+=tr[p].lazy*(mid-l+1);
    tr[tr[p].l].lazy+=tr[p].lazy;

    if(!tr[p].r)//检查右子节点是否存在，不存在就创建
    {
        tr[p].r=++cnt;
        tr[tr[p].r].sum=getsum(mid+1,r);
        tr[tr[p].r].lazy=0;
    }
    //这里和普通线段树一样下放懒标记
    tr[tr[p].r].sum+=tr[p].lazy*(r-mid);
    tr[tr[p].r].lazy+=tr[p].lazy;
    tr[p].lazy=0;//节点懒标记清零
}

其实很明显，只是比普通线段树多了两个 if 判断看节点是否存在而已，几乎没有大变化。

五，ask查询区间和

再来看看ask函数。

ll ask(int p,int l,int r,int askl,int askr)
{
    if(!p)//子节点不存在，我们要求的是总区间[askl,askr]和子区间[l,r]的交集
    {
        int tl=max(l,askl);
        int tr=min(r,askr);
        return getsum(tl,tr);
    }
    if(l>=askl&&r<=askr) return tr[p].sum;
    pushdown(p,l,r);
    ll ans=0;
    int mid=l+((r-l)>>1);
    if(askl<=mid) ans+=ask(tr[p].l,l,mid,askl,askr);
    if(askr>mid) ans+=ask(tr[p].r,mid+1,r,askl,askr);
    return ans;
}

到了不存在的子节点，我们要求大区间 [askl,askr]和小区间 [l,r] 的交集。因为ask到这里节点还没存在，说明这个区间都没有被修改过，直接拿走我们需要的区间长度的初始值就行了。除此之外，和普通线段树基本相同。

到这里其实发现，动态开点并非什么高深算法，也不过是人类“偷懒”的产物。至此我们已经完全掌握动态开点了。但是洛谷这个题目比较恶心，使用long long仍然会溢出，只能使用gcc编译器的__int128类型了。但是这个数据类型并不支持IO流输入输出，只能手写输入read和print函数来输入输出了。写得时候要注意read的传参必须要使用引用&。

六，P13825 AC代码

最后是洛谷p13825的AC代码，也可当作模板。（图个方便我就直接让ll=__int128了）

#include <bits/stdc++.h>
#define maxn 100005
#define endl '\n'
using namespace std;
using ll=__int128;
int n,m;
void read(ll &x)
{
    x=0;
    ll f=1;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        x=x*10+(ch-'0');
        ch=getchar();
    }
    x=x*f;
}
void print(ll x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9) print(x/10);
    putchar(x%10+'0');
}
struct node
{
    ll sum,lazy;
    int l,r;
}tr[maxn*60];
int root,cnt;
ll getsum(int l,int r)
{
    if(l>r) return 0;
    return (ll)(l+r)*(r-l+1)/2;
}
void pushdown(int p,int l,int r)
{
    if(!tr[p].lazy) return;
    int mid=l+((r-l)>>1);
    if(!tr[p].l)
    {
        tr[p].l=++cnt;
        tr[tr[p].l].sum=getsum(l,mid);
        tr[tr[p].l].lazy=0;
    }
    tr[tr[p].l].sum+=tr[p].lazy*(mid-l+1);
    tr[tr[p].l].lazy+=tr[p].lazy;
    if(!tr[p].r)
    {
        tr[p].r=++cnt;
        tr[tr[p].r].sum=getsum(mid+1,r);
        tr[tr[p].r].lazy=0;
    }
    tr[tr[p].r].sum+=tr[p].lazy*(r-mid);
    tr[tr[p].r].lazy+=tr[p].lazy;
    tr[p].lazy=0;
}
void chag(int &p,int l,int r,int chgl,int chgr,ll val)
{
    if(!p)
    {
        p=++cnt;
        tr[p].sum=getsum(l,r);
        tr[p].lazy=0;
    }
    if(chgl<=l&&chgr>=r)
    {
        tr[p].sum+=val*(r-l+1);
        tr[p].lazy+=val;
        return;
    }
    pushdown(p,l,r);
    int mid=l+((r-l)>>1);
    if(chgl<=mid) chag(tr[p].l,l,mid,chgl,chgr,val);
    if(chgr>mid) chag(tr[p].r,mid+1,r,chgl,chgr,val);
    ll lval= tr[p].l==0 ? getsum(l,mid) : tr[tr[p].l].sum;
    ll rval= tr[p].r==0 ? getsum(mid+1,r) : tr[tr[p].r].sum;
    tr[p].sum=lval+rval;
}
ll ask(int p,int l,int r,int askl,int askr)
{
    if(!p)
    {
        int tl=max(l,askl);
        int tr=min(r,askr);
        return getsum(tl,tr);
    }
    if(l>=askl&&r<=askr) return tr[p].sum;
    pushdown(p,l,r);
    ll ans=0;
    int mid=l+((r-l)>>1);
    if(askl<=mid) ans+=ask(tr[p].l,l,mid,askl,askr);
    if(askr>mid) ans+=ask(tr[p].r,mid+1,r,askl,askr);
    return ans;
}
int main()
{
    cin>>n>>m;
    root=++cnt;
    tr[root].sum=getsum(1,n);
    for(int i=1;i<=m;++i)
    {
        int op;
        cin>>op;
        if(op==1)
        {
            int x,y;
            ll k;
            cin>>x>>y;
            read(k);
            chag(root,1,n,x,y,k);
        }else
        {
            int x,y;
            cin>>x>>y;
            print(ask(root,1,n,x,y));
            putchar('\n');
        }
    }
}

学习完线段树及动态开点，也就有了学习可持久化线段树即主席树的基础，且难度也不是特别大了。如果有兴趣的可以继续阅读我的博客继续学习可持久化线段树，博客链接：【数据结构】可持久化线段树：图解原理逻辑及版本实现细节（洛谷 P3919 C++代码）-CSDN博客