【算法】线段树

Tobiichi_Origami · 2023-06-01 11:44:30 · 个人记录

线段树是一种支持区间操作的数据结构，用类似于一棵树的方式进行存储，本文将会讲述其基本操作和衍生问题以及算法。

一. 基础线段树

线段树用来维护区间信息，一般有四个基础操作，分别是单点修改，单调查询，区间修改，区间查询。

建树

建树操作和二叉树的建树方法十分相近，每次递归分治建树，将区间一分为二，如果到达叶子区间，则直接将所要维护的信息赋值。

每次赋值后需要进行 \text{pushup} 操作，目的是将所维护的信息从两个子区间传入父区间。以区间和为例 \text{pushup} 操作进行的就是父区间的和等于两个子区间的和。

void pushup(int u)
{
    int tmp=t[u<<1].sum+t[u<<1|1].sum;//u<<1和u<<1|1皆为左右儿子编号
    t[u].sum=tmp;
}
void build(int u,int l,int r)//u表示当前区间编号
{
    t[u].l=l;t[u].r=r;
    if(l==r)
    {
        t[u].sum=w[l];//w[l]为输入区间下标为l的值
        return ;
    }
    int mid=(l+r)>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    pushup(u);
}

单点修改

首先，我们先要明确修改的位置下标以及修改的数值。

和建树的方法相差不大，每次分治查找位置再左区间还是右区间，依次递归进行处理。若找到了位置，则将要修改的信息直接修改。因为信息已经更新，所以还要进行 \text{pushup} 操作。

void modify(int u,int pos,int val)
{
    if(t[u].l==pos&&t[u].r==pos)
    {
        t[u].sum=val;
        return ;
    }
    int mid=(t[u].l+t[u].r)>>1;
    if(pos<=mid) modify(u<<1,pos,val);
    else modify(u<<1|1,pos,val);
    pushup(u);
    return ;
}

单点查询

单点查询和单点修改几乎相同。

首先，需要明确查询的位置。再每次分治查找位置再左区间还是右区间，依次递归进行处理，找到位置后直接返回所要查询的数值。

int query(int u,int pos)
{
    if(t[u].l==pos&&t[u].r==pos)
        return t[u].sum;
    int mid=(t[u].l+t[u].r)>>1,res;
    if(pos<=mid) res=query(u<<1,pos,val);
    else res=query(u<<1|1,pos,val);
    return res;
}

区间查询

首先，区间查询需要明确所要查询的区间范围。

再每次分治查找，如果中点大于等于要查询的区间范围的左端点，就说明左区间在所要查询的区间范围内；果中点小于要查询的区间范围的右端点，就说明右区间在所要查询的区间范围内。

之后如果当前递归到的区间再所要查询的区间范围之内，直接返回当前区间所维护的信息，并将其计入答案。

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

区间修改

我们先考虑，如果每个点都要进行一次单点修改，时间复杂度为 O(n\log n)，显然会寄。

我们会引进一个新的概念，懒标记。

我们考虑，更新一定是为了保证答案的准确，所以如果不查询的这个区间，这个区间就可以不更新，换句话说，可以先将之前所要维护的值计入懒标记当中，当这个区间被查询时，将这个区间所维护的信息更新。

区间修改需要明确所修改的区间范围和要修改的值。

和区间查询一样，分治查找并且更新，因为之后还要更新儿子，所以我们要将懒标记传给儿子区间，自己清零，即为 \text{pushdown} 操作。如果当前区间在所要查找的区间范围内，直接在此区间内更新。

因为区间修改修改了维护的信息，所以需要进行 \text{pushup} 操作。

void pushdown(int u)
{
    if(t[u].add)
    {
        t[u<<1].add+=t[u].add;
        t[u<<1].sum+=(t[u<<1].r-t[u<<1].l+1)*t[u].add;
        t[u<<1|1].add+=t[u].add;
        t[u<<1|1].sum+=(t[u<<1|1].r-t[u<<1|1].l+1)*t[u].add;
        t[u].add=0;
    }
    return ;
}
void modify(int u,int l,int r,int val)
{
    if(t[u].l>=l&&t[u].r<=r)
    {
        t[u].sum+=(t[u].r-t[u].l+1)*val;
        t[u].add+=val;
        return ;
    }
    int mid=(t[u].l+t[u].r)>>1;
    if(l<=mid) modify(u<<1,l,r,val);
    if(mid<r) modfiy(u<<1|1,l,r,val);
    return ;
}

