线段树初步

线段树基础

线段树,是利用一个区间建立一个完全二叉树,来快速实现区间修改、查询操作。

例如,要求对序列 A{1,3,4,2,5,3,7,8} 进行如下两种操作:

  • add(l,r,v): 把 [l,r] 的元素都增加 v
  • sum(l,r): 求 [l,r] 的元素和

以此为例,从最基础的构建讲起。

线段树结构

对于闭区间 , 若其对应的树的结点为 ,则有如下定义:

  • 时,root 没有子结点
  • 否则,令 ,则其左子区间为 , 对应结点 ,右子区间为 , 对应结点

如此递归定义,可构建一个线段树。在进行查询与修改的时候,将区间一分为二递归处理。

树构建

针对初始数据,我们需要对其进行线段树构建。直接递归构建即可,伪代码如下:

/*
变量声明
l,r,rt: 分别代表区间的左端,右端,以及其对应结点的编号
sum[]: 线段树中存储区间查询值的数组,这里是查询区间和
a[]: 初始数据
*/
int tree_build(int l=1,int r=n,int rt=1){
    if(l==r)return sum[rt]=a[l];// 单个结点
    int mid=(l+r)>>1;
    tree_build(l,mid,rt<<1);// 左子区间
    tree_build(mid+1,r,rt<<1|1);// 右子区间
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];// 合并
}

区间查询

有了前面的树构建,区间查询的代码也类似,不过需要注意的是,区间查询要考虑是否有交集,如果没有交集就应停止递归。另一个比较难理解的地方是,该函数的递归终止条件是返回一个被包含在 [L,R] 的当前区间 [l,r] 的 sum 值。不过在看完伪代码以后,这个问题就比较好理解了。

/*
变量声明
L,R: 目标区间 [L,R] , 即要查询的区间
l,r,root: 当前区间 [l,r] 及其对应结点的编号
*/
int Sum(int L,int R,int l=1,int r=n,int rt=1){
    if(r<L||R<l)return 0;// 不包含
    if(L<=l&&r<=R)return sum[rt];// 当前区间在目标区间内
    int mid=(l+r)>>1;
    return Sum(L,R,l,mid,rt<<1)+Sum(L,R,mid+1,r,rt<<1|1);
}

如果还没有理解它的运作方式的话,以序列 A 为例,调用 SUM(3,7,1,8,1),即查询 [3,7] 的元素和,当前区间为 1,8,运行情况如下:
线段树.gif

SUM(3,7,1,8,1)
SUM(3,7,1,4,2)
SUM(3,7,3,4,5) 发现包含,返回 sum[5]
SUM(3,7,5,8,3)
SUM(3,7,5,6,6) 发现包含,返回 sum[6]
SUM(3,7,7,8,7)
SUM(3,7,7,7,14) 发现包含,返回 sum[14]

区间修改

与 SUM 类似,不过在遇到包含的情况后不是返回 sum,而是调用另一个函数来递归完成修改。

/*
变量声明:
v: 要加上的值
*/
int tree_add(int l=1,int r=n,int rt=1,int v){// 将整个 [l,r] 全部加 v
    if(l==r)return sum[rt]+=v;
    int mid=(l+r)>>1;
    tree_add(l,mid,rt<<1,v);
    tree_add(mid+1,r,rt<<1|1,v);
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
int add(int L,int R,int l=1,int r=n,int rt=1,int v){// 将目标区间加 v
    if(r<L||R<l)return 0;
    if(L<=l&&r<=R)return tree_add(l,r,rt,v);
    int mid=(l+r)>>1;
    add(L,R,l,mid,rt<<1,v);
    add(L,R,mid+1,r,rt<<1|1,v);
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];// 加完之后向上更新
}

线段树与树状数组

相对而言,树状数组的实现要简单于线段树,但线段树处理的问题更多更全面。

相比而言,树状数组适合处理区间查询,点修改区间修改,点查询(差分)的问题,而线段树则能解决所有区间的修改查询问题。

线段树进阶

在进行区间修改时,上述代码实际上是到达两每一个点的,复杂度达到了 .

我们可以将这些修改操作攒起来,到了合适的时候一起修改。

懒惰标记 -Lazytag

对于线段树上的每一个结点,引入一个标记,记录这个结点对应的区间需要加但还未加的值。

等到这个结点的 sum 需要被查询的时候,再加上去。

懒惰标记的意义

首先搞清楚懒惰标记的意义

它不对所在结点生效,而是对该结点的子结点生效

也就是说,懒惰标记表达的是该结点的子结点所需要加的值,而该结点本身的 sum 已经被懒惰标记更新过,所以不属于标记的范畴。

说得程序一点,我们在更新 Lazytag 的时候,对该结点的值也会更新。至于为什么这样做,是因为在递归到单个元素的结点后,其本身没有子结点,为防止访问无效内存,所以这样设计。

懒惰标记的更新

线段树的结点是从下往上更新的,然而 Lazytag 是从上往下更新。

将原线段树的更新操作定义为 pushup() 函数:

void pushup(ll rt){// 将下层数据向上更新
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}

将 lazytag 的更新定义为 pushdown() 函数:

/*
变量声明:
s:保存线段树的和
add:lazytag 标记
*/
void push_down(int l,int r,int rt){// 将当期标记下传
    int mid=(l+r)>>1;
    sum[rt<<1]+=(mid-l+1)*add[rt],sum[rt<<1|1]+=(r-mid)*add[rt];// 更新左右子的 sum
    add[rt<<1]+=add[rt],add[rt<<1|1]+=add[rt];// 更新左右子的标记
    add[rt]=0;// 当前标记清零
}

