[算法学习笔记]线段树

USSENTERPRISE · 2019-11-24 10:04:51 · 个人记录

0.解决问题

在树状数组那篇博客中，留下了一个坑：

区间修改区间查询

树状数组博客传送门

今天我们就要来解决这个问题

1.前置知识

二分

二叉树

都很简单

2. 简介

线段树是一种可以较快维护满足区间可加性区间信息（如：区间和，区间积，区间最大最小等）的数据结构，其基本思想就是二分。

注：区间可加性指一些可以通过子区间信息合并维护的信息，如区间最大就可以由二分后两个子区间最大值得到

3. 基本操作（以区间加和为例，无优化）

约定

以下代码运用到的宏和全局变量及其解释：

#define ls now<<1
#define rs now<<1|1

建树

对于一棵线段树，我们可以递归地建树。根据二分的思想，我们可以每次进行二分，分别建立左子树和右子树，直到递归到叶子结点（即l=r）

• pushup操作

pushup操作是用来合并子区间信息的操作，对于区间加和，此操作所干的事就是sumv_{[l,r]}=sumv_{[l,mid]}+sumv_{[mid+1,r]}

建树代码如下：

inline void pushup(int now){ sumv[now]=sumv[ls]+sumv[rs]; }
inline void build(int now,int l,int r){
    if(l==r){ sumv[now]=a[l]; return;}

    rg int mid=(l+r)>>1;
    build(ls,l,mid);
    build(rs,mid+1,r);

    pushup(now);

}

单点修改

其实完全不用这样维护

基本思想：二分查找

代码：

inline void change(int now,int l,int r,int x,int v){
    if(l==r){ sumv[now]=v; return; }
    rg int mid=(l+r)>>1;
    if(x<=mid) change(ls,l,mid,x,v);
    else change(rs,mid+1,r,x,v);
    pushup(now);
}

区间修改

二行版

思想：对于一个想要修改的区间[ql,qr]，假设你现在到了编号为now的节点，其管控的区间为[l,r]，中点为mid，如果ql \leq mid则证明修改区间与[l,mid]有相交的部分，需修改左半区间；同理，如果mid<qr，则需修改右区间（如下图）

代码如下：

inline void change(int now,int l,int r,int ql,int qr,int v){
    if(l==r){ sumv[now]+=v; return; }

    int mid=(l+r)>>1;

    if(ql<=mid) change(ls,l,mid,ql,qr,v);
    if(mid<qr) change(rs,mid+1,r,ql,qr,v);

    pushup(now);
}

三行版

思想：对于一个想要修改的区间[ql,qr]，假设你现在到了编号为now的节点，其管控的区间为[l,r]，中点为mid，如果ql>mid，则证明所需修改的区间全部位于右半区间及其以右，修改右区间；同理，如果qr\leq mid，需修改右区间。额外的，其他情况则证明修改区间左右兼占，需修改两个区间（如下图）

inline void optadd(int now,int l,int r,int ql,int qr,int v){
    if(l==r){ sumv[now]+=v; return; }
    rg int mid=(l+r)>>1;
    if(ql>mid) optadd(rs,mid+1,r,ql,qr,v);
    else if(qr<=mid) optadd(ls,l,mid,ql,qr,v);
    else optadd(ls,l,mid,ql,qr,v),optadd(rs,mid+1,r,ql,qr,v);
}

注：请注意二行版与三行版关于情况之间关系的不同

区间查询

思想：对于一个查询区间[ql,qr]，为了节省时间，只需递归到一个包含于此区间的区间[l_i,r_i]即可。ans=\sum[l_i,r_i]

注：二行版和三行版思想与上方相同，下同，不再解释

//二行版
inline int query(int now,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr) return sumv[now];
    rg int mid=(l+r)>>1,ans=0;
    if(ql<=mid) ans+=query(ls,l,mid,ql,qr);
    if(mid<qr) ans+=query(rs,mid+1,r,ql,qr);
    return ans;
}
//三行版
inline int query(int now,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr) return sumv[now];
    rg int mid=(l+r)>>1,ans=0;
    if(ql>mid) ans=query(rs,mid+1,r,ql,qr,v);
    else if(qr<=mid) ans=query(ls,l,mid,ql,qr,v);
    else ans=query(ls,l,mid,ql,qr,v)+query(rs,mid+1,r,ql,qr,v);
    return ans;
}

4. 线段树的基本优化(lazy标记)

可以发现，我们在区间修改这一环节时间开销比较大，每次修改都需要递归到叶子结点才可以完成。但是查询时并不需要查找每个叶子节点的值

所以懒惰的人类就有了lazy标记这种做法

我们只需要在每次修改时为区间打上一个标记，在需要查询叶子结点时再将标记和修改下放一层，就可以以较小的时间开销完成修改。

pushdown操作