segement tree trick

2019-09-25 public 学习笔记 0 Comments

SGTtrick

$By\ 蒟蒻\ ldxcaicai$

Chapter 1.关于线段树操作的一些分析

我们知道，线段树有两个核心的函数$pushdown$和$pushup$。

以及两类对于一段区间进行操作的函数$update$和$query$

博主在这里简单讲一下几个函数的功能：

首先我们假设用$Val$表示维护信息的类型，$Tag$表示懒标记的类型。

显然一个线段树节点（类型为$Node$）是由一个$Val$元素和一个$Tag$以及表示区间管辖范围的$l,r$构成的。

1
2
3

struct Tag{...};
struct Val{...};
struct Node{Val val;Tag tag;int l,r;}T[N<<2];

$pushdown(int\ p)$表示将$p$的标记下传给$p$的儿子并更新它们的信息和标记
$pushup(int\ p)$表示把$p$儿子的信息合并成$p$的信息
$query(int\ p,int\ ql,int\ qr)$表示查询区间$[ql,qr]$的一些信息
$update(int\ p,int\ ql,int\ qr,Tag\ v)$表示用标记$v$对区间$[ql,qr]$的信息和标记进行更新

可以看出来这些函数分成两类：

父亲朝儿子转移：$update,pushdown$
儿子朝父亲转移：$query,pushup$

而我们继续将这几个函数的功能进行拆分并取上并集（雾，发现它其实是这几个东西的组合：

两个$Val$类型的元素的合并
一个$Tag$类型的元素对一个$Val$类型的元素的更新

一个$Tag$类型的元素对一个$Tag$类型的元素的更新

inline Tag operator+(const Tag&a,const Tag&b){...}
inline void operator+=(Tag&a,const Tag&b){a=a+b;}
inline Val operator+(const Val&a,const Tag&b){...}
inline void operator+=(Val&a,const Tag&b){a=a+b}
inline Val operator+(const Val&a,const Val&b){...}
inline void operator+=(Val&a,const Val&b){a=a+b;}

如果我们对这几个操作重载运算符的话，那么上述函数的实现就很简单了，为了让实现更加简便可以设计一个$pushnow函数$。

$pushup$函数：把儿子的$Val$合并成自己的$Val$。

1
2
3

inline void pushup(int p){
    T[p].val=T[lc].val+T[rc].val;
}

$pushnow$函数：$pushnow(int\ p,Tag\ v)$表示用标记$v$更新节点$p$的信息和标记。
代码：
1
2
3
inline void pushnow(int p,Tag v){
T[p].val+=v,T[p].tag+=v;
}

$pushdown$函数：用自己的$Tag$去更新儿子的$Val$和$Tag$

inline void pushdown(int p){
    if(check(T[p].tag))return;
    pushnow(lc,T[p].tag),pushnow(rc,T[p].tag);
    T[p].tag=tag_empty;
}

$query$函数：把要查询的区间拆成线段树上至多$log$个区间把它们的$Val$按一定顺序合并起来。

inline Val query(int p,int ql,int qr){
    if(ql>T[p].r||qr<T[p].l)return val_empty;
    if(ql<=T[p].l&&T[p].r<=qr)return T[p].val;
    pushdown(p);
    if(qr<=mid)return query(lc,ql,qr);
    if(qr>mid)return query(rc,ql,qr);
    return query(lc,ql,qr)+query(rc,ql,qr);
}

$update$函数：把要修改的区间拆成线段树上至多$log$个区间分别用给出的$Tag$更新它们的$Tag$和$Val$。

inline void update(int p,int ql,int qr,Tag v){
    if(ql>T[p].r||qr<T[p].l)return;
    if(ql<=T[p].l&&T[p].r<=qr)return pushnow(p,v);
    pushdown(p);
    if(qr<=mid)update(lc,ql,qr,v);
    else if(ql>mid)update(rc,ql,qr,v);
    else update(lc,ql,qr,v),update(rc,ql,qr,v);
    pushup(p);
}

所以当你拿到一道线段树题的时候，思考上述三种运算符如何重载即可$qwq$。

那么最后我们给上一波上述所有内容合起来的伪代码：才不会告诉你这是一个通用的框架呢

