前言

"老师求留！"

做了个博客网站，大家可以看看 (^_^)：与日的个人网站

（注：因为备案还没过，所以暂时用 服务器的 IP 地址 ，等备案过了这条注释再删除，虽然蛮不安全的）

0x1. 动态开点线段树：从固态思维到节省内存

温馨提示 : 如果你已经看过了 2020 严誉沣的 《暑假知识点笔记合集》，那么你可以阅读这个帖子加强理解。

首先，请您先习惯我的码风：

#include <iostream>
using namespace std;

const int MAXN=1e6+5;

char str[MAXN]={'?','h','e','l','l','o',' ','w','o','r','l','d'};
int n;

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cout<<str[i];
    }
    return 0;
}

其实蛮明显的，这里就不再说什么了。

0x10. 内存不够？：我自己出的模板题

例题：

内存、时间限制 :
好多好多 M, 1s

题目描述 :
有一个 长度为 n 的区间, 现在要对这个区间进行 q 次操作。
对于 操作 1, 格式为 1 l r k, 区间[l,r]每个数 增加 k。 对于 操作 2, 格式为 2 l r, 输出区间[l,r]的 和。

数据范围 :
1<=n<=好多好多, 1<=q<=没有 n 多。

输入 :
第一行输入两个整数 n 和 q 。
后面 q 行输入 q 次操作, 同题目描述。

输出 :
根据操作 2 输出。

样例输入 :

7 4
1 2 5 5
2 3 7
2 1 3
2 4 7

样例输出 : (我也不知道)

内存多少我也不知道怎么定，总之平常的线段树不能存就是了。

（这道题有时间的话我应该会放在我的网站上）

对于这种情况，就需要使用到这期要讲的动态开点线段树了。

0x12. 关于动态开点线段树

动态开点线段树与平常的线段树最大的区别就在于前者的编号是根据创建顺序来分的，也就是说，左右子节点也不是 2x 和 2x+1 了，而是通过创建来确定。

我们每个节点现在多了两个变量，分别存的是左右子节点的编号：

struct node
{
    int sum,tag;
    int l_son,r_son;
}tr[MAXN];

然后再是 push_up 操作，因为我们不能用 2x 和 2x+1 来访问左右子节点了，所以要改成这样：

void push_up(int p)
{
    int lft=tr[p].l_son;
    int rgt=tr[p].r_son;
    tr[p].sum=tr[lft].sum+tr[rgt].sum;
}

接下来是 push_down：

void push_down(int &p,int l,int r)
{
    if(tr[p].tag)
    {
        int mid=(l+r)>>1;
        adt(tr[p].l_son,l,mid,tr[p].tag);
        adt(tr[p].r_son,mid+1,r,tr[p].tag);
        tr[p].tag=0;
    }
}

因为我们不知道我们在下传标记的时候是否会访问到未创建的节点，所以在 adt 函数里就要判断当前节点是否创建：

void adt(int &p,int l,int r,int k)
{
    if(p==0)
    {
        id++;
        p=id;
        tr[p].l_son=0;
        tr[p].r_son=0;
        tr[p].sum=0; 
    }
    tr[p].sum+=(r-l+1)*k;
    tr[p].tag+=k;
}

id 是当前节点到了第几个。

这里使用引用的好处是，既能改变 push_down 里的 l_son，r_son，又能创建新的编号给节点赋值，一举两得。

然后是用于增加 k 的 update 函数：

void upt(int &p,int l,int r,const int &cl,const int &cr,int k)
{
    if(p==0)
    {
        id++;
        p=id;
        tr[p].l_son=0;
        tr[p].r_son=0;
        tr[p].sum=0;
    }
    if(cl<=l&&r<=cr)
    {
        adt(p,l,r,k);
        return ;
    }
    push_down(p,l,r);
    int mid=(l+r)>>1;
    if(cl<=mid)
    {
        upt(tr[p].l_son,l,mid,cl,cr,k);
    }
    if(cr>mid)
    {
        upt(tr[p].r_son,mid+1,r,cl,cr,k);
    }
    push_up(p);
}

[cl, cr]是查询区间，[l, r]是当前区间，然后和前文一样，如果访问到未创建的节点就创建，使用引用也是为了给上层的 l_son，r_son 赋值。

最后是 query 函数：

int qry(int &p,int l,int r,const int &cl,const int &cr)
{
    if(p==0)
    {
        return 0;
    }
    if(cl<=l&&r<=cr)
    {
        return tr[p].sum;
    }
    push_down(p,l,r);
    int mid=(l+r)>>1;
    int res=0;
    if(cl<=mid)
    {
        res+=qry(tr[p].l_son,l,mid,cl,cr);
    }
    if(cr>mid)
    {
        res+=qry(tr[p].r_son,mid+1,r,cl,cr);
    }
    return res;
}

没有创建其实就是没有增加过，所以值必然是 0。

主函数略。

0x13. 总结：动态开点太好用了你们知道吗

其实这篇帖子其实还是为了巩固一下新知识，不过还是写一下总结吧。

  • 用编号来存储，创建节点时就 ++；
  • 左右节点不用 2x 和 2x+1，而是两个变量（伪指针）；

大概就这样，其实与平常的线段树比也没改什么地方。

0x14. 后记

后面打算下次写一下搜索树和平衡树的笔记。