线段树

绝地灬酷狼 2024-04-17 20:17 13阅读 0赞

### 线段树 ###

*  线段树
 *  区间修改(加)+ 区间查询
 *  区间修改(加+乘）+区间查询
 *  静态区间第K小
 *  参考博客

# 线段树 #

线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。  
使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间复杂度为O(logN)。而未优化的空间复杂度为2N，实际应用时一般还要开4N的数组以免越界，因此有时需要离散化让空间压缩。

# 区间修改(加)+ 区间查询 #

#include<cstdio>
    const int MAXN=1e5+5;
    typedef long long ll;
    
    /* * 利用线段树的完成下面操作： * 1.区间修改 * 2.区间查询 */
    
    
    ll n,m,a[MAXN],ans[MAXN<<2],tag[MAXN<<2];
    /* a:读入的原数组 ans：构造的线段树 tag:懒标记 使区间更新的复杂度就达到O(logn) 标记的含义：本区间已经被更新过了，但是子区间却没有被更新过， 被更新的信息是什么（区间求和只用记录有没有被访问过，而区间加减乘除等多种操作的问题则要记录进行的是哪一种操作） 相对标记指的是可以共存的标记，且打标记的顺序与答案无关，即标记可以叠加。 比如说给一段区间中的所有数字都+a， 我们就可以把标记叠加一下，比如上一次打了一个+1的标记，这一次要给这一段区间+2，那么就把+1的标记变成+3。 绝对标记是指不可以共存的标记，每一次都要先把标记下传，再给当前节点打上新的标记。这些标记不能改变次序， 否则会出错。 比如说给一段区间的数字重新赋值，或是给一段区间进行多种操作。 */ 
    
    
    inline ll ls(ll x)
    { 
        return x<<1;
    }//寻找左孩子(2*x)
    
    inline ll rs(ll x)
    { 
        return x<<1|1;//位运算的效率高
    }//寻找右孩子(2*x+1)
    
    
    inline void push_up(ll p)
    { 
        ans[p]=ans[ls(p)]+ans[rs(p)];
    }//维护父子节点之间的逻辑关系
    // ans[p]=max(ans[ls(p)],ans[rs(p))维护区间最大值
    // ans[p]=min(ans[ls(p)],ans[rs(p))维护区间最小值
    
    void build(ll p,ll l,ll r)
    { 
        // p当前节点的编号
        //l,r 当前区间的左边界，右边界
        tag[p]=0;
        if(l==r){ ans[p]=a[l];return ;}//叶子结点
        ll mid=(l+r)>>1;//区间分半
        build(ls(p),l,mid);
        build(rs(p),mid+1,r);
        push_up(p);//递归实际意义是先向底层递归，然后从底层向上回溯
        //先去整合子节点的信息，再向它们的祖先回溯整合之后的信息
    } //建树
    
    inline void f(ll p,ll l,ll r,ll k)
    { 
        tag[p]=tag[p]+k;
        ans[p]=ans[p]+k*(r-l+1);
        //由于是这个区间统一改变，所以ans数组要加元素个数次啦 
    }//f函数的唯一目的，就是记录当前节点所代表的区间 
    
    inline void push_down(ll p,ll l,ll r)
    { 
        ll mid=(l+r)>>1;
        f(ls(p),l,mid,tag[p]);
        f(rs(p),mid+1,r,tag[p]);
        tag[p]=0;
        //每次更新两个儿子节点。以此不断向下传递 
    }
    
    inline void update(ll nl,ll nr,ll l,ll r,ll p,ll k)
    { 
        //nl,nr为要修改的区间[nl,nr]
        //l,r,p为当前节点所存储的区间[l,r]以及节点的编号 p
        //k 区间[nl,nr]增加k
        if(nl<=l&&r<=nr)
        { 
            ans[p]+=k*(r-l+1);
            tag[p]+=k;
            //懒惰标记叠加
            return ;
        }
        push_down(p,l,r);
        //回溯之前（也可以说是下一次递归之前，因为没有递归就没有回溯） 
        //由于是在回溯之前不断向下传递，所以自然每个节点都可以更新到 
        ll mid=(l+r)>>1;
        if(nl<=mid)update(nl,nr,l,mid,ls(p),k);
        if(nr>mid) update(nl,nr,mid+1,r,rs(p),k);
        push_up(p);
    }
    
    ll query(ll ql,ll qr,ll l,ll r,ll p)
    { 
        //查询区间[ql,qr]的区间和
        ll res=0;
        if(ql<=l&&r<=qr)return ans[p];
        ll mid=(l+r)>>1;
        push_down(p,l,r);
        if(ql<=mid)res+=query(ql,qr,l,mid,ls(p));
        if(qr>mid) res+=query(ql,qr,mid+1,r,rs(p));
        return res;
    }
    
    int main()
    { 
        ll op,l,r,d;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;++i)scanf("%lld",a+i);
        build(1,1,n);
        while(m--)
        { 
            scanf("%lld%lld%lld",&op,&l,&r);
            if(op==1){ 
                scanf("%lld",&d);
                update(l,r,1,n,1,d);//修改区间[l,r] ,区间内的数相加d
            }else  printf("%lld\n",query(l,r,1,n,1));//查询区间[l,r]的和
        }
        return 0;
    }

