线段树

原理

线段树，就是把一段区间，不断二分，分为一颗二叉树，去维护区间信息。

算法结构

一个完整的线段树代码中，通常由六个部分组成

这里展示以一个简单的整数问题2为例

struct Node

节点部分，其中维护的是，关于线段树所有需要用到的信息。

这里需要着重说一下的是，一般我们的Node会开到四倍区间大小

左右端点 ,题目中会用到的信息 及懒标记

例子(或者叫板子？emm)

struct Node
{
    int l,r;
    LL sum; //(区间需要维护的值)
    LL add;//（懒标记，可以有多个）
}tr[N*4];

pushup

这个函数的作用是将子节点产生的变化，传递到父节点。

所以一般在的位置都是在已经递归结束的函数后，因为此时子节点的变化已经结束，可以去更新父节点了

只有这个地方会使用，一定记住,因为如果每次发生变化，就立即进行回溯改变，就破坏了懒标记的作用。

懒标记便是为了延迟更新，当要改变的区间完全包括某个树中区间时，直接将这个区间的懒标记+d即可，不用进行pushup操作，等到，查询时需要这个区间时，我们再进行pushdown操作，将影响传递到它的子节点，在一步步回溯回来时，再利用pushup去更新，父节点！！！

很关键，易错点。

防止错误，首先需要死记住，pushup和pushdown的位置。然后再进行理解。

void pushup(int u)
{
    tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
}

pushdown

这个函数的作用是将父节点产生的变化，传递到子节点

但这里一定要提及一下，它所在的位置是需要进行分裂时，之前。

例如：查询时，遇到的树中区间与我所查的区间是有一部分相交的情况，此时就要分裂了，因此要pushdown

另外，再进行区间改变时，当所要改变的区间与树中区间是有一部分相交时，此时也要分裂，pushdown一下。

void pushdown(int u)
{
    Node &root = tr[u],&left = tr[u<<1],&right = tr[u<<1|1];
    if(root.add){
        left.add+=root.add,left.sum+=(LL)(left.r-left.l+1)*root.add;
        right.add+=root.add,right.sum+=(LL)(right.r-right.l+1)*root.add;
        root.add=0;//传递到到下边后，要清空。
    }
}

build

build函数的操作，比较简单，就是不断二分，向下递归，递归到区间内只剩下一个数字了，则停止进行赋值，然后回溯。

这里可以注意看pushup的位置

void build(int u,int l,int r)
{
    if(l==r) tr[u]={l,r,w[r],0};
    else
    {
        tr[u]={l,r};//这一步比较容易忘记
        int mid = l + r >> 1;
        build(u<<1,l,mid),build(u<<1|1,mid+1,r);
        pushup(u);
	}
}

modify

modify函数，在改变时，分为单点修改和区间修改。单点修改比较简单，只要查到需要改的数字下标，改了之后pushup即可，这里不说了。这里着重提一下区间修改。

要分为三种情况

• 所要改变区间包含树中的区间，则直接将需要加或者减的数，直接更改到该树中区间的懒标记上，同时改变需要改变的值

• 所要改变区间与树中区间交叉一部分，mid=tr[u].r+tr[u].l>>1，则判断若要改变区间l是否比mid小,若是，则递归到左边界，再判断所改变区间的r是否>mid,若是，则递归到有边界。

• 第三种情况不可能出现，但是还是提一下。所要改变区间被，树中区间所包含。

其中第一种情况，因为区间没有分裂情况，所以不用pushdown。而第二种，有分裂情况出现，则需要pushdown一下，再进行接下来的操作。

void modify(int u,int l,int r,int d)
{
    if(tr[u].l>=l&&tr[u].r<=r) 
    {
        tr[u].sum+=(LL)(tr[u].r-tr[u].l+1)*d;
        tr[u].add+=d;
	}
    else
    {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if(l<=mid) modify(u<<1,l,r,d);
        if(r>mid) modify(u<<1|1,l,r,d);
        pushup(u);
	}
}

query

query函数，跟modify函数几乎相同，只要注意分裂之前要用pushdown即可

LL query(int u,int l,int r)
{
    if(tr[u].l>=l&&tr[u].r<=r) return tr[u].sum;
    
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    LL sum = 0;
    if(l<=mid) sum += query(u<<1,l,r);
    if(r>mid) sum += query(u<<1|1,l,r);
    return sum;
}

以上就是，以一道题目为例，说明了一下线段树的结构

能解决的问题

• 区间修改
• 区间查询
• 单点修改
• 单点查询

一些例题

区间最大公约数

比较经典，如何去维护一个区间的最大公约数，利用差分数组。因为

维护序列

懒标记的复杂运用，同时维护两个懒标记，使区间可以进行乘和加。

我们在维护pushdown时，利用的是先乘后加的操作

举个例子，例如，新加进来的add',mul'

则pushdown中更新，左右节点的eval函数

void eval(Node &u,LL add,LL mul)
{
    u.sum=(u.sum*mul+(u.r-u.l+1)*add)%p;
    u.mul=mul*u.mul%p;
    u.add=(u.add*mul+add)%p;
}

你能回答这些问题嘛

展示了，可能我们需要维护许多的信息。

其实还有一个，扫描线，但是它有些特殊，我们放到别的地方单独记忆。