JZTXT

线段树的一些延伸

发布时间 2023-08-09 22:10:33作者: Code_AC

一.动态开点线段树

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

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

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

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

例题：