# 区间修改(加+乘）+区间查询 #

#include<cstdio>
    const int maxn=1e5+5;
    typedef long long ll;
    
    /* * 利用线段树完成区间修改(加+乘）+区间查询 1.将某区间[x,y]每一个数乘上k 2.将某区间[x,y]每一个数加上k 3.求出某区间[x,y]每一个数的和 */
    
    ll a[maxn],tree[maxn*4],mul[maxn*4],add[maxn*4],n,m,mod;
    //a:读入的原始数据
    //tree:线段树节点值
    //mul:乘法懒标记
    //add：加法懒标记
    //为了区分两种标记,add初始为0（加0不影响原来的值），mul初始化为1（乘以1不影响原来的值）
    
    inline void maintain(ll p){ 
        tree[p]=(tree[p<<1]+tree[p<<1|1])%mod;
    }//维护父子节点之间的逻辑关系
    
    void build(ll p,ll l,ll r){ 
        mul[p]=1;
        add[p]=0;
        if (l==r){ 
            tree[p]=a[l];
            return ;
        }
        ll mid=(l+r)>>1;//区间分解
        build(p<<1,l,mid);
        build(p<<1|1,mid+1,r);
        //注意p<<1|1 等价于p*2+1,或(p<<1)+1，<<的优先级低，位运算的效率高
        maintain(p);
    }//建树
    
    void ADD(ll p,ll l,ll r,ll mulk,ll sumk){ 
        tree[p]=(tree[p]*mulk+(r-l+1)*sumk)%mod;//修改节点
        add[p]=(add[p]*mulk+sumk)%mod;
        mul[p]=(mul[p]*mulk)%mod;
        //更新懒标记
        return ;
    }//执行区间修改的时候节点
    
    void pushdown(ll p,ll l,ll r){ 
        ll mid=(l+r)>>1;
        ADD(p<<1,l,mid,mul[p],add[p]);
        ADD(p<<1|1,mid+1,r,mul[p],add[p]);
        add[p]=0;
        mul[p]=1;
        return ;
    }//每次更新两个儿子节点。以此不断向下传递 
    
    void changemul(ll p,ll l,ll r,ll x,ll y,ll v){ 
        if (x<=l&&r<=y){ 
            ADD(p,l,r,v,0);
            return ;
        }
        pushdown(p,l,r);
        ll mid=(l+r)>>1;
        if (x<=mid) changemul(p<<1,l,mid,x,y,v);//我不是注释：看是否还有包含的交集，下同理
        if (mid<y) changemul(p<<1|1,mid+1,r,x,y,v);
        maintain(p);
    }
    
    void changesum(ll p,ll l,ll r,ll x,ll y,ll v){ 
        //区间修改,在[x,y]每个数加上v
        //当前区间[l,r],根节点p
        if (x<=l&&r<=y){ 
            ADD(p,l,r,1,v);
            return ;
        }//[l,r]属于[x,y]
        pushdown(p,l,r);//往下递归
        ll mid=(l+r)>>1;
        if (x<=mid) changesum(p<<1,l,mid,x,y,v);
        if (mid<y) changesum(p<<1|1,mid+1,r,x,y,v);
        maintain(p);
    }
    
    ll query(ll p,ll l,ll r,ll x,ll y){ 
        //求解区间[x,y]的值
        //当前区间[l,r],根节点p
        if (x<=l&&r<=y) return tree[p] ;//[l,r]属于[x,y]
        pushdown(p,l,r);//往下递归
        ll mid=(l+r)>>1,res=0;
        if (x<=mid) res+=query(p<<1,l,mid,x,y);
        if (mid<y) res+=query(p<<1|1,mid+1,r,x,y);
        return res%mod;
    }//区间询问
    
    int main(){ 
        scanf("%lld%lld%lld",&n,&m,&mod);
        for (ll i=1;i<=n;i++)scanf("%lld",&a[i]);
        build(1,1,n);
        ll op,x,y,k;
        for (ll i=1;i<=m;i++){ 
            scanf("%lld%lld%lld",&op,&x,&y);
            if (op==1){ 
                scanf("%lld",&k);
                changemul(1,1,n,x,y,k);
            }else if (op==2){ 
                scanf("%lld",&k);
                changesum(1,1,n,x,y,k);
            }else if (op==3)printf("%lld\n",query(1,1,n,x,y));
        }
        return 0;
    }

