lls的数据结构课：线段树

junxis · 2022-02-10 19:21:07 · 个人记录

1.引入

现在 lls抛给你一个问题：输入一个数列 需支持在线询问区间l - r的和。

显然这题可以用可爱的前缀和O(1)解决。

那lls加强题目：还要支持对第x个数加上一个数K，怎么办？

拜拜了您内我不做了

我们考虑对前缀和数组修改 但这样的复杂度将变成O(n)。 这种辣鸡复杂度能过的题就不叫数据结构题了

这时，我们就请出了它 -- 线段树

2.介绍

线段树是一种非常强大的树形数据结构，它可以维护各种乱七八糟的区间信息，它可以在O(logn)的时间复杂度内完成对一个线性序列的大部分操作，但前提是维护信息必须满足结合律。 线段树的每个节点都要保存一个区间的信息。

3.无区间修改的线段树实现

3.0 例题

我是例题

3.1 存储与建树

3.1.1 分析

令当前节点编号为p 保存区间的左右边界分别为l,r 而对于一颗二叉树 我们还要知道它的左孩子和右孩子，我们采取堆式存储法： 则左节点为px2 右节点为px2+1（我一般提前define掉）

我们想知道一个区间的信息 可以利用分治思想 把它变成左右两部份 令mid=(l+r)/2
则左节点为保存区间的左右边界为(l,mid)

右节点为保存区间的左右边界为(mid+1,r)

那么对于信息的向上维护（从左右孩子推出父节点信息）也变得非常简单 只需对题目具体分析 然后利用结合律按题目意思模拟即可

这里再放张图照顾一下对式子过敏的同学：

3.1.2 代码实现

那么我们用结构体存储每个节点，再利用分治递归建树即可，不过结构体的数组一定要开四倍序列空间。

是不是很简单呢？ 上代码！

#define lc p<<1//左孩子 
#define rc p<<1|1//右孩子 
struct Point/*线段树节点 */{
    int l,r,v;
}tree[N<<2];
void pushUp(int p)//向上维护
{
    tree[p].v=tree[lc].v+tree[rc].v;//本题要求区间和   
} 
void build(int p,int l,int r)//建树
{
    tree[p].l=l;tree[p].r=r;
    if(l==r)//若递归到叶节点 那么它的区间和退化成了原数组中的一个元素  
    {
        tree[p].v=a[l];
        return ; 
    }
    int mid=(l+r)>>1;
    build(lc,l,mid);
    build(rc,mid+1,r);
    pushUp(p);
    //这几行参考前面的分析 
} 

现在你已经掌握了线段树的存储与建树！Orz

3.2线段树的单点修改与区间查询

3.2.1 单点修改

3.2.1.1 分析

对于单点修改，我们只需要在线段树上不断查找，直到找到一个叶节点保存的点恰等于需要修改的点，将它直接修改，并回溯，在回溯时向上维护即可。

3.2.1.2 代码

void modify(int p,int x,int k)//单点修改，当前节点编号为p ，需要修改的点是序列中的第x个，需要将它加上k
{
    if(tree[p].l==tree[p].r&&tree[p].l==x)
    {
        tree[p].v+=k;
        return ;    
    }//参考分析 
    if(x<=tree[lc].r/*也就是x<=mid*/) modify(lc,l,r);
    if(x>tree[lc].r/*也就是x>mid*/) modify(rc,l,r);
    //上面两行决定了要修改的数在当前节点的左子树还是右子树
    //这两个if建议背下来,在草稿纸上模拟一下就知道了
    pushUp(p);//修改完要记得向上维护 
} 

3.2.2 区间查询

3.2.2.1 分析

对于区间查询 我们只需在线段树上不断查找，若当前节点保存的区间包含在需查询的区间里 直接返回这个区间的值，否则就判断所查询区间是否与左子树区间有交集还是与右子树区间有交集（也有可能被同时包含了一部分）递归求有交集的几个部分的答案，将答案合并再返回即可。

3.2.2.2 代码

int query(int p,int l,int r)//区间查询 当前节点编号为p 要查询的区间为[l,r] 
{
    if(tree[p].l>=l&&r>=tree[p].r) return tree[p].v;
    int tmp=0;
    if(l<=tree[lc].r/*即l<=mid*/) tmp+=query(lc,l,r);
    if(r>tree[lc].r/*即r>mid*/)  tmp+=query(rc,l,r); 
    return tmp;
}//参考分析理解代码 

到这里，你已经实现了一颗难度较低的无区间操作线段树，赶紧拿它去切题吧！！

不过这只是线段树最简单的一部分，与树状数组的功能相当，接下来，更强大的，无法被树状数组取代的线段树要来了！

4.带区间操作的线段树

4.0 前言

这个部分的难度将有一个阶梯式上升，请反复阅读，保证对其理解透彻。 例题：我是例题

4.1 懒标记

4.1.1 引入

看到例题，它有一个操作令我们无从下手：将区间l - r加上k

于是你想：那么能不能用一个标记代替一个区间呢？

能！

不过我们要对它的定义稍作修改---

4.1.2 实现

每个节点的懒标记tag 表示这个节点所代表的区间还剩多少没有加。

这样一来 我们就只要修改tag 并在要对下一个区间做操作之前将下一个区间的值用tag修改并将它的tag也修改即可

这样，即不会影响正确性，也不会影响时间复杂度

所以我们要写的是三个操作：

PushDown : 下传标记

Modify:区间修改

Query:区间查询

