线段树及其扩展

发布于 10 天前  67 次阅读


线段树是一种维护区间性质,满足符合结合律的运算的区间修改的数据结构。

基本实现

朴素线段树

#include<iostream>
using namespace std;
using ll=long long;
#define int ll
const int maxn=1e5+10;
int a[maxn],tree[maxn<<2],mark[maxn<<2];
void build(int node,int l,int r)
{
    if(l==r)tree[node]=a[l];
    else{
        int mid=(l+r)>>1;
        build(node<<1,l,mid);
        build(node<<1|1,mid+1,r);
        tree[node]=tree[node<<1]+tree[node<<1|1];
    }
}
void push_down(int node,int len)
{
    mark[node<<1]+=mark[node];
    mark[node<<1|1]+=mark[node];
    tree[node<<1]+=mark[node]*(len-(len>>1));
    tree[node<<1|1]+=mark[node]*(len>>1);
    mark[node]=0;
}
void update(int node,int l,int r,int L,int R,int d)
{
    if(L>r||R<l)return;
    else if(l>=L&&r<=R){
        tree[node]+=(r-l+1)*d;
        if(r>l)mark[node]+=d;
    }
    else{
        int mid=(l+r)>>1;
        push_down(node,r-l+1);
        update(node<<1,l,mid,L,R,d);
        update(node<<1|1,mid+1,r,L,R,d);
        tree[node]=tree[node<<1]+tree[node<<1|1];
    }
}
int query(int node,int l,int r,int L,int R)
{
    if(L>r||R<l)return 0;
    else if(l>=L&&r<=R)return tree[node];
    else{
        int mid=(l+r)>>1;
        push_down(node,r-l+1);
        return query(node<<1,l,mid,L,R)+query(node<<1|1,mid+1,r,L,R);
    }
}
signed main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    build(1,1,n);
    int oper,x,y,k;
    for(int i=1;i<=m;i++){
        cin>>oper>>x>>y;
        if(oper==1){
            cin>>k;
            update(1,1,n,x,y,k);
        }
        else{
            cout<<query(1,1,n,x,y)<<endl;
        }
    }
    return 0;
}

查询与修改代码类似,三步
1. 查询(修改)区间与当前区间无交集,直接返回
2. 当前区间完全被包含在查询(修改)区间内,对当前树节点(和懒标记)修改或直接返回当前树节点
3. 当前区间与查询(修改)区间有交集,下推懒标记后递归处理左右儿子。

双tag线段树

有两种操作,需要两个懒标记,需要定义优先级。注意两种操作对值的影响和先后顺序,并且做出修改。

