线段树入门 | hkr04‘s blogs

这是百度百科上的图，线段树定义可以看这里->定义戳我

任何一个区间都能被分成两个小区间，从而能够把对于大区间的查询转换为对几个小区间和小小区间和小小小区间……的查询。
这是我对线段树的朴素理解，实际上就是一种分治的思想。

从图上也可以明显地看出任意一个长度大于1的区间都由两个小的子区间组成，子区间再往下分，直到区间内只有一个元素无法再分。因此，对于每一个长度大于1的区间[l,r]，有mid=(l+r)/2,
分为左子区间[l,mid]，右子区间[mid+1,r]；且满足二叉树的性质。

当我们在考虑用线段树解题时，要思考：

1. 是否能分成多个区间；
2. 区间是否具有可加性；
3. 叶子节点存储什么信息。

有一个小地方需要注意：
通常线段树底层都不会满，但是它就是要多用那一层
我们假设线段树底层是满的且叶子数为n（空间利用最优情况）（易证最后一层叶子数等于原数组元素个数），那么显而易见的，叶子总数为
$n+n/2+n/2/2…+2+1=2n-1$
凡事要往坏的地方多去想想，我们的空间不会运用得那么彻底，那我们还要再加一层防止溢出，这一层的叶子数就为 $2n$ 。
加上预留的一层空间，我们给线段树的空间就为 $4n$ （舍去了影响较小的-1），这样就能防止因为数组不够大而re了( ´▽｀)

把基础的线段树掰开来理解，主要有三个部分：

构建
修改
查询

注：以下代码以基础的区间修改和查询区间和的线段树为例

模板：p3372线段树1

1. 构建：

我采用结构体来存储每个区间的信息（这里我用数组，也有指针的写法，看个人喜好）

typedef long long ll;
int a[maxn];
struct SegmentTree
{
    int l,r;//l、r分别代表这一区间的左右边界
    ll dat,add;//dat为存储的信息，add是使用的lazytag（可以理解为修改标记，等下修改的时候要用到，现在可以先不管它）
    SegmentTree(){add=0;}//先默认不修改
}t[maxn*4];//maxn通常在函数开头定义，方便修改大小。maxn*4是防止数组越界

void build(int p, int l, int r)//初始化函数
{
    //p是当前构造的线段树数组下标，l、r分别为当前构造的点代表的区间的左右边界
    t[p].l=l;t[p].r=r;//先把边界定好
    if (l==r){t[p].dat=a[l];return;}
    //如果l==r说明不能再分，把原数组上的信息存一下，返回
    int mid=(l+r)>>1;//mid=(l+r)/2
    build(p*2, l, mid);//构建左子区间
    build(p*2+1, mid+1, r);//构建右子区间
    t[p].dat=t[p*2].dat+t[p*2+1].dat;
    //这是一个求区间和的线段树，所以该区间所存的信息等于两个子区间所存信息之和
}

当a数组的信息完全输入以后，build（1，1，n）即可
（n为数组中元素个数）

2. 修改：

前面出现了个神奇的lazy tag，它的作用是什么呢？

跟你想的一样，就是用来偷懒的

首先我们知道，修改带来的影响是对于好几个区间的。如果我们耿直地每一次修改都敬职敬责地改到最小的区间，但是很多修改根本不会被询问到，无疑是吃力不讨好的。当修改特别多的时候就可能超时。这个时候我们就得想办法~~偷工减料~~优化了。
要是你修改了却不用，和不修改是没有区别的。所以我们先把工作攒起来，当查询的时候再去执行~~（本质就是偷工减料嘛（逃~~
lazy tag的不严谨定义~~（因为是我自己写的）~~：

当lazy tag不为0时，说明当前区间已经被这个影响所作用，这个区间的所有子区间全都攒着工作没有修改

代码

void spread(int p)//先看下面那个函数
{
    if (t[p].add)//如果当前位置为p的点的下一层要改
    {
        t[p*2].dat+=t[p].add*(t[p*2].r-t[p*2].l+1);
        //修改左子区间（r-l+1得到区间内元素个数，我每一个都要加上从上一层传过来的add的值，那么对于这个区间的影响就是加上【元素个数*add】
        //注意是+=
        t[p*2+1].dat+=t[p].add*(t[p*2+1].r-t[p*2+1].l+1);//右子区间同理
        t[p*2].add+=t[p].add;
        //把影响给加上，同样要注意+=
        t[p*2+1].add+=t[p].add;
        t[p].add=0;//已经把工作传给子区间了，这一层的信息已经是最新的了，消除lazy tag
    }
}
void change(int p, int v, int l, int r)
{
//p是需要修改的位置，v是要加上的值，l、r为修改区间边界
    if (l<=t[p].l&&t[p].r<=r)//如果当前的点区间包含于[l,r]，执行修改并打上lazy tag
    {
        t[p].add+=(ll)v;
        t[p].dat+=(ll)v*(t[p].r-t[p].l+1);
        return;
    }
    spread(p);//将修改向下传，见上一个函数
    int mid=(t[p].l+t[p].r)>>1;
    if (l<=mid)change(p*2, v, l, r);//如果l<=mid，说明在左子区间中有地方需要更改
    if (r>mid)change(p*2+1, v, l, r);
    //右子区间同理
    t[p].dat=t[p*2].dat+t[p*2+1].dat;
    //更新当前信息
}

3. 查询

直接上代码吧

ll ask(int p, int l, int r)
{
    if (l<=t[p].l&&t[p].r<=r)//如果当前区间包含于需要查询的区间，直接征用该区间的信息，返回
        return t[p].dat;
    spread(p);//先看看有没有积压的工作要在查询前做了
    int mid=(t[p].l+t[p].r)>>1;
    ll val=0;
    if (l<=mid)val+=ask(p*2, l, r);
    //如果l<=mid，说明左子区间有地方的信息需要用到
    if (r>mid)val+=ask(p*2+1, l, r);//同理
    //因为两边的子区间中都有可能有某个子区间有信息需要征用，所以是两个if
    return val;
}

线段树大概就是这样……

因为个人水平有限，难免有疏漏，欢迎批评指正(=ﾟωﾟ)ﾉ