线段树全家桶（持续咕咕咕）

NuoCarter · 2020-09-11 23:05:06 · 个人记录

线段树全家桶

线段树基础

原理：

将一个大区间划分为若干个小区间，每一个小区间都对应这线段树中的一个结点。（分治的思想）

这个线段树采用二倍编号规则。

即一个结点的左儿子为这个结点的编号的两倍，右儿子为两倍加一。

结构体定义：

#define lc x<<1
#define rc x<<1|1
struct node{
    int l,r;
    ll sum,lazy;
    #define l(x)    c[x].l
    #define r(x)    c[x].r
    #define sum(x)  c[x].sum
    #define lazy(x) c[x].lazy
}c[400005];

基本操作（无push_down操作）：

以下均以求区间和为例子

更新结点值(update 又称 push_up)

inline void update(int x){
    sum(x)=sum(lc)+sum(rc);
}

建树(build)

inline void build(int x,int l,int r){
  l(x)=l;
  r(x)=r;
  if(l==r) {//已经到了叶子结点
    sum(x)=a[l];
    return;
  }
  int mid=(l+r)>>1;
  build(lc,l,mid);
  build(rc,mid+1,r);
  update(x);
}

单点修改

就是简单的修改叶子结点然后回溯修改父亲结点的值

inline void modify(int x,int L,int R,int t){
    if(l(x)==L&&r(x)==R){
        sum(x)+=t;
        return;
    }
    int mid=(l(x)+r(x))>>1;
    if(mid>=L){modify(lc,L,R,t);}
    if(mid<R){modify(rc,L,R,t);}
    update(x);
    return;
}

区间求和：

要求查询一个区间[L,R] 如何求出$ \sum_{i=L}^R {a_i}

###### 1.朴素算法十分暴力的求复杂度为 $O(n)

int sum=0;
for(int i=L;i<=R;++i){
    sum+=a[i];
}
return sum;

2.线段树的查询方法：

可以表示为 log n 个区间和的和

对于一个区间：它有四种情况： 1.它 完全包含 于这个区间对于这种情况我们直接

return  sum(x);

2.左儿子有一部分包含于这个区间

if(mid>=L){ans+=query(lc,L,R);}

3.右儿子有一部分包含于这个区间

if(mid<R){ans+=query(rc,L,R);}

. .4.它根本不在查询区间中

return 0;

这样子就可以写出查询代码了

inline ll query(int x,int L,int R){
    if(t[x].l>=L&&t[x].r<=R){return sum(x);}
    if(t[x].l>R||t[x].r<L){return 0;}
    int mid=(l(x)+r(x))>>1;
    ll ans=0;
    if(mid>=L){ans+=query(lc,L,R);}
    if(mid<R){ans+=query(rc,L,R);}
    return ans;
}

复杂度O(\log_{2}^{n})

进阶操作（push_down)

区间修改

暴力修改：

对在 [L,R] 的每一个叶子结点都进行一次单点修改操作

复杂度O(n\log_{2}^{n})

线段树延迟修改（push_down操作，懒标记维护）

对于一个区间：

你在修改的时候修改完了，后续的查询却根本没有用到这个区间，那你的这次修改就是无用的。

所以我们可以在一次修改中，只修改目标修改区间中的多个最大子区间，修改这个区间的sum 和 lazy 就可以了，懒标记(lazy)表示当前区间的子节点是否被修改过，如需要，需要修改的 d 为多少，通过懒标记就可以维护区间修改的线段树区间和了。

比如：

当我们修改区间 [1,6] 时只需要修改区间 [1,4] 和区间 [5,6] ，还有 [1,4] 的两个子区间 [1,2] 与 [3,4] 和 [5,6] 的两个子区间 [5,5] [6,6]

修改：值修改区间的 lazy 和 sum

这样我们在区间修改时就可以做到严格log n 了

push_down 操作

顾名思义是将一些东西下传线段树中需要下传的东西可能就一个懒标记($lazy$)了但是你下传两个子区间的同时，也要将两个子区间的 $sum$ 用 $lazy$ 给更新了 $push$_$down$ Code: ``` cpp inline void add(int x,ll d){//单纯为了好看而已 sum(x)+=(r(x)-l(x)+1)*d; lazy(x)+=d; } inline void push_down(int x){ if(lazy(x)){ add(lc); add(rc); lazy(x)=0; return; } } ``` 区间修改Code: ``` cpp inline void add(int x,ll d){ sum(x)+=(r(x)-l(x)+1)*d; lazy(x)+=d; } inline void push_down(int x){ if(lazy(x)){ add(lc,lazy(x)); add(rc,lazy(x)); lazy(x)=0; return; } } inline void modify(int x,int L,int R,ll d){ if(l(x)>=L&&r(x)<=R){add(x,d);return;} push_down(x); int mid=(l(x)+r(x))>>1; if(mid>=L){modify(lc,L,R,d);} if(mid<R){modify(rc,L,R,d);} update(x); return; } ``` 那么为什么要在$modify$中加上一个 push_down 呢？按照懒标记的逻辑，不是只用在 $query$ 里面加上 push_down 就好了么？但是我们在修改时也在往下递归，这时加上一个 push_down 可以有效的防止懒标记溢出，也可以防止修改时溢出（比如需要中间取mod时），而且你之后要push_down，可能这个区间有懒标记，但是没有下传，经过了一遍 modify 后 update 的还是原本的值，此时的 query 可能查询到的就是一个错误的值，所以必须加上 push_down ### 区间修改后查询区间和因为区间修改只修改了目标修改区间的最大子区间，而你的区间查询有可能会访问到这个最大子区间的更小的几个子区间所以你在查询的同时也要进行$push$_$down$ 操作（就比单点修改查询多一个$push$_$down$而已） Code: ``` cpp inline ll query(int x,int L,int R){ if(l(x)>=L&&r(x)<=R){return sum(x);} push_down(x); int mid=(l(x)+r(x))>>1; ll ans=0; if(mid>=L){ans+=query(lc,L,R);} if(mid<R){ans+=query(rc,L,R);} return ans; } ``` ## 值域线段树 ## 例题： ### 求逆序对：题意懂得都懂，求有多少个逆序对普通做法：归并排序复杂度($n$ $log$ $n$),这是一个不需要离散化的做法。值域线段树做法：对于一个数列 {$a_i$} 由于逆序对的定义为$i>j$ && $a_j>a_i