#include<iostream>
using namespace std;
using ll=long long;
const int maxn=1e5+10;
ll a[maxn],tree[maxn<<2],add[maxn<<2],mul[maxn<<2],p;
void build(int node,int l,int r)
{
    add[node]=0,mul[node]=1;
    if(l==r)tree[node]=a[l];
    else{
        int mid=(l+r)>>1;
        build(node<<1,l,mid);
        build(node<<1|1,mid+1,r);
        tree[node]=(tree[node<<1]+tree[node<<1|1])%p;
    }
}
void push_down(int node,int len)
{
    tree[node<<1]=(tree[node<<1]*mul[node]+add[node]*(len-(len>>1)))%p;
    tree[node<<1|1]=(tree[node<<1|1]*mul[node]+add[node]*(len>>1))%p;
    mul[node<<1]=(mul[node<<1]*mul[node])%p;
    mul[node<<1|1]=(mul[node<<1|1]*mul[node])%p;
    add[node<<1]=(add[node<<1]*mul[node]+add[node])%p;
    add[node<<1|1]=(add[node<<1|1]*mul[node]+add[node])%p;
    mul[node]=1,add[node]=0;
}
void mulupdate(int node,int l,int r,int L,int R,int k)
{
    if(L>r||R<l)return;
    else if(L<=l&&R>=r){
        tree[node]=(tree[node]*k)%p;
        mul[node]=(mul[node]*k)%p;
        add[node]=(add[node]*k)%p;
    }
    else{
        int mid=(l+r)>>1;
        push_down(node,r-l+1);
        mulupdate(node<<1,l,mid,L,R,k);
        mulupdate(node<<1|1,mid+1,r,L,R,k);
        tree[node]=(tree[node<<1]+tree[node<<1|1])%p;
    }
}
void addupdate(int node,int l,int r,int L,int R,int k)
{
    if(L>r||R<l)return;
    else if(L<=l&&R>=r){
        add[node]=(add[node]+k)%p;
        tree[node]=(tree[node]+k*(r-l+1))%p;
    }
    else{
        int mid=(l+r)>>1;
        push_down(node,r-l+1);
        addupdate(node<<1,l,mid,L,R,k);
        addupdate(node<<1|1,mid+1,r,L,R,k);
        tree[node]=(tree[node<<1]+tree[node<<1|1])%p;
    }
}
ll query(int node,int l,int r,int L,int R)
{
    if(L>r||R<l)return 0;
    else if(L<=l&&R>=r){
        return tree[node];
    }
    else{
        int mid=(l+r)>>1;
        push_down(node,r-l+1);
        return (query(node<<1,l,mid,L,R)+query(node<<1|1,mid+1,r,L,R))%p;
    }
}
int main()
{
    ios::sync_with_stdio(false);
    int n,m;
    cin>>n>>m>>p;
    for(int i=1;i<=n;i++)cin>>a[i];
    build(1,1,n);
    int oper,x,y,k;
    for(int i=1;i<=m;i++)
    {
        cin>>oper>>x>>y;
        if(oper==1){
            cin>>k;
            mulupdate(1,1,n,x,y,k);
        }
        else if(oper==2){
            cin>>k;
            addupdate(1,1,n,x,y,k);
        }
        else{
            cout<<query(1,1,n,x,y)<<endl;
        }
    }
    return 0;
}

jls线段树

同时维护两个值,在修改时比较两个值,如果修改不会影响结果则直接退出,否则分类讨论修改区间和。
hdu5306(线段树+区间取最值)jls线段树线段树及其扩展

#include<iostream>
using namespace std;
const int maxn=1e6+10;
int a[maxn];
struct node{
    int l,r,sum,mx,se,c;
#define l(i) tree[i].l
#define r(i) tree[i].r
#define c(i) tree[i].c
#define mx(i) tree[i].mx
#define se(i) tree[i].se
#define sum(i) tree[i].sum
#define ls rt<<1
#define rs rt<<1|1
}tree[maxn<<2];
void push_up(int rt)
{
    sum(rt)=sum(ls)+sum(rs);
    mx(rt)=max(mx(ls),mx(rs));
    se(rt)=max(se(ls),se(rs));
    c(rt)=0;
    if(mx(ls)!=mx(rs))se(rt)=max(se(rt),min(mx(ls),mx(rs)));
    if(mx(rt)==mx(ls))c(rt)+=c(ls);
    if(mx(rt)==mx(rs))c(rt)+=c(rs);
}
void build(int rt,int l,int r)
{
    l(rt)=l,r(rt)=r;
    if(l==r){
        mx(rt)=sum(rt)=a[l],se(rt)=-1;
        c(rt)=1;
        return;
    }
    int mid=(l+r)>>1;
    build(ls,l,mid);
    build(rs,mid+1,r);
    push_up(rt);
}
void update(int rt,int k){
    if(k>=mx(rt))return;
    sum(rt)-=(mx(rt)-k)*c(rt);
    mx(rt)=k;
}
void push_down(int rt){
    update(ls,mx(rt)),update(rs,mx(rt));
}
void modify(int rt,int x,int y,int k)
{
    if(k>=mx(rt))return;
    if(l(rt)>=x&&r(rt)<=y&&k>se(rt)) {
        update(rt,k);
        return;
    }
    int mid=l(rt)+r(rt)>>1;
    push_down(rt);
    if(x<=mid)modify(ls,x,y,k);
    if(y>mid)modify(rs,x,y,k);
    push_up(rt);
}
int getmax(int rt,int x,int y)
{
    if(l(rt)>=x&&r(rt)<=y)return mx(rt);
    push_down(rt);
    int ans=0;
    int mid=l(rt)+r(rt)>>1;
    if(x<=mid)ans=max(ans,getmax(ls,x,y));
    if(y>mid)ans=max(ans,getmax(rs,x,y));
    return ans;
}
int getsum(int rt,int x,int y)
{
    if(l(rt)>=x&&r(rt)<=y)return sum(rt);
    push_down(rt);
    int ans=0;
    int mid=l(rt)+r(rt)>>1;
    if(x<=mid)ans+=getsum(ls,x,y);
    if(y>mid)ans+=getsum(rs,x,y);
    return ans;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,q;
        cin>>n>>q;
        for(int i=1;i<=n;i++)cin>>a[i];
        build(1,1,n);
        int op,x,y,z;
        while(q--){
            cin>>op>>x>>y;
            if(op==0)cin>>z,modify(1,x,y,z);
            else if(op==1)cout<<getmax(1,x,y)<<endl;
            else if(op==2)cout<<getsum(1,x,y)<<endl;
        }
    }
    return 0;
}