题型

1.线段树优化

在进行某些区间操作时，无法用线段树来进行维护，这时我们就可以每个点进行单调修改，并根据所进行的区间操作特性进行优化。

以花神游历各国为例

题意

给你两个操作，一个是将整个区间开方，另一个是查询一个区间的区间和，用线段树维护。

思路

首先，区间开方用线段树非常难维护（维护不了？），所以我们考虑一些优化。

因为 \text{c++} 是自动下取整，所以在经历了若干遍开方之后，最终的答案必定会为 1，然而 1 开方还是为 1，所以之后便都在进行无效操作。

考虑维护一个区间最大值，因为如果区间最大值已经为 1 了，那么其他的元素也一定为 1。

那么如果已经为 1 了，就直接退出区间修改，其他与区间修改一样。

区间查询照常进行。

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct tree{
    int l,r;
    int sum=0;
    int max=-114514; 
}t[1000001];
int a[100001];
int n,m;
void pushup(int u)
{
    t[u].sum=t[u<<1].sum+t[u<<1|1].sum;
    t[u].max=max(t[u<<1].max,t[u<<1|1].max);
}
void build(int u,int l,int r)
{
    t[u].l=l;t[u].r=r;
    if(l==r)
    {
        t[u].sum=t[u].max=a[l];
        return ;
    }
    int mid=(l+r)>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    pushup(u);
}
void modify(int u,int l,int r)
{
    if(t[u].l==t[u].r)
    {
        t[u].sum=sqrt(t[u].sum);
        t[u].max=sqrt(t[u].max);
        return ;
    }
    int mid=(t[u].l+t[u].r)>>1;
    if(mid>=l&&t[u<<1].max!=1)
        modify(u<<1,l,r);
    if(mid<r&&t[u<<1|1].max!=1)
        modify(u<<1|1,l,r);
    pushup(u);
    return ;
}
int query(int u,int l,int r)
{
    if(t[u].l>=l&&t[u].r<=r) 
        return t[u].sum;
    int mid=(t[u].l+t[u].r)>>1,res=0;
    if(mid>=l) res+=query(u<<1,l,r);
    if(mid<r) res+=query(u<<1|1,l,r);
    return res;
}
signed main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);
    scanf("%lld",&m);
    while(m--)
    {
        int op;
        scanf("%lld",&op);
        if(!op)
        {
            int x,y;
            scanf("%lld %lld",&x,&y);
            if(x>y) swap(x,y);
            modify(1,x,y);
        }
        else
        {
            int x,y;
            scanf("%lld %lld",&x,&y);
            if(x>y) swap(x,y);
            printf("%lld\n",query(1,x,y));
        }
    }
}

总结

此类题型需多加注意区间修改的特性，根据这个特性进行优化。

习题

The Child and Sequence

2.标记永久化

标记永久化是一个线段树优化的技巧，此技巧可以省略线段树中的 \text{pushdown} 操作。

以区间和为例，考虑每次修改区间时，将其子树所被影响到的区间打上标记，在更新时，将所有子树中的标记累加，这样也就省去了朴素线段树中下传标记的操作。

二. 权值线段树

权值线段树是线段树的一种衍生算法，其基本存储结构和线段树基本相同。

如图，每个结点存储的分别为下方元素的出现次数。

1.建树

和朴素线段树的建树方式相同，只是其维护的信息与朴素线段树不同。

void pushup(int u)
{
    int tmp=t[u<<1].sum+t[u<<1|1].sum;
    t[u].sum=tmp;
}
void build(int u,int l,int r)
{
    t[u].l=l;t[u].r=r;
    if(l==r)
    {
        t[u].sum=w[l];//w[l]为l出现的次数
        return ;
    }
    int mid=(l+r)>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    pushup(u);
}

2.单点修改

单点修改就和朴素线段树一模一样了，因为都是修改一个数，本质上没有区别。