# 静态区间第K小 #

#include <cstdio>
    #include<algorithm>
    const int maxn = 2e5+5;
    
    /* * 利用可持久化线段树（主席树）静态查询区间第k小 * 主席树是利用函数式的编程思想使得线段树支持查询历史版本， * 同时充分利用他们之间的共同数据来减少时间和内存消耗的数据结构 * 主席树的每个节点保存的是一颗线段树，维护的区间信息， * 结构相同，因此具有可加减性 * 静态主席树的一些特点： 1.建树时首先需要建一棵空的线段树，即最原始的主席树， 此时主席树只含有一个空的节点，之后依次对原序列按某种顺序更新， 就是将原序列加入到相应的位置 2.主席树是一种特殊的线段树集，它包含了所有线段树的优势， 并且可以保存历史状态，主席树查找和更新的时空复杂度都为O(nlogn) 且总空间复杂度为O(nlogn+nlogn)前者为空树的复杂度， 后者为更新n次的空间复杂度，缺点是空间损耗巨大 3.主席树可以处理区间[L,R]中介于[x,y]的值的问题 4.若增加空间垃圾回收则可以使空间复杂度降低一个log */
    
    int node_cnt, n, m;
    // node_cnt 记录节点的个数
    int sum[maxn<<5], rt[maxn], lc[maxn<<5], rc[maxn<<5];//线段树相关
    int a[maxn], b[maxn];//原序列和离散化序列
    int p;//修改点
    
    void build(int &t, int l, int r)
    { 
        t = ++node_cnt;
        if(l == r) return;
        int mid = (l + r) >> 1;
        build(lc[t], l, mid);
        build(rc[t], mid+1, r);
    }//建一个全0的线段树，称作基础主席树；
    
    int update(int o, int l, int r)
    { 
        //节点o表示区间[l,r]，修改点为p，
        int oo = ++node_cnt;
        lc[oo] = lc[o]; rc[oo] = rc[o]; sum[oo] = sum[o] + 1;
        if(l == r) return oo;
        int mid = (l + r) >> 1;
        if(p <= mid) lc[oo] = update(lc[oo], l, mid);
        else rc[oo] = update(rc[oo], mid+1, r);
        return oo;
    }
    
    int query(int u, int v, int l, int r, int k)
    { 
        // 查询线段树[u,v]区间的第k大
        int ans, mid = ((l + r) >> 1), x = sum[lc[v]] - sum[lc[u]];
        if(l == r) return l;
        if(x >= k) ans = query(lc[u], lc[v], l, mid, k);
        else ans = query(rc[u], rc[v], mid+1, r, k-x);
        return ans;
    }
    
    int main()
    { 
        int l, r, k, q, ans;
        scanf("%d%d", &n, &m);
        for(int i = 1; i <= n; ++i)scanf("%d", &a[i]), b[i] = a[i];
        std::sort(b+1, b+n+1);
        q = std::unique(b+1, b+n+1) - b - 1;//去重，离散化
        build(rt[0], 1, q);
        for( int i = 1; i <= n; ++i){ 
            p = std::lower_bound(b+1, b+q+1, a[i])-b;//可以视为查找最小下标的匹配值，核心算法是二分查找
            rt[i] = update(rt[i-1], 1, q);
        }
        while(m--){ 
            scanf("%d%d%d", &l, &r, &k);
            ans = query(rt[l-1], rt[r], 1, q, k);
            printf("%d\n", b[ans]);
        }
        return 0;
    }
    //动态主席树就是在静态主席树基础上增加了一批用树状数组维护的线段树
    //利用差分完成

# 参考博客 #

[P3372 【模板】线段树 1 题解][P3372 _ 1]  
[P3373 【模板】线段树 2][P3373 _ 2]  
[P3834 【模板】可持久化线段树 1（主席树） 题解][P3834 _ 1_]  
[线段树详解][Link 1]  
[线段树的原理与模板][Link 2]  
[线段树详解 （原理，实现与应用）][Link 3]  
[poj 2104 K-th Number 主席树+超级详细解释][poj 2104 K-th Number]

[P3372 _ 1]: https://www.luogu.org/problemnew/solution/P3372
[P3373 _ 2]: https://www.luogu.org/problemnew/solution/P3373
[P3834 _ 1_]: https://www.luogu.org/problemnew/solution/P3834
[Link 1]: https://blog.csdn.net/huangzihaoal/article/details/81813454
[Link 2]: https://blog.csdn.net/iwts_24/article/details/81484561
[Link 3]: https://blog.csdn.net/zearot/article/details/48299459
[poj 2104 K-th Number]: https://blog.csdn.net/woshinannan741/article/details/53012682