动态开点线段树

在需要用到左右儿子的时候再分配下标,在push_down(或update反正是修改时)中开点。

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1e5+10;
struct node{
    int s,lc,rc;
}tree[maxn<<2];
int tot=1,root=0;
void update(int &node,int l,int r,int x,int k)
{
    if(!node)node=++tot;
    if(l==r)tree[node].s+=k;
    else{
        int mid=(l+r)>>1;
        if(x<=mid)update(tree[node].lc,l,mid,x,k);
        else update(tree[node].rc,mid+1,r,x,k);
        tree[node].s=tree[tree[node].lc].s+tree[tree[node].rc].s;
    }
}
int query(int node,int l,int r,int L,int R)
{
    if(!node)return 0;
    else if(L==l&&R==r)return tree[node].s;
    else{
        int mid=(l+r)>>1;
        if(R<=mid) return query(tree[node].lc,l,mid,L,R);
        else if(L>mid) return query(tree[node].rc,mid+1,r,L,R);
        return query(tree[node].lc,l,mid,L,mid)+query(tree[node].rc,mid+1,r,mid+1,R);
    }
}
int main()
{
    int n;
    cin>>n;
    int ans=0;
    for(int i=1;i<=n;i++){
        int a;
        cin>>a;
        ans+= query(root,1,1e5,a+1,1e5);
        update(root,1,1e5,a,1);
    }
    cout<<ans<<endl;
    return 0;
}

由于不用build,而是在修改过程中建树,所以建的位置需要记录,所以update中传入了引用,为了在函数中改变值。

权值线段树

开桶保存每一个数出现的次数,用线段树去维护桶即为权值线段树。由于需要按值域去开数组,所以常常动态开点。可以 O(logv)v 为值域)地查询某个范围内的数出现的总次数。不仅如此,它还可以 O(logv) 地求得第 k 大的数。

int kth(int k, int p = 1, int cl = L, int cr = R) // 求指定排名的数
{
    if (cl == cr)
        return cl;
    int mid = (cl + cr - 1) / 2;
    if (val(ls(p)) >= k)
        return kth(k, ls(p), cl, mid); // 往左搜
    else
        return kth(k - val(ls(p)), rs(p), mid + 1, cr); // 往右搜
}

zkw线段树

非递归式线段树,把线段树开成满二叉树,从叶子结点往上处理,缩小传统线段树的常数与代码量。无法处理有运算优先级的问题,如双tag。

