线段树的一些延伸

一.动态开点线段树

简介

虽然思路简单，但对于一个习惯数组写法的人，这是一个比较难受的东西。

动态开点一般是用来解决空间上的问题的。

一般来说，普通的线段树是直接将一颗完整的线段建出来，但如碰到数据范围大或卡空间的时候，我们就只能在我们需要的时候再建，这个就叫做动态开点。（类似于 trie）

处理方法

• 结构体

动态开点用数组是极不方便的，所以采用结构体写法。（本人真的很不习惯）

struct Tree
{
    int sum;
    int l,r;
}t[MAXN<<5];

• 上传

inline void pushup(int p)
{
    t[p].sum=t[t[p].l].sum+t[t[p].r].sum;
    return;
}

• 下传

由于跑到的节点可能没建过，所以要新建。

inline void pushdown(int p)
{
    if(!t[p].l) t[p].l=++tot;
    if(!t[p].r) t[p].r=++tot;
    return;
}

• 单点修改

inline void change(int p,int l,int r,int x,int k)
{
    if(l==r) {t[p].sum+=k;return;}
    int mid=(l+r-1)>>1; pushdown(p);
    if(x<=mid) change(t[p].l,l,mid,x,k);
    else change(t[p].r,mid+1,r,x,k);
    pushup(p); return;
}

• 求和

inline int ask(int p,int l,int r,int a,int b)
{
    if(l>b || r<a) return 0;
    if(l>=a && r<=b) return t[p].sum;
    int mid=(l+r-1)>>1,ans=0; pushdown(p);
    if(a<=mid) ans+=ask(t[p].l,l,mid,a,b);
    if(b>mid) ans+=ask(t[p].r,mid+1,r,a,b);
    return ans;
}

二.权值线段树

简介

对于值域建立的线段树，用于统计区间内某个数出现次数。

支持维护同一个动态区间第 \(k\) 小（反之同理），支持单点修改。

修改与查询的复杂度均为 \(O(\log n)\)。

处理方法

• 建树

建树只需维护左右区间，无需赋值。

1. 用每个节点维护原序列中的值；
2. 记录每个区间每个数的出现次数；

inline void build(int p,int l,int r)
{
    t[p].l=l,t[p].r=r;
    if(l==r) return;
    int mid=(l+r)>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    return;
}

特别地，因为权值线段树又名值域线段树，所以建树是基于值域建的。

如：

题目规定：\(a_i\leqslant 10^5\)

那么建树操作便为 build(1,1,100000)。

• 修改

权值线段树在修改中可以维护区间第 \(k\) 小于前 \(k\) 小的和，故需要统计一下。

inline void change(int p,int k)
{
    t[p].val+=k,t[p].num++;
    if(t[p].l==t[p].r) return;
    if(k>=t[p<<1|1].l) change(p<<1|1,k);
    else change(p<<1,k);
    return;
}

• 查询

有了上面统计的那些信息，区间求值就很容易了。

区间前 \(k\) 小之和

inline int ask1(int p,int k)
{
    if(t[p].l==t[p].r) return t[p].val/t[p].num*k;
    if(k>t[p<<1].num) return t[p<<1].val+ask1(p<<1|1,k-t[p<<1].num);
    else return ask1(p<<1,k);
}

区间第 \(k\) 小

inline int ask2(int p,int k)
{
    if(t[p].l==t[p].r) return t[p].val/t[p].num;
    if(k>t[p<<1].num) return ask2(p<<1|1,k-t[p<<1].num);
    else return ask2(p<<1,k);
}

三.主席树

简介

又名可持久化权值线段树，用于动态维护任意区间第 \(k\) 大。

支持单点修改和区间查询。

处理方法

主席树的思想是对每一个前缀均建立一颗权值线段树。

• 初始化

我们发现，由于空间复杂度的问题，我们需要动态开点，所以就无法直接算出一个节点的左右儿子，所以都要记录一下。

需要注意的是，主席树一般要开32倍空间。

\(rt_i\) 为版本 \(i\) 的标号。

int id[MAXN];

struct Tree
{
    int l,r,val;
}e[MAXN<<5];

• 建树

我们无法直接算出左右儿子编号，所以建树可以只用统计 \(id\) 数组。

inline void build(int &p,int l,int r)
{
    p=++cnt;
    if(l==r) return;
    int mid=(l+r)>>1;
    build(t[p].l,l,mid);
    build(t[p].r,mid+1,r);
    return;
}

\(cnt\) 表示动态开点的编号。

• 修改

与权值线段树唯一不同的是要再开一颗线段树。

inline int change(int p,int l,int r,int k)
{
    int rt=++cnt;
    t[rt]=t[p],t[rt].val++;
    if(l==r) return rt;
    int mid=(l+r)>>1;
    if(k<=mid) t[rt].l=change(t[p].l,l,mid,k);
    else t[rt].r=change(t[p].r,mid+1,r,k-x);
    return rt;
}

• 查询

由于每一颗线段树的结构相同，具有可加减性。

并且我们建立的是关于前缀的线段树，所以我们可以用前缀和的思想。

inline int ask(int l,int r,int a,int b,int k)
{
    int ans=0,mid=(l+r)>>1;
    int x=t[t[b].l].val-t[t[a].l].val;
    if(l==r) return l;
    if(k<=x) ans=ask(l,mid,t[a].l,t[b].l,k);
    else ans=ask(mid+1,r,t[a].r,t[b].r,k);
    return ans;
}

• 离散化

考虑到空间问题，我们需要离散化。

inline void dist()
{
    sort(b+1,b+n+1);
    m=unique(b+1,b+n+1)-b-1;
    build(id[0],1,m);
    for(int i=1;i<=n;i++)
    {
        int p=lower_bound(b+1,b+m+1,a[i])-b;
        id[i]=change(id[i-1],1,m,p);
    }
    return;
}

到这里，主席树的模板就没了，但还有一些操作需要自己去探索。

例题：

• P3919 【模板】可持久化线段树1
• P3834 【模板】可持久化线段树2
• P3567 [POI2014]KUR-Couriers

四.线段树合并

思想

前置知识：动态开点线段树、权值线段树。

顾名思义，就是建立一颗新的线段树，保存原有两颗线段树的信息。

这个思想比较简单，假设我们现在合并到了两棵线段树 \(a,b\) 的 \(p\) 位置，那么：

1.如果 \(a\) 有 \(p\) 位置，\(b\) 没有，那么新的线段树 \(p\) 位置赋成 \(a\)，返回；
2.如果 \(b\) 有 \(p\) 位置，\(a\) 没有，赋成 \(b\)，返回；
3.如果此时已经合并到两棵线段树的叶子节点了，就把 \(b\) 在 \(p\) 的值加到 \(a\) 上，把新线段树上的 \(p\) 位置赋成 \(a\)，返回；
4.递归处理左子树，递归处理右子树；
5.用左右子树的值更新当前节点；
6.将新线段树上的 \(p\) 位置赋成 \(a\)，返回；

处理方法

• 合并

线段树合并的核心操作。

inline int merge(int a,int b,int l,int r)
{
    if(!a) return a;
    if(!b) return b;
    if(l==r) return a;
    int mid=(l+r)>>1;
    t[a].l=merge(t[a].l,t[b].l,l,mid);
    t[a].r=merge(t[a].r,t[b].r,mid+1,r);
    pushup(a); return a;
}

假设要插入的点数为 \(n\)，那么时空复杂度均为 \(\Theta(n\log n)\)