每次,在调用或经过这个结点的时候,首先 pushdown 以获取到这个结点的准确数据,并保证在下层结点修改的时候,是在准确数据的基础上修改;也就是说,在更新当前结点(比如区间加的时候),要保证它的祖先路径上的结点的 lazytag 全部下传清零

对于下层的子结点作修改之后,要在递归结尾 pushup 来把数据更新回来

因为不需要递归更新(只需要随着路径调用 pushdown),所以复杂度降至 .

模板

[LuoguP3373] 线段树 2

维护区间加 / 乘 / 求和

对线段树的多重不同优先级的区间操作。加法和乘法的优先级不同。因此简单的两个同级 lazytag 不能正确维护线段树。

考虑两个 lazytag:addmul

mul 比 add 优先。区间加法时,直接更新 add 即可区间乘法更新时,除了更新 mul,还要更新 add。根据乘法分配律,所以

#include<bits/stdc++.h>
#define SIZE 262150
using namespace std;
typedef long long ll;
ll n,m,p;
ll a[100001];
ll s[SIZE],add[SIZE],mul[SIZE];
//tag_add&tag_mul
void push_down(ll l,ll r,ll rt){
    ll mid=(l+r)>>1;

    s[rt<<1]=(s[rt<<1]*mul[rt]%p+add[rt]*(mid-l+1)%p)%p;
    add[rt<<1]=(add[rt<<1]*mul[rt]%p+add[rt])%p;
    mul[rt<<1]=mul[rt<<1]*mul[rt]%p;

    s[rt<<1|1]=(s[rt<<1|1]*mul[rt]%p+add[rt]*(r-mid)%p)%p;
    add[rt<<1|1]=(add[rt<<1|1]*mul[rt]%p+add[rt])%p;
    mul[rt<<1|1]=mul[rt<<1|1]*mul[rt]%p;

    add[rt]=0,mul[rt]=1;// 注意 mul 的清零是 1 不是 0
}
void push_up(ll rt){
    s[rt]=(s[rt<<1]+s[rt<<1|1])%p;
}
ll lst_build(ll l,ll r,ll rt){
    mul[rt]=1;
    if(l==r)return s[rt]=a[l];
    ll mid=(l+r)>>1;
    lst_build(l,mid,rt<<1),lst_build(mid+1,r,rt<<1|1);
    push_up(rt);
}
ll lst_add(ll L,ll R,ll l,ll r,ll rt,ll v){
    if(R<l||r<L)return 0;
    else if(L<=l&&r<=R)return add[rt]=(add[rt]+v)%p,s[rt]=(s[rt]+v*(r-l+1)%p)%p;
    ll mid=(l+r)>>1;
    push_down(l,r,rt);
    lst_add(L,R,l,mid,rt<<1,v),lst_add(L,R,mid+1,r,rt<<1|1,v);
    push_up(rt);
}
ll lst_mul(ll L,ll R,ll l,ll r,ll rt,ll v){
    if(R<l||r<L)return 0;
    else if(L<=l&&r<=R)return mul[rt]=mul[rt]*v%p,add[rt]=add[rt]*v%p,s[rt]=s[rt]*v%p;
    ll mid=(l+r)>>1;
    push_down(l,r,rt);
    lst_mul(L,R,l,mid,rt<<1,v),lst_mul(L,R,mid+1,r,rt<<1|1,v);
    push_up(rt);
}
ll lst_sum(ll L,ll R,ll l,ll r,ll rt){
    if(R<l||r<L)return 0;
    else if(L<=l&&r<=R)return s[rt];
    ll mid=(l+r)>>1;
    push_down(l,r,rt);
    return (lst_sum(L,R,l,mid,rt<<1)+lst_sum(L,R,mid+1,r,rt<<1|1))%p;
}
int main(){
    scanf("%lld%lld%lld",&n,&m,&p);
    for(ll i=1;i<=n;i++)scanf("%lld",&a[i]);
    lst_build(1,n,1);
    for(ll i=1,a,x,y,k;i<=m;i++){
        scanf("%lld%lld%lld",&a,&x,&y);
        if(a==1){
            scanf("%lld",&k);
            lst_mul(x,y,1,n,1,k);
        }
        else if(a==2){
            scanf("%lld",&k);
            lst_add(x,y,1,n,1,k);
        }
        else printf("%lld\n",lst_sum(x,y,1,n,1));
    }
    return 0;
}

  转载请注明: Sshwy's Blog 线段树初步

 上一篇
Splay 初步 Splay 初步
2019.6.19 编入精选文章。 前言 平衡树是计算机科学中的一类改进的二叉查找树。一般的二叉查找树的查询复杂度是跟目标结点到树根的距离(即深度)有关,因此当结点的深度普遍较大时,查询的均摊复杂度会上升,为了更高效的查询,平衡树应运而生了
2018.12.19
下一篇 
[LuoguP1357] 花园 [LuoguP1357] 花园
暴力 DP首先有一个暴力状压 DP, 表示以第 个花盆结尾,后 个花盆的二进制状态为 (1 为 C,0 为 P)时的方案数 对于环形的处理,我们让两个相同状态作为 DP 的初始和结尾即可.具体的说,初始
2018.12.17
  目录