#include<iostream>
using namespace std;
using ll=long long;
const int maxn=1e5+10;
int n,m,N=1;
ll tree[maxn<<2],add[maxn<<2];
void build() {
    for(; N <= n+1; N <<= 1);
    for(int i=N+1;i<=N+n;i++)cin>>tree[i];
    for(int i=N-1;i>=1;i--) tree[i] = tree[i << 1] + tree[i << 1 | 1];
}
void update(int s, int t, int k) {
    int lNum=0, rNum=0, nNum=1;
    //lNum:  s一路走来已经包含了几个数
    //rNum:  t一路走来已经包含了几个数
    //nNum:  本层每个节点包含几个数
    for(s = N+s-1, t = N+t+1; s^t^1; s >>= 1, t >>= 1, nNum <<= 1) {
        //更新tree
        tree[s] += k*lNum;
        tree[t] += k*rNum;
        //处理add
        if(~s&1) {add[s^1] += k; tree[s^1] += k*nNum; lNum += nNum;}
        if(t&1) {add[t^1] += k; tree[t^1] += k*nNum; rNum += nNum;}
    }
    //更新上层tree
    for(; s; s >>= 1, t >>= 1) {
        tree[s] += k*lNum;
        tree[t] += k*rNum;
    }
}
ll query(int s, int t){
    ll lNum=0, rNum=0, nNum=1;
    ll ans=0;
    for(s = N+s-1, t = N+t+1; s^t^1; s >>= 1, t >>= 1, nNum <<= 1) {
        //根据标记更新
        if(add[s]) ans += add[s]*lNum;
        if(add[t]) ans += add[t]*rNum;
        //常规求和
        if(~s&1) {ans += tree[s^1]; lNum += nNum;}
        if(t&1) {ans += tree[t^1]; rNum += nNum;}
    }
    //处理上层标记
    for(; s; s >>= 1, t >>= 1) {
        ans += add[s]*lNum;
        ans += add[t]*rNum;
    }
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    build();
    int oper,x,y,k;
    for(int i=1;i<=m;i++){
        cin>>oper>>x>>y;
        if(oper==1){
            cin>>k;
            update(x,y,k);
        }
        else{
            cout<<query(x,y)<<endl;
        }
    }
    return 0;
}

主席树(可持久化权值线段树)

为了保存每一次的历史记录,每次修改实际上是新建了一棵线段树,并不对原树做任何修改。但为了合理的时空复杂度,可以发现每次修改只会改一部分结点,剩下的结点可以共用。因此可持久化只需要把修改改为动态开点,只新建需要修改的点。每次修改都会新增一个根节点,因此查询时需要选择查询哪个根节点。
在建立第一个版本的线段树时应当一次建好,之后再动态开点。
虽然我不喜欢用一堆宏,但是这里不用宏代码会显得逻辑不够清晰且啰嗦冗余,所以算了。