void modify(int u,int pos,int val)
{
    if(t[u].l==pos&&t[u].r==pos)
    {
        t[u].pos+=val;
        return ;
    }   
    int mid=(t[u].l+t[u].r)>>1;
    if(mid>=l) modify(u<<1,pos,val);
    if(mid<r) modify(u<<1|1,pos,val);
    pushup(u);
}

3.单点查询

单点查询查询的是 \text{val} 出现的次数。

int query(int u,int pos)
{
    if(t[u].l==pos&&t[u].r==pos)
        return t[u].sum;
    int mid=(t[u].l+t[u].r)>>1,res;
    if(pos<=mid) res=query(u<<1,pos,val);
    else res=query(u<<1|1,pos,val);
    return res;
}

4.查询 k 大值

首先，我们要明确，此操作只针对于整个权值线段树，不适用于某个独立的子区间。

我们考虑，我们存入的左右端点皆为某个具体的数字，且升序排序，那么我们便可以分治求解答案。

如果 k 小于区间中点，那么也就说明结果为左区间第 k 大数。否则，也就说明结果为右区间第 k-mid 大数。

int query(int u,int k)
{
    if(t[u].l==k&&t[u].r==k)
        return t[u].l;
    int mid=(t[u].l+t[u].r)>>1;
    if(k<mid) return query(u<<1,k);
    else return query(u<<1|1,k-mid);
}

习题

中位数 直接用权值线段树加离散化

送花 权值线段树模板题

三. 动态开点线段树

因为朴素的线段树需要开四倍空间，很容易空间超限，那么我们此时便可以运用动态开点线段树。

动态开点线段树的主要思想即为如果用到了便开一个点，所以动态开点线段树也没有建树的操作。每次需要一个点便将节点编号增加，然后插入数值。

单点修改

int pushup(int u)
{
    int tmp=t[t[u].l].sum+t[t[u].r].sum;
    t[u].sum=tmp;
}
void modify(int &u,int l,int r,int pos,int val)
{
    if(!u) u=++cnt;
    if(l==pos&&r==pos) 
    {
        t[u].sum=x;
        return ;
    }
    int mid=(l+r)>>1;
    if(pos<=mid) modify(t[u].l,l,mid,pos,val);
    else modify(t[u].r,mid+1,r,pos,val);
    pushup(u);
}

单点查询

int query(int u,int l,int r,int pos)
{
    if(!u) return 0;
    if(l==pos&&r==pos)
        return t[u].sum;
    int mid=(l+r)>>1,res=0;
    if(pos<=mid) res=query(t[u].l,l,mid,pos);
    else res=query(t[u].r,mid+1,r,pos);
    return res;
}

区间查询

int query(int u,int l,int r int L,int R)
{
    if(!u) return 0;
    if(l>=L&&r<=R)
        return t[u].sum;
    int mid=(l+r)>>1,res=0;
    if(mid>=L) res+=query(t[u].l,l,mid,L,R);
    if(mid<R) res+=query(t[u].r,mid+1,r,L,R);
    return res;
}

区间修改

void pushdown(int u,int l,int r)
{
    if(t[u].add)
    {
        if(!t[u].l) t[u].l=++cnt;
        if(!t[u].r) t[u].r=++cnt;
        int mid=(l+r)>>1;
        t[t[u].l].add+=t[u].add;
        t[t[u].l].sum+=(mid-l+1)*t[u].add;
        t[t[u].r].add+=t[u].add;
        t[t[u].r].sum+=(r-mid)*t[u].add;
        t[u].add=0;
    }
}
void modify(int &u,int l,int r,int L,int R,int val)
{
    if(!u) u=++cnt;
    if(l>=L&&r<=R)
    {
        t[u].add+=val;
        t[u].sum+=(r-l+1)*val;
        return ;
    }
    pushdown(u,l,r);
    int mid=(l+r)>>1;
    if(mid>=L) modify(t[u].l,l,mid,L,R,val);
    if(mid<R) modify(t[u],r,mid+1,r,L,R,val);
    pushup(u);
}

总结

动态开点线段树准确来说是一种优化线段树空间的技巧，其作用也可以通过离散化来实现。

习题

[SDOI2014]旅行 建 n 棵线段树，用动态开点线段树与树剖进行维护