（由于文字还是比较抽象，可参考代码理解）

代码环节！

void pushDown(int p)
{   
    tree[lc].v+=(tree[lc].r-tree[lc].l+1)*tree[p].tag;
    tree[rc].v+=(tree[rc].r-tree[rc].l+1)*tree[p].tag;
    tree[lc].tag+=tree[p].tag;
    tree[rc].tag+=tree[p].tag;
    //自行根据懒标记定义理解 
    tree[p].tag=0;
 } 
void modify(int p,int l,int r,int k)//区间加法 
{
    if(tree[p].l>=l&&tree[p].r<=r)
    {
        tree[p].v+=k*(tree[p].r-tree[p].l+1);
        tree[p].tag+=k;
        return ; 
    }//若被修改区间完全包含，则直接修改 
    pushDown(p);//在递归之前下传下一层标记 
    if(l<=tree[lc].r) modify(lc,l,r,k);
    if(r>tree) modify(rc,l,r,k);
    pushUp(p);//别忘了向上维护 
} 
int query(int p,int l,int r)//区间查询 当前节点编号为p 要查询的区间为[l,r] 
{
    if(tree[p].l>=l&&r>=tree[p].r) return tree[p].v;
    int tmp=0;
    pushDown(p);//在递归之前下传下一层标记 
    if(l<=tree[lc].r/*即l<=mid*/) tmp+=query(lc,l,r);
    if(r>tree[lc].r/*即r>mid*/)  tmp+=query(rc,l,r); 
    return tmp;
}//参考分析理解代码 

tips:有些题中要维护多个区间信息，这时我们便要 注:spoon也是一觉醒来才对懒标记恍然大悟的，只需多思考，就能理解它

到这里：你掌握了基本的线段树功能，在做一些题时你也能灵活运用线段树，但还有许多更高深莫测的线段树算法等着你学习……

5.线段树的经典应用 - 逆序对计数

5.0 前言

题目传送门

在我们刚学 OI 时就遇见过这个问题，它的时间复杂度要求是O(n \log n) ，那时，我们利用归并排序的特性轻易地解决了了它，但由于归并排序的应用范围过于狭隘，现在，利用线段树来解决它反而成了对于每个看到这里的 OIer 最自然的想法。

5.1 分析

这个思路乍一看很难，但只要认真思考，对上文的理解深刻，还是能够自己想出来的。

我们先思考逆序对的形成缘由，有一个比你大的数比你先出现，那么你和他构成了一个逆序对，对于每个数，我们只要求出当前已经出现的数里有几个比他大即可。

反复阅读这句话，你想到了什么？

桶。（意识流做题）

桶这个东西可以将大小关系转化成位置关系，这样一来，值为 val 的元素出现时，他对答案的贡献A：

其中 Lim 表示给定的数组元素大小上界，t 为桶。

5.2 实现

看到这里有个区间求和。

线段树。

这时你说：“这道题 a_i 最多有 10^9 ，内存直接炸飞啊”

看到重点部分的这个字眼“比我大”，想到了什么？

离散化。

而对于每个数的出现，只需要在桶中对应点加 1 即可。

综上，我们只需要写一颗支持单点修改和区间查询的线段树即可。

你要写树状数组我也不拦着你

代码：

#include<bits/stdc++.h>
const int N=5e5+5;
#define lc p<<1
#define rc p<<1|1
#define ll long long 
ll ans;
struct disc{
    int val,id;
    bool operator <(const disc rhs)const
    {
        return this->val<rhs.val;
    }
}a[N];//离散化 
int n,b[N];
struct point{
    int l,r;
    ll v;
}tree[N<<2];
void pushUp(int p)
{
    tree[p].v=tree[lc].v+tree[rc].v;
}
void build(int p,int l,int r)
{
    tree[p].l=l,tree[p].r=r,tree[p].v=0;
    if(l==r)return ;//最开始没有数出现，建的是空树。 
    int mid=(l+r)>>1;
    build(lc,l,mid);
    build(rc,mid+1,r);
    pushUp(p); 
}
void modify(int p,int k)
{
    if(tree[p].l==k&&tree[p].r==k)
    {
        ++tree[p].v;
        return ;
    }
    if(tree[lc].r>=k) modify(lc,k);
    if(tree[rc].l<=k) modify(rc,k);
    pushUp(p);
}//简单的单点修改 
ll query(int p,int l,int r) 
{
    if(tree[p].l>r)return 0;
    if(tree[p].r<l)return 0;
    if(tree[p].l>=l&&tree[p].r<=r)return tree[p].v;
    ll Tmp=0;
    if(l<=tree[lc].r)Tmp+=query(lc,l,r); 
    if(r>tree[lc].r)Tmp+=query(rc,l,r);
    return Tmp;
}//简单的区间查询 
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i].val);
        a[i].id=i;
    }
    std::sort(a+1,a+n+1);
    int rank=0;a[0].val=1e9+1;
    for(int i=1;i<=n;i++)b[a[i].id]=(rank+=(a[i].val!=a[i-1].val));//离散化 当然你也可以用STL三连 
    build(1,1,n);
    for(int i=1;i<=n;i++)
    {
        modify(1,b[i]);
        ans+=query(1,b[i]+1,rank);  
    }//参考分析食用 
    printf("%lld",ans);
    return 0;
}

5.3 后记

当然，这种用线段树维护桶的想法也叫权值线段树，我一般叫它树桶，它是一种非常灵活的思想，因为他可以做到删点和加点，你可以用它 AC 普通平衡树。