单点修改

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1e6+10;
int a[maxn],roots[maxn],n,m,cnt=1;
#define ls(x) tree[x].ls
#define rs(x) tree[x].rs
#define val(x) tree[x].val
#define mark(x) tree[x].mark;
struct node{
    int val,ls,rs;
}tree[20000000];
void build(int p=1,int l=1,int r=n)
{
    if(l==r)val(p)=a[l];
    else{
        ls(p)=++cnt,rs(p)=++cnt;
        int mid=(l+r)>>1;
        build(ls(p),l,mid);
        build(rs(p),mid+1,r);
        val(p)=val(ls(p))+val(rs(p));
    }
}
void update(int x,int k,int p,int q,int l=1,int r=n)
{
    if(l==r)val(q)=k;
    else{
        ls(q)=ls(p),rs(q)=rs(p);
        int mid=(l+r)>>1;
        if(x<=mid)
            ls(q)=++cnt,update(x,k,ls(p),ls(q),l,mid);
        else
            rs(q)=++cnt,update(x,k,rs(p),rs(q),mid+1,r);
        val(q)=val(ls(q))+val(rs(q));
    }
}
int query(int p,int L,int R,int l=1,int r=n)
{
    if(L>r||R<l)return 0;
    else if(L<=l&&R>=r)return val(p);
    else{
        int mid=(l+r)>>1;
        return query(ls(p),L,R,l,mid)+query(rs(p),L,R,mid+1,r);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    build();
    roots[0]=1;
    int v,oper,loc,k;
    for(int i=1;i<=m;i++)
    {
        cin>>v>>oper>>loc;
        if(oper==1){
            cin>>k;
            roots[i]=++cnt;
            update(loc,k,roots[v],roots[i]);
        }
        else{
            roots[i]=roots[v];
            cout<<query(roots[v],loc,loc)<<endl;
        }
    }
    return 0;
}

区间修改

使用标记永久化技术,即不再向下传递标记,而是查询时带着标记。

ll query(int l, int r, int p, int cl = 1, int cr = n, ll mk = 0) // 区间查询
{
    if (cl > r || cr < l)
        return 0;
    else if (cl >= l && cr <= r)
        return val(p) + mk * (cr - cl + 1); // 加上带的标记
    else
    {
        int mid = (cl + cr) / 2;
        return query(l, r, ls(p), cl, mid, mk + mark(p)) + query(l, r, rs(p), mid + 1, cr, mk + mark(p)); // 带着标记传递
    }
}
void update(int l, int r, int d, int p, int q, int cl = 1, int cr = n) // 区间修改
{
    ls(q) = ls(p), rs(q) = rs(p), mark(q) = mark(p); // 复制节点
    if (cl >= l && cr <= r)
    {
        if (cr > cl)
            mark(q) += d;
    }
    else
    {
        int mid = (cl + cr) / 2;
        if (cl <= r && mid >= l) // 提前进行判断,以免新建不必要的节点
            ls(q) = ++cnt, update(l, r, d, ls(p), ls(q), cl, mid);
        if (mid + 1 <= r && cr >= l)
            rs(q) = ++cnt, update(l, r, d, rs(p), rs(q), mid + 1, cr);
    }
    val(q) = val(p) + (min(cr, r) - max(cl, l) + 1) * d; // 根据需要更新的区间长度计算当前节点的值
}

求静态区间第k小数

摘自算法学习笔记(50): 可持久化线段树 - 知乎
先建立一棵全0的树(因为要可持久化所以不能动态开点):

void build(int l = 1, int r = n, int p = 1) // 建树
{
    val(p) = 0;
    if (l != r)
    {
        ls(p) = ++cnt, rs(p) = ++cnt;
        int mid = (l + r) / 2;
        build(l, mid, ls(p));
        build(mid + 1, r, rs(p));
    }
}

把原数组离散化:

int C[MAXN], L[MAXN], ori[MAXN];
void discretize(int A[], int n)
{
    memcpy(C, A, sizeof(int) * n);     // 复制
    sort(C, C + n);                    // 排序
    int l = unique(C, C + n) - C;      // 去重
    for (int i = 0; i < n; ++i)
    {
        L[i] = lower_bound(C, C + l, A[i]) - C + 1; // 查找
        ori[L[i]] = A[i]; // 保存离散化后的数对应的原数
    }
}

然后按原区间中的顺序,把离散化后的数据一个一个地插入可持久化的权值线段树:

for (int i = 0; i < n; ++i)
{
    roots[i + 1] = ++cnt;
    update(L[i], 1, roots[i], roots[i + 1]);
}

重点来了:我们已经有了求[1, r]内第k小数的方法(查询相应历史版本即可),而求[l, r]内第k小数,只需对kth函数稍作修改。注意,我们在求kth时会用到当前左儿子对应的区间和,现在要排除[1, l-1],那么把这部分和减去即可。

int kth(int k, int p, int q, int cl = 1, int cr = n) // 求指定排名的数
{
    if (cl == cr)
        return ori[cl];
    int mid = (cl + cr) / 2;
    if (val(ls(q)) - val(ls(p)) >= k)
        return kth(k, ls(p), ls(q), cl, mid); // 往左搜
    else
        return kth(k - (val(ls(q)) - val(ls(p))), rs(p), rs(q), mid + 1, cr); // 往右搜
}
// 在main函数中
printf("%d\n", kth(k, roots[l - 1], roots[r]));

李超线段树

一种用于维护平面直角坐标系内线段关系的数据结构。(也许计算几何能用?某年icpc出到了可以用这个做)

基本应用

线段树染色问题

-1表示染了多种颜色,0表示未染色,其它数字表示颜色种类。
似乎只要用父节点和懒标记的值区间覆盖就行了。
修改时要考虑下递归之后的回溯,对于两个子区间的颜色是什么情况来更新父区间的颜色情况。
查询时对于一个区间内颜色的情况,未染色直接返回,染了多种颜色则递归查。跨区间的也递归查。

扫描线

经典应用,解决平面矩形覆盖的面积和问题。(也能够扩展到空间和其它图形)。
思想是水平或竖直方向扫描,以下以水平方向扫描为例,也就是矩形的竖边作为扫描线。从左往右扫,将整个图形分成若干个小矩形相加(如果上下两个矩形分开,视为合并在一起的就好)。那么,扫过的距离就是小矩形的宽,只有长在不断变化。使用线段树维护扫过区间内被覆盖的次数和长度,然后相乘即可。
具体思路如下:首先按照边来读入,对左边的边标记为1,右边的标记为-1,然后离散化,使用二分来查找对应的边。建立线段树,其中的每一个点表示一条线段,维护该线段的长度len与被多少个矩形覆盖的cnt。按照每一条边去更新线段树,每更新一条边在答案上累加。(扫描线)最后输出答案即可。

#include <cstdio>
#include <algorithm>
using namespace std;
#define p1 (p<<1)
#define p2 (p<<1|1)
const int N=1e5+10;
struct T {
    int l,r,cnt;
    double len;
} t[N*8];
struct A {
    double x,y1,y2;
    int add;
} a[N*2];
int n,len;
double lsh[N*2];
bool cmp(A u,A v) {return u.x<v.x;}
int val(double x) {return lower_bound(lsh+1,lsh+1+len,x)-lsh;}
double raw(int x) {return lsh[x];}
void pushUp(int p) {t[p].len=(t[p].cnt>0)?raw(t[p].r+1)-raw(t[p].l):t[p1].len+t[p2].len;}
void build(int p,int l,int r) {
    t[p]={l,r,0,0};
    if(l==r) return;
    int mid=(l+r)>>1;
    build(p1,l,mid),build(p2,mid+1,r);
}
void upd(int p,int l,int r,int add) {
    if(t[p].l>=l && t[p].r<=r) {t[p].cnt+=add,pushUp(p); return;}
    int mid=(t[p].l+t[p].r)>>1;
    if(l<=mid) upd(p1,l,r,add);
    if(r>mid) upd(p2,l,r,add);
    pushUp(p);
}
int main()
{
    for(int tim=1;;tim++) {
        scanf("%d",&n);
        if(!n) break;
        printf("Test case #%d\n",tim);
        for(int i=1;i<=n;i++) {
            double x1,y1,x2,y2;
            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
            a[i]={x1,y1,y2,1},a[i+n]={x2,y1,y2,-1};
            lsh[i]=y1,lsh[i+n]=y2;
        }
        n*=2;
        sort(a+1,a+1+n,cmp),sort(lsh+1,lsh+1+n);
        len=unique(lsh+1,lsh+1+n)-lsh-1;
        build(1,1,len-1);
        double ans=0;
        upd(1,val(a[1].y1),val(a[1].y2)-1,a[1].add);
        for(int i=2;i<=n;i++) {
            ans+=t[1].len*(a[i].x-a[i-1].x);
            upd(1,val(a[i].y1),val(a[i].y2)-1,a[i].add);
        }
        printf("Total explored area: %.2lf\n\n",ans);
    }
    return 0;
}

夢に僕らで帆を張って 来るべき日のために夜を越え。