namespace SGT{
    #define lc (p<<1)
    #define rc (p<<1|1)
    #define mid (T[p].l+T[p].r>>1)
    struct Tag{...};
    struct Val{...};
    const Tag tag_empty=(Tag){...};
    const Val val_empty=(Val){...};
    inline Tag operator+(const Tag&a,const Tag&b){...}
    inline void operator+=(Tag&a,const Tag&b){a=a+b;}
    inline Val operator+(const Val&a,const Tag&b){...}
    inline void operator+=(Val&a,const Tag&b){a=a+b}
    inline Val operator+(const Val&a,const Val&b){...}
    inline void operator+=(Val&a,const Val&b){a=a+b;}
    struct Node{Val val;Tag tag;int l,r;}T[N<<2];
    inline bool check(const Tag&v){...}
    inline void pushdown(int p){
        if(check(T[p].tag))return;
        T[lc].val+=T[p].tag,T[lc].tag+=T[p].tag;
        T[rc].val+=T[p].tag,T[rc].tag+=T[p].tag;
        T[p].tag=tag_empty;
    }
    inline void pushup(int p){
        T[p].val=T[lc].val+T[rc].val;
    }
    inline void build(int p,int l,int r){
        T[p]=(Node){val_empty,tag_empty,l,r};
        if(l==r){
            T[p].val=(Val){...};
            return;
        }
        build(lc,l,mid);
        build(rc,mid+1,r);
        pushup(p);
    }
    inline void update(int p,int ql,int qr,Tag v){
        if(ql>T[p].r||qr<T[p].l)return;
        if(ql<=T[p].l&&T[p].r<=qr){
            T[p].val+=v,T[p].tag+=v;
            return;
        }
        pushdown(p);
        if(qr<=mid)update(lc,ql,qr,v);
        else if(ql>mid)update(rc,ql,qr,v);
        else update(lc,ql,qr,v),update(rc,ql,qr,v);
        pushup(p);
    }
    inline Val query(int p,int ql,int qr){
        if(ql>T[p].r||qr<T[p].l)return val_empty;
        if(ql<=T[p].l&&T[p].r<=qr)return T[p].val;
        pushdown(p);
        if(qr<=mid)return query(lc,ql,qr);
        if(qr>mid)return query(rc,ql,qr);
        return query(lc,ql,qr)+query(rc,ql,qr);
    }
    #undef lc
    #undef rc
    #undef mid
}

Chapter 2.线段树的两种写法

吐槽：我吐我自己

这里简单谈一谈线段树的两种实现方法：$dfs$版和$bfs$版，其中后者为我瞎$yy$的，经过测试实际效果跟$dfs$版差距不大。

~~我才不会告诉你们我测出来很多题用第二种写法要慢一些呢~~

好吧我承认我发现的这种$bfs$版写法很鸡肋。

正题

众所周知，搜索有几种顺序，其中有两种很著名分别叫做$dfs$和$bfs$。

而我们的常规线段树就是使用的$dfs$序。

然而在博主的努力尝试下，$bfs$序也是可以处理的。

为什么呢？

因为在$Chapter\ 1$中我们已经谈到过线段树的$query$和$update$操作的本质了：

$query$函数：把要查询的区间拆成线段树上至多$log$个区间把它们的$Val$按顺序合并起来。
$update$函数：把要修改的区间拆成线段树上至多$log$个区间分别用给出的$Tag$更新它们的$Tag$和$Val$。

这样的话，只要按照顺序把这$log$段区间找到再合起来一定就可以维护所有的操作。

因为按照$bfs$版本的顺序来合并也是正确的。

如何维护顺序？用一个队列即可。

于是我们可以给出$bfs$版的一些框架，这里跟$dfs$版本相同的函数就不拿上来了。

代码如下：

namespace SGT{
    ...
    int q[N<<2],hd,tl;
    inline void build(int n){
        q[hd=tl=1]=1,T[1]=(Node){val_empty,tag_empty,1,n};
        while(hd<=tl){
            int p=q[hd++];
            if(T[p].l==T[p].r){
                T[p].val=(Val){...};
                continue;
            }
            T[lc]=(Node){val_empty,tag_empty,T[p].l,mid};
            T[rc]=(Node){val_empty,tag_empty,mid+1,T[p].r};
            q[++tl]=lc,q[++tl]=rc;
        }
        for(ri i=tl;i^1;--i)T[q[i]>>1].val+=T[q[i]].val;
    }
    inline void update(int p,int ql,int qr,Tag v){
        q[hd=tl=1]=1;
        while(hd<=tl){
            int p=q[hd++];
            if(ql>T[p].r||qr<T[p].l)continue;
            if(ql<=T[p].l&&T[p].r<=qr){
                pushnow(p,v);
                continue;
            }
            pushdown(p);
            if(qr<=mid)q[++tl]=lc,T[p].val=T[rc].val;
            else if(ql>mid)q[++tl]=rc,T[p].val=T[lc].val;
            else q[++tl]=lc,q[++tl]=rc,T[p].val=val_empty;
        }
        for(ri i=tl;i^1;--i)T[q[i]>>1].val+=T[q[i]].val;
    }
    inline Val update(int p,int ql,int qr,Tag v){
        Val ret=val_empty;
        q[hd=tl=1]=1;
        while(hd<=tl){
            int p=q[hd++];
            if(ql>T[p].r||qr<T[p].l)continue;
            if(ql<=T[p].l&&T[p].r<=qr){
                ret+=T[p].val;
                continue;
            }
            pushdown(p);
            if(qr<=mid)q[++tl]=lc;
            else if(ql>mid)q[++tl]=rc;
            else q[++tl]=lc,q[++tl]=rc;
        }
        return ret;
    }
    ...
}

经过我们的努力改动，代码量成功翻了一倍！！！(滑稽
$That’s\ all$
$Thank\ you$

本文链接： http://ldxcaicai.github.io/SGTtrick/

版权声明： 本博客所有文章除特别声明外，均采用 CC BY 4.0 CN协议许可协议。转载请注明出处！

ldxcaicai

a loser😬😦😭😢😰

segement tree trick

SGTtrick

Chapter 1.关于线段树操作的一些分析

Chapter 2.线段树的两种写法

吐槽：我吐我自己

正题

ldxcaicaia loser😬😦😭😢😰