那么我们可以O(n)扫描整个序列

对于每一个元素a_i进行以下操作：

查找 [1,a_i-1] 有多少个数

将[a_i,a_i] 加上 1。

整个复杂度(n log V)

但是显而易见，当值域够大时，线段树的$4$倍空间是开不下的。那么显而易见加一个离散化就好了。 ~~不会吧不会吧我会真有人学到了值域线段树都不会离散化的吧~~ 经典$sort$ + $unique$ + $lower$_$bound$ 离散化 ## 值域线段树优化DP #### 导弹拦截假装这是一个求最长上升子序列的题我们定义：$dp[i]$ 为以 $i$ 结尾的最长上升子序列长度：那么，$dp[i]$肯定是从$dp[1$~$i-1]$ 转移过来的因为求的是最长上升子序列，所以 $dp[i]=max(dp[1$~$i-1])+1

通常的暴力都是O(n)查询之前的最大值

而线段树就是用来优化的这个查询过程

遇到一个a[i]

查询[1,a[i]-1]间dp[i]的最大值max

dp[a[i]]=max+1

然后在线段树中将a[i]这个值修改为dp[a[i]]

~~听起来就很简单~~

扫描线

我不会(或者说我一直没有过板子题）先咕咕咕好了

各种进阶例题：

区间开方操作：

P4145 上帝造题的七分钟2 / 花神游历各国

题目描述：

第一行一个整数 n ，代表数列中数的个数。

第二行 n 个正整数，表示初始状态下数列中的数。

第三行一个整数 m ，表示有 m 次操作。

接下来 m 行每行三个整数k,l,r

$k=1$ 表示询问 $[L,R]$ 中各个数的和。数据中有可能 $L>R$，所以遇到这种情况请交换 $L$ 和 $R$。原题数据中的$a_i$最大值为$10^{12}

易证昂，所有\leq 10^{12}的数，都可以在 \leq6次开根的情况下变为 1。

因为1,0 的根号还是1,0

所以当我们修改到一个区间全为1或者0时，完全可以跳过这个区间的修改：

于是我们在整个区间开方的过程中维护两个变量：

一个sum区间和,一个maxn表示区间最大值

因为开方并不满足区间可加性，我们可以转而使用复杂度略高的进行n次单点修改

每一次的复杂度为(n log n)

但是每一个点最多修改6次，所以是可以通过这道题的

Code:

#define ll long long
#define lc x<<1
#define rc x<<1|1
struct node{
    int l,r;
    ll sum，maxinum;
    #define l(x) t[x].l
    #define r(x) t[x].r
    #define sum(x) t[x].sum
    #define maxinum(x)  t[x].maxinum
}t[4000005];
int n,m;
ll a[100005];
inline void update(int x){
    sum(x)=sum(lc)+sum(rc),maxinum(x)=max(maxinum(lc),maxinum(rc));
    return;
}
inline void build(int x,int l,int r){
    l(x)=l;
    r(x)=r;
    if(l==r){
        sum(x)=a[l];
        maxinum(x)=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(lc,l,mid);
    build(rc,mid+1,r);
    update(x);
}
inline void modify(int x,int L,int R){
    if(l(x)==r(x)){
        sum(x)=sqrt(sum(x));
        maxinum(x)=sqrt(maxinum(x));
        return;
    }
    int mid=(l(x)+r(x))>>1;
    if(mid>=L&&maxinum(lc)>1){modify(lc,L,R);}
    if(mid<R&&maxinum(rc)>1){modify(rc,L,R);}
    update(x);
    return;
}
inline ll query(int x,int L,int R){
    if(l(x)>=L&&r(x)<=R){return sum(x);}
    ll tep=0;
    int mid=(l(x)+r(x))>>1;
    if(mid>=L){tep+=query(lc,L,R);}
    if(mid<R){tep+=query(rc,L,R);}
    return tep;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){scanf("%lld",&a[i]);}
    build(1,1,n);
    scanf("%d",&m);
    for(int i=1;i<=m;++i){
        int op,L,R;
        scanf("%d%d%d",&op,&L,&R);
        if(L>R){swap(L,R);}
        if(op==0){modify(1,L,R);}
        else{printf("%lld\n",query(1,L,R));}
    }
    return 0;
}