精华内容
下载资源
问答
  • 【集训队作业2018】三角形【线段树合并+思路详解
    2019-03-03 14:45:13

    题目链接

    【题面】

    Snuke 有一棵 nn 个点的有根树,每个点有权值 wiwi,初始每个结点上都没有石子。

    Snuke 准备了一些石子,并把它们拿在手中。她可以进行以下两种操作任意多次:

    1. 从手中取 wiwi 个石子放在结点 ii 上,进行该操作要求结点 ii 的所有孩子 jj 上都有 wjwj 个石子。
    2. 将结点 ii 上的所有石子收回手中。

    Takahashi 想知道对于每个 ii,为了在结点 ii 上放 wiwi 个石子,Snuke 至少需要准备多少石子。

    输入格式

    从标准输入读入数据。

    第一行一个数字 TT 表示这个子任务的编号。

    第二行一个正整数 nn 。(n≤2×105)(n≤2×105)

    第三行 n−1n−1 个正整数,第 i−1i−1 个数 pipi 表示 ii 的父亲。(pi<i)(pi<i)

    第四行 nn 个正整数,第 ii 个数为 wiwi 。

    输出格式

    输出到标准输出。

    输出一行 nn 个正整数,第 ii 个数为结点 ii 的答案。


    我写的比较烂吧,理解的不是很深了,基本是基于大佬代码的理解来写的。

    这篇博客写的可以,没读懂一号

    这篇文章写的也很好,但是更加大佬,我又不大懂,只能基于其来做理解

      这道题,并没用去使用很多博主的用堆去维护状态的想法,直接上线段树上的合并来解这道题(说实话,自己单独是没有那个能力来完成这道题的,然后跟着博客以及已经过的代码去理解,再写出来的自己的code)

      首先讲一下吧,关于这道题的为什么会去使用线段树合并的想法(本来压根儿想不到这块的,就是因为其他博主都这么写,所以想到了),我们可以看到,一共有两种操作,一个是放Wi个石子到该点,另一个是去取Wi个石子下来放回手上,然后我们所要知道的就是每个节点所需要的最少的石头数,使得该节点能被放上石头。

      然后,我们可以看到,每个点,都要先得到所有的子节点上都放上石头之后,再加上该节点的石子,就有可能是该节点的所需石子数,但是可能会偏小,因为你不能这么确定出每个子节点的最大需要是否会满足这个条件,所以,我们必须从子节点开始,从叶子节点往上去寻找最适合的答案,那么又该怎么解?

      从叶子节点向上去,我们去求叶子节点所需要的石子数就是其自己的石子数,然后往上一层,就是所有旗下的叶子节点加上该点的权重(石子数),但是岂不是可以看成,叶子节点之上的每一层都存在一个最大的前缀和最小的后缀,是这样来的:对于这个节点,我们要考虑它的操作,就是要考虑到选取它的时候,我们要对于它的所有子节点都进行一个判断,因为对于目前节点,譬如这样(自己画的图,有点点丑):

    (好像这幅图还横过来了……将就看啦)

      (举例来说)我们可以知道,要是要让权值是6的节点拿满是需要5+4+6的数目的石子数,但是到了6周之后,可以舍去这些石子了,所以此时的最大需求石子数是15,但是现在放下去的石子数是6,所以可以保存住这些数据(15, 6);接下来再看,权值为10的节点,我们要拿它,就是需要(15, 10)这样子的节点;再看9权值的这个节点,我们要单纯的只拿它,岂不是要(10, 9)。再往上,就是权值为3的最顶的那个节点,它所需要的情况又是怎样的呢?6+10+9+max(5+4, 3+2, 1, 0, 3) = 28(前面的几个(9, 5, 1, 0)去取大,然后跟3去取小的),其中这个最后的0特有深意,就是为了一定要变成升权的,(但是现在体现的不明显,我们往下推,就知道了),但是这样做的确是不好推,因为其中的5+4、3+2、1都是没有继承下来的,所以,该怎么办?不妨这样,我们先不要去加上该节点的权值,等到需要得到ans的时候再加上自己的权值,就是这么说原来的6、10、9号节点会变成(9, 6)、(5, 10)、(1, 9)这样子的类型,那么不就是可以知道前面的最大需求了吗。

      其实,还需要一点的优化,但是基本已经成型了,我们可以知道这点,一共最多2e5个点,以及最大1e9的权值,所以最大最大的需求也不过2e14。——此为前提O(log2e14)是可行的。

      那么,为了让每个节点都能从其子节点的状态开始往上推,我们应该处理一些什么,我们把每个节点看成一个处理前缀和后缀的过程,那么维护的是什么呢?我们可以去考虑维护一个前缀最大值和一个后缀最小值,这是为什么呢?为什么这么维护呢?前缀最大值维护的是答案,就是每个节点的最少需要的除去自己上面的所需的石子数,而后缀最小值呢,维护的又是什么呢?

      现在这么考虑,维护一个前缀最大值(maxx)和一个后缀最小值(minn),其中为了使得到达每个点都能用最大前缀来表示它的答案,我们得做一些想法,譬如说,我们把两个子节点合并起来,来看到权值为6的这号节点就有两个子节点5号和4号,我们就会有对应的需要继承,譬如说,权值为5号节点的向上推的(maxx, minn)的值为(0, -5),之所以为什么是这个值呢,最大的前缀去除自己的权值为0,再看看其他的点,我们从小往上去访问,得到的是这样的:

    我们从下往上,以权值为目的来解:

    (5)、(0, -5)

    (4)、(0, -4)

    (3)、(,0 -3)

    (2)、(0, -2)

    (1)、(0, -1)

    (6)、(9, -15)

    (10)、(5, -15)

    (9)、(1, -10)

    (3)、(25, -28)

    这些都是向上递推时候,放进去的状态,而一开始我们应该怎么去假设状态呢?

    不妨令其为(0, -w[u]),这样子就可以在最后的时候在加入+w[u]了。

    那么答案就是:这个点时候的maxx  + w[u]。


    另外大佬一号

    考虑每个操作,如果把操作按先后顺序放到序列上的话,操作一就是把wiwi的石子放到某个节点,那么就是在序列末端加入wiwi,然后根据贪心肯定要把它所有儿子的石子拿走,也就是要减去∑wson∑wson

    那么每个点的答案就是序列的最大前缀

    因为父亲节点的操作一要在儿子之后进行,很麻烦,那么可以每次在自己这里把wiwi减掉,到父亲的时候再加回去

    记(x,y)(x,y)为一个二元组,xx表示当前位置的最大前缀和,yy表示最小后缀和,然后定义一个运算(ax,by)=(x+max(0,a+y),b+min(0,a+y)(ax,by)=(x+max(0,a+y),b+min(0,a+y),大概能看出是个什么东西,注意这个运算不满足交换律

    然后考虑一下这些二元组在序列中的顺序,如果x+y<0x+y<0,那么肯定得放前面,因为可以让之后的前缀和减小。

    那么当x+y<0x+y<0时,按xx排序,这样能使前缀和不断减小。如果x+y>0x+y>0,按yy排序就好了

    维护二元组的话,用线段树合并,如果当前二元组的x+y<0x+y<0且有比它最大前缀大的二元组,那么就已经是最优的了否则将在它前面的二元组与它合并,合并完后加进线段树里就好了。注意合并完之后节点没了要记得清空。


    大佬二号

    先理解操作的意义。我们把所有的操作以先后顺序放在一个序列上,然后开始想两个操作对于这个序列的修改。

    操作一是把wiwi的石子放在某个节点,在序列上的表现则是在当前序列的末端加入wiwi。

    而当我们做完操作一,肯定是贪心地将这个节点的儿子们的石子全拿回来。在序列上的表现就是减去∑w[son]∑w[son]。

    而我们要求的就是序列上的最大前缀。

    但这个东西并不好搞。为什么呢?因为对于一个操作一而言,必须在它的儿子们操作一之后执行。这个限制看起来不好消除,但其实也很办。

    我们知道两个操作是连续的。所以可以把+wi−∑w[son]+wi−∑w[son]改成+∑w[son]−wi+∑w[son]−wi。

    定义一个二元组(x,y)(x,y),xx表示为当前位置在序列的最大前缀,&y&表示为当前位置在序列的最小后缀。

    考虑如何定义这个二元组的运算符。假设有二元组A(x,y)A(x,y)。把两个二元组合并为C(xX,yY)C(xX,yY),其中xX=x+max(0,X+y)xX=x+max(0,X+y),yY=y+min(0,X+y)yY=y+min(0,X+y)。这个东西可以感性理解一下,感觉也不用解释。

    然后我们考虑一下这些二元组应当以什么样的顺序放在序列里。很明显的一个结论,若A(x,y)A(x,y)中,x+y<0x+y<0,则应当放在前面。然后就可以分两类考虑了。

    对于x+y<0x+y<0的情况。显然的应该以xx从小到大排序。这样最大前缀一定越小。同理,另一种情况就是按yy排序就好了。

    那接下来只用考虑如何维护这些二元组就行了。网上有篇题解的做法是先将序列构造出来,再用线段树合并。其实没必要这样,直接线段树合并就好了。

    考虑每次如何合并二元组。如果当前二元组x+y<0x+y<0而且有比它的最大前缀还大最大前缀,那么当前一定是最优的,所以放在前面就好了。否则每次将在它前面的二元组与它合并就好了。合并完后再添加进线段树即可。

    这里稍微注意一下合并,合并完后,那个被合并的二元组就没了(因为已经是最优的了),那么就要在线段树上把当前的节点删掉,不然下次合并二元组的时候就会再次调用这个已经被用过的二元组了。

    每次的答案就是最大前缀。


    他们都好强啊……QAQ……%%%


    #include <iostream>
    #include <cstdio>
    #include <cmath>
    #include <string>
    #include <cstring>
    #include <algorithm>
    #include <limits>
    #include <vector>
    #include <stack>
    #include <queue>
    #include <set>
    #include <map>
    #define lowbit(x) ( x&(-x) )
    #define pi 3.141592653589793
    #define e 2.718281828459045
    #define INF 0x3f3f3f3f
    #define HalF (l + r)>>1
    #define lsn rt<<1
    #define rsn rt<<1|1
    #define Lson lsn, l, mid
    #define Rson rsn, mid+1, r
    #define QL Lson, ql, qr
    #define QR Rson, ql, qr
    #define myself rt, l, r
    using namespace std;
    typedef unsigned long long ull;
    typedef long long ll;
    const int maxN = 2e5 + 7;
    const ll _UP = 2e14;
    int N, fa[maxN], w[maxN], head[maxN], cnt, root[maxN], tot, lc[maxN*100], rc[maxN*100];
    ll ans[maxN];
    struct Eddge
    {
        int next, to;
        Eddge(int a=-1, int b=0):next(a), to(b) {}
    }edge[maxN<<1];
    inline void addEddge(int u, int v)
    {
        edge[cnt] = Eddge(head[u], v);
        head[u] = cnt++;
    }
    struct node     //将每个操作都看成一个序列
    {
        ll maxx, minn;  //最大前缀、最小后缀
        node(ll a=0, ll b=0):maxx(a), minn(b) {}    //合并操作就是将点连立的时候,{最大前缀1+max(0,最小后缀1+最大前缀2),最小后缀1+min(0,最大前缀2+最小后缀1)},其中max中的0是为了最大前缀一定是上升的,min中的0是为了最小后缀是一定会下降的
        friend node operator + (node e1, node e2) { return node(e1.maxx + max(0ll, e1.minn + e2.maxx), e2.minn + min(0ll, e1.minn + e2.maxx)); }    //合并操作,将子节点合并上去
    }tr[maxN*100];
    void insert(int &rt, ll l, ll r, node x)    //建立新树节点操作,是一串操作序列的形式
    {
        if(!rt) rt = ++tot;
        if(l == r) { tr[rt] = tr[rt] + x;   return; }
        ll mid = HalF;
        if(x.maxx <= mid) insert(lc[rt], l, mid, x);
        else insert(rc[rt], mid + 1, r, x);
        tr[rt] = tr[lc[rt]] + tr[rc[rt]];
    }
    void Merge(int p1, int p2, ll l, ll r)
    {
        if(l == r) { tr[p1] = tr[p1] + tr[p2]; return; }
        ll mid = HalF;
        if(lc[p1] && lc[p2]) Merge(lc[p1], lc[p2], l, mid);
        else if(lc[p2]) lc[p1] = lc[p2];
        if(rc[p1] && rc[p2]) Merge(rc[p1], rc[p2], mid + 1, r);
        else if(rc[p2]) rc[p1] = rc[p2];
        tr[p1] = tr[lc[p1]] + tr[rc[p1]];
    }
    void update(int &rt, ll l, ll r, node &x, bool &flag)   //更新根节点
    {
        if(!rt || flag) return;
        if(l == r)
        {
            if(x.maxx + x.minn < 0 && x.maxx < l) { flag = true; return; }  //这个解更优
            x = x + tr[rt];
            rt = 0;
            return;
        }
        ll mid = HalF;
        update(lc[rt], l, mid, x, flag);
        update(rc[rt], mid + 1, r, x, flag);
        if(lc[rt] || rc[rt]) tr[rt] = tr[lc[rt]] + tr[rc[rt]];
        else rt = 0;
    }
    void dfs(int u)
    {
        node res = node(0, -w[u]);  //初始的情况
        if(!root[u]) root[u] = ++tot;
        for(int i=head[u], v; ~i; i=edge[i].next)
        {
            v = edge[i].to;
            res.maxx += w[v];   //最大值一定是会加上所有的子节点的
            dfs(v);
            Merge(root[u], root[v], 0, _UP);    //把子节点的情况都推上父节点,父节点去查询最大的前缀
        }
        node tmp = res; bool flag = false;
        tmp.maxx += w[u];   //要给最大前缀加上该点的权重,因为要拿这个点,不止需要的是子节点的还需要目前节点的权重
        ans[u] = (tmp + tr[root[u]]).maxx;  //此时得到的就是ans的值了,此时也是要用到合并的,因为子节点的后缀是可以再来利用的
        update(root[u], 0, _UP, res, flag); //去更新目前的根节点,因为已经选取过了,所以要更新它
        insert(root[u], 0, _UP, res);
    }
    inline void init()
    {
        cnt = tot = 0;
        memset(head, -1, sizeof(head));
    }
    int main()
    {
        int T;  scanf("%d", &T);
        scanf("%d", &N);
        init();
        for(int i=2; i<=N; i++)
        {
            scanf("%d", &fa[i]);
            addEddge(fa[i], i);
        }
        for(int i=1; i<=N; i++) scanf("%d", &w[i]);
        dfs(1);
        for(int i=1; i<=N; i++) printf("%lld%c", ans[i], i == N ? '\n' : ' '); 
        return 0;
    }
    

     

    更多相关内容
  • 数据结构专题 - 线段树合并的学习笔记。

    数据结构专题-学习笔记:线段树合并

    一些 Update

    Update 2021/12/16:修改了一下垃圾回收部分的描述,改为更一般的描述空间回收并且加了一些解释说明。

    1. 前言

    线段树合并,是一种听起来高大上实际上难度并不大的算法,专门用于一些 DS 题目,可以在一定的复杂度内合并两棵线段树,这过程中有时会用启发式合并。

    当然,如果你学过任何一种需要合并的数据结构(如 FHQ Treap),那么学习线段树合并将会非常简单。

    前置知识:动态开点线段树,树上差分。

    2. 详解

    先上例题:P4556 [Vani有约会]雨天的尾巴

    题意简述:给出 n n n 点连通树, q q q 次操作,每次操作对 x → y x \to y xy 路径上所有点加入一个大小为 z z z 的数,问加完后每个点上哪个大小的数最多, n , q ≤ 1 0 5 , z ≤ 1 0 5 n,q \leq 10^5,z \leq 10^5 n,q105,z105

    这道题首先有个最直接的方式就是暴力跑所有路径,然后每个点开一个值域线段树存一下,每个点维护两个值 M a x n , a n s Maxn,ans Maxn,ans 表示最大数的个数以及这个数,最后每个点查一下就好了,复杂度 O ( q n log ⁡ n ) O(qn \log n) O(qnlogn),这个做法总应该会的吧qwq,不会好好想想()

    发现这样只有 50pts,于是想想怎么优化,这就需要用到线段树合并了。

    首先简要说一下线段树合并的作用:对于两棵动态开点线段树,设这两棵树点数均为 x x x,那么线段树合并可以在 O ( x ) O(x) O(x) 的时间内将两棵线段树的信息合并到一棵上。如果两棵树点数不一样就需要看树的结构了,但是可以保证会至多遍历较大树一次。

    那么怎么合并呢,就是对两棵树同时暴力 dfs,自底向上更新即可。

    听起来确实很暴力呢,说白了就是将两棵树对应的点合到一起,那么他们相关的信息也被合到了一起,只不过实现的时候我们是先合并左右儿子然后再合并这个点,学过别的需要合并的数据结构的应该能很快理解。

    画个图解释下:

    假设现在我们有两棵线段树,每个点维护区间和(每个点上的数字就是区间和):

    在这里插入图片描述
    那么现在将这两棵线段树进行合并,结果就是这样的:

    在这里插入图片描述

    然后实现过程就是暴力!

    回到例题,我们发现每次修改都是对路径的修改,于是这里我们可以套上一个树上差分, x , y , l c a ( x , y ) , f a l c a ( x , y ) x,y,lca(x,y),fa_{lca(x,y)} x,y,lca(x,y),falca(x,y) 这四个点单点修改,然后对这棵树重新 dfs 然后自底向上进行线段树合并即可。

    至于为啥复杂度是对的,因为你总共只有 4 n 4n 4n 个节点对吧,因此自底向上合并的时候由于复杂度一般是点数较小树决定的,复杂度不会过 O ( 4 n ) O(4n) O(4n),空间复杂度 O ( 4 n log ⁡ n ) O(4n \log n) O(4nlogn)

    关于线段树合并的写法就有两种形式了:

    先贴一下结构体和 Update 函数:

    struct SgT
    {
        int l, r, Maxn, ans;
        #define l(p) tree[p].l
        #define r(p) tree[p].r
        #define Maxn(p) tree[p].Maxn
        #define ans(p) tree[p].ans
    }tree[MAXN * 100];
    
    void Update(int p)
    {
        if (Maxn(l(p)) >= Maxn(r(p))) { Maxn(p) = Maxn(l(p)); ans(p) = ans(l(p)); }
        else { Maxn(p) = Maxn(r(p)); ans(p) = ans(r(p)); }
    }
    

    一种写法是直接合并,在原树上修改值:

    void Merge(int &p1, int p2, int l, int r) // 表示将树 p2 的信息合并到树 p1 上
    {
        if (!p1 || !p2) { p1 = p1 + p2; return ; }
        if (l == r) { Maxn(p1) = Maxn(p1) + Maxn(p2); return ; }
        int mid = (l + r) >> 1;
        Merge(l(p1), l(p2), l, mid);
        Merge(r(p1), r(p2), mid + 1, r);
        Update(p1);
    }
    

    这种做法的好处是节省了空间,但是坏处是如果你需要询问这个点的相关内容需要在修改之后立刻询问才行,即使是像例题一样做在差分完毕之后统一 dfs 自底向上合并,也需要在这个点合并完之后立刻存下答案,否则就会造成答案错误,因为该做法合并的时候会出现多个树共用一个节点的情况,此时一旦任何一棵树被合并,所有的树答案都会被影响。

    该做法只适用于修改完之后即刻询问的做法。

    另外一种做法是不修改这个点点值,而是动态开点接着做(边合并边动态开点):

    int Merge(int p1, int p2, int l, int r)
    {
        if (!p1 || !p2) { p1 = p1 + p2; return p1; }
        int p = ++cnt_SgT; // cnt_SgT 是计数器
        if (l == r) { Maxn(p) = Maxn(p1) + Maxn(p2); ans(p) = l; return p; }
        int mid = (l + r) >> 1;
        l(p) = Merge(l(p1), l(p2), l, mid);
        r(p) = Merge(r(p1), r(p2), mid + 1, r);
        Update(p); return p;
    }
    

    这个做法会比较耗空间,但是好处就是你可以边修改边询问,询问修改互不干扰,因为你每次都动态开点了。

    当然该做法耗空间是可以避免的,比如你使用一个空间回收的 Trick,这个 Trick 可以将那些再也用不到的点拿回来重复利用,其实相当于指针空间释放再开指针,而且空间回收是不会影响总复杂度的(顶多影响一点常数)。

    但是特别的,如果你用了空间回收的话你就需要跟第一个做法一样合并完立刻存下答案了,理由就是空间回收会清空一个点的数据,这对以该节点为根的点的询问会有影响。

    不过因为这道题空间复杂度不过 O ( 4 n log ⁡ n ) O(4n \log n) O(4nlogn),所以现在不用空间回收也能过。

    CodeBase:CodeBase-of-Plozia

    Code:

    /*
    ========= Plozia =========
        Author:Plozia
        Problem:P4556 【模板】线段树合并
        Date:2021/12/5
    ========= Plozia =========
    */
    
    #include <bits/stdc++.h>
    
    int Max(int fir, int sec) { return (fir > sec) ? fir : sec; }
    int Min(int fir, int sec) { return (fir < sec) ? fir : sec; }
    
    typedef long long LL;
    const int MAXN = 1e5 + 5;
    int n, q, Head[MAXN], cnt_Edge = 1, Root[MAXN], cnt_SgT, fa[MAXN][21], dep[MAXN];
    struct node { int To, Next; } Edge[MAXN << 1];
    struct SgT
    {
        int l, r, Maxn, ans;
        #define l(p) tree[p].l
        #define r(p) tree[p].r
        #define Maxn(p) tree[p].Maxn
        #define ans(p) tree[p].ans
    }tree[MAXN * 100];
    
    int Read()
    {
        int sum = 0, fh = 1; char ch = getchar();
        for (; ch < '0' || ch > '9'; ch = getchar()) fh -= (ch == '-') << 1;
        for (; ch >= '0' && ch <= '9'; ch = getchar()) sum = sum * 10 + (ch ^ 48);
        return sum * fh;
    }
    void add_Edge(int x, int y) { ++cnt_Edge; Edge[cnt_Edge] = (node){y, Head[x]}; Head[x] = cnt_Edge; }
    
    void Update(int p)
    {
        if (Maxn(l(p)) >= Maxn(r(p))) { Maxn(p) = Maxn(l(p)); ans(p) = ans(l(p)); }
        else { Maxn(p) = Maxn(r(p)); ans(p) = ans(r(p)); }
    }
    
    void dfs(int now, int father)
    {
        dep[now] = dep[father] + 1; fa[now][0] = father;
        for (int i = Head[now]; i; i = Edge[i].Next)
        {
            int u = Edge[i].To;
            if (u == father) continue ;
            dfs(u, now);
        }
    }
    
    void init()
    {
        for (int j = 1; j <= 20; ++j)
            for (int i = 0; i <= n; ++i)
                fa[i][j] = fa[fa[i][j - 1]][j - 1];
    }
    
    int LCA(int x, int y)
    {
        if (dep[x] < dep[y]) std::swap(x, y);
        for (int i = 20; i >= 0; --i)
            if (dep[fa[x][i]] >= dep[y]) x = fa[x][i];
        if (x == y) return x;
        for (int i = 20; i >= 0; --i)
            if (fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
        return fa[x][0];
    }
    
    void Insert(int &p, int x, int k, int l, int r)
    {
        if (!p) p = ++cnt_SgT;
        if (l == r && l == x) { Maxn(p) += k; ans(p) = x; return ; }
        int mid = (l + r) >> 1;
        if (x <= mid) Insert(l(p), x, k, l, mid);
        else Insert(r(p), x, k, mid + 1, r);
        Update(p);
    }
    
    int Merge(int p1, int p2, int l, int r)
    {
        if (!p1 || !p2) { p1 = p1 + p2; return p1; }
        int p = ++cnt_SgT;
        if (l == r) { Maxn(p) = Maxn(p1) + Maxn(p2); ans(p) = l; return p; }
        int mid = (l + r) >> 1;
        l(p) = Merge(l(p1), l(p2), l, mid);
        r(p) = Merge(r(p1), r(p2), mid + 1, r);
        Update(p); return p;
    }
    
    void dfs2(int now, int father)
    {
        for (int i = Head[now]; i; i = Edge[i].Next)
        {
            int u = Edge[i].To;
            if (u == father) continue ;
            dfs2(u, now); Root[now] = Merge(Root[now], Root[u], 1, MAXN - 5);
        }
    }
    
    int main()
    {
        n = Read(), q = Read();
        for (int i = 1; i < n; ++i)
        {
            int x = Read(), y = Read();
            add_Edge(x, y); add_Edge(y, x);
        }
        add_Edge(0, 1); add_Edge(1, 0);
        dfs(0, 0); init();
        for (int i = 1; i <= q; ++i)
        {
            int x = Read(), y = Read(), z = Read();
            int l = LCA(x, y);
            Insert(Root[fa[l][0]], z, -1, 1, MAXN - 5);
            Insert(Root[l], z, -1, 1, MAXN - 5);
            Insert(Root[x], z, 1, 1, MAXN - 5);
            Insert(Root[y], z, 1, 1, MAXN - 5);
        }
        dfs2(0, 0);
        for (int i = 1; i <= n; ++i)
        {
            if (Maxn(Root[i]) == 0) printf("0\n");
            else printf("%d\n", ans(Root[i]));
        }
        return 0;
    }
    

    3. 总结

    线段树合并就是一种暴力合并算法,结合动态开点线段树完成,但是我们可以通过诸如计算空间复杂度最大值,启发式合并等思路降低复杂度。

    4. 参考资料

    展开全文
  • 线段树区间合并详解

    2018-05-24 15:20:30
    深入理解线段树区间合并问题摘自:百度文库

    深入理解线段树区间合并问题

    摘自:百度文库

    展开全文
  • 数据结构 线段树--权值线段树 详解

    千次阅读 2021-05-29 11:21:24
    一、权值线段树 简介 1.线段树 线段树是一种用于维护区间信息的高效数据结构,可以在 O(log⁡N)O(\log N)O(logN) 的时间复杂度内实现单点修改、区间修改、区间...具体有关线段树的的讲解请参考博客:线段树 详解与模板
    😊 | Powered By HeartFireY | Weighted Segment Tree

    一、权值线段树 简介

    1.线段树

    线段树是一种用于维护区间信息的高效数据结构,可以在 O ( log ⁡ N ) O(\log N) O(logN) 的时间复杂度内实现单点修改、区间修改、区间查询(区间求和,求区间最大值,求区间最小值)等操作。

    线段树维护的信息必须满足可加性,即能以可以接受的速度合并信息和修改信息,包括在使用Lazy标记时,标记也要满足可加性

    具体有关线段树的的讲解请参考博客:线段树 详解与模板

    2.权值线段树

    权值线段树是一种建立在基本线段树之上的数据结构。因此它的基本原理仍是基于对区间的维护操作。但与线段树相区分的点是:权值线段树维护的信息与基本线段树有所差异:

    • 基本线段树中每个系欸但用来维护一段区间的最大值或总和等;
    • 权值线段树每个结点维护的是一个区间的数出现的次数。

    实际上,权值线段树可以看作是一个桶,桶的操作它都支持,并且能够以更快的方式去完成。

    根据权值线段树的性质,我们可以知道其主要用途:

    权值线段树一般用于维护一段区间的数出现的次数,从它的定义来看,它可以快速计算出一段区间的数的出现次数。

    在实际应用中,我们使用权值线段树查询区间第 K K K大的值。

    二、权值线段树的基本原理与操作

    1.权值线段树维护信息的原理

    基础线段树和权值线段树的一个较大的区别点在于:(此处特指使用数组储存树结构)基础线段树根据初始的一个序列建立树结构,具有单独的建树操作;而权值线段树不需要进行建树操作,初始状态下默认建立一棵所有点权为 0 0 0的空树,对于每个元素,在遍历的时候相应的结点做自增运算。换而言之:

    • 权值线段是一棵已经建好的线段树,储存树结构的下标范围根据区间最大值最小值确定(一般开大空间即可);
    • 初始状态下所有的点权均为 0 0 0
    • 执行插入元素的操作时,会导致插入值 v v v对应的 A [ v ] + + A[v]++ A[v]++,同时引发单点更新操作。
    • 可以从上述描述中得到基本推论:向空的权值线段树中插入一个无序序列,则插入完成后在树上无法再得到原序列的遍历,但能通过遍历得到有序序列(无序序列变有序序列)

    我们可以通过结构对比线段树与权值线段树的区别,以此理解原理。

    我们给定序列 { 1 , 2 , 2 , 3 , 3 , 3 , 4 , 4 , 4 , 4 } \{1, 2, 2, 3, 3, 3, 4, 4, 4, 4 \} {1,2,2,3,3,3,4,4,4,4},以该序列为例建立两种线段树。

    首先,序列长度为 10 10 10,建立基础区间和查询线段树,结构图如下:

    在这里插入图片描述

    对应具体的细节不再阐述。我们继续建立权值线段树:首先给出一棵空树:

    (注:为演示方便,A数组下标做+1操作,树上的范围也对应变化,这里懒得改了~)

    在这里插入图片描述

    然后按照序列顺序插入元素:

    在这里插入图片描述

    解释:

    A [ 1 ] = 1 A[1] = 1 A[1]=1:原序列中存在值为 1 1 1的元素 1 1 1
    A [ 2 ] = 1 A[2] = 1 A[2]=1:原序列中存在值为 2 2 2的元素 2 2 2
    A [ 3 ] = 1 A[3] = 1 A[3]=1:原序列中存在值为 3 3 3的元素 3 3 3
    A [ 4 ] = 1 A[4] = 1 A[4]=1:原序列中存在值为 4 4 4的元素 4 4 4

    D [ k ] D[k] D[k]一定区间内所含元素的个数

    我们继续探究查找第 K K K大元素的方法:

    由于权值线段树每个节点记录了某段区间内包含的元素个数,且元素在叶子节点构成的序列中是有序的:

    • 对于整列数中第 K K K大/小的值,我们从根节点开始判断(这里按第 K K K大为例),如果 K K K比右儿子大,就说明第 K K K大的数在左儿子所表示的值域中。然后, K K K要减去右儿子。(这是因为继续递归下去的时候,正确答案,整个区间的第 K K K大已经不再是左儿子表示区间的第 K K K大了)。如此递归到叶子节点时即为答案。
    • 整棵线段树的根节点就表示整个值域有几个数。

    我们很容易看出:在权值线段树中,采用元素到下标数组映射的方式进行插入。这样会导致一个问题:在数据离散程度较大的情况下,空间的利用效率比较低。因此我们对于线段树所开空间不足时,常采用离散化的方式进行解决。

    📕 | 此处的前导知识:离散化(具体的参见离散化的讲解)

    2.权值线段树的基本操作与实现

    ①.查询第 K K K大/小元素

    假设 K = 5 K = 5 K=5,那么查询过程是怎样的?

    首先我们从根节点出发,由于要查询第 K K K大,是相对于终点而言的,因此从右子结点开始判断:

    在这里插入图片描述

    当前节点右子树包含 4 4 4个元素,所以应该向左子树遍历,注意:此时应该减去右子树的 4 4 4个元素!

    在这里插入图片描述

    寻找第 K K K小的操作与上方类似,区别在于相对于起点OR终点而言(遍历时对左右子树的判断顺序)。

    再次回顾整个步骤:对于整列数中第 K K K大/小的值,我们从根节点开始判断(这里按第 K K K大为例),如果 K K K比右儿子大,就说明第 K K K大的数在左子树中。然后, K K K要减去右子节点的值。(这是因为继续递归下去的时候,正确答案,整个区间的第 K K K大已经不再是左子树表示区间的第 K K K大了)。如此递归到叶子节点时即为答案

    根据以上分析步骤,我们可以写出查询第 K K K大和第 K K K小的函数:

    int query_kth(int pos, int l, int r, int k){
        if(l == r) return l;
        int mid = (l + r) >> 1, right = tree[pos << 1 | 1];
        if(k <= right) return query(pos << 1 | 1, mid + 1, r, k);
        else return query(pos << 1, l, mid, k - right);
    }
    
    int query_kth(int pos, int l, int r, int k){
        if(l == r) return l;
        int mid = (l + r) >> 1, left = tree[pos << 1];
        if(k <= left) return query(pos << 1, l, mid, k - left);
        else return query(pos << 1 | 1, mid + 1, r, k);
    }
    

    ②.单点更新操作

    类似基础线段树,递归到叶子节点 + 1 +1 +1然后回溯

    void add(int l, int r, int v, int x){
        if (l == r) tree[v]++;
        else{
            int mid = (l + r) >> 1;
            if (x <= mid) add(l, mid, v << 1, x);
            else add(mid + 1, r, v << 1 | 1, x);
            tree[v] = tree[v << 1] + tree[v << 1 | 1];
        }
    }
    

    ③.查询某个数出现的个数

    树上二分查找的思想,代码如下:

    int find(int l, int r, int v, int x){
        if (l == r) return tree[v];
        else{
            int mid = (l + r) >> 1;
            if (x <= mid) return find(l, mid, v << 1, x);
            else return find(mid + 1, r, v << 1 | 1, x);
        }
    }
    

    ④.查询一段区间的数出现的次数

    int find(int l, int r, int v, int x, int y){
        if (l == x && r == y) return tree[v];
        else{
            int mid = (l + r) >> 1;
            if (y <= mid) return find(l, mid, v << 1, x, y);
            else if (x > mid) return find(mid + 1, r, v << 1 | 1, x, y);
            else return find(l, mid, v << 1, x, mid) + find(mid + 1, r, v << 1 | 1, mid + 1, y);
        }
    }
    

    3.区间离散化

    如前所述,在将元素个数映射到叶子节点的过程中,离散程度较大时会导致极低的空间利用效率。对本种数据结构,我们关心的仅仅是元素之间的大小关系,因此可以采用离散化的方法对空间进行优化。

    离散化的知识在此不展开赘述,直接采用C++STL算法

    int get_discretization(){
        for (int i = 1; i <= n; ++i) a[i] = read(), b[i] = a[i]; //读入数据
        sort(b + 1, b + n + 1);
        int len = unique(b + 1, b + n + 1) - b - 1;
        for (int i = 1; i <= n; ++i){
            int pos = lower_bound(b + 1, b + len + 1, a[i]) - b;
            a[i] = pos;
        } //离散化
    }
    
    展开全文
  • 线段树合并模板
  • 线段树详解

    千次阅读 多人点赞 2018-08-12 18:44:56
    1.线段树是一种二叉搜索树,与区间树相似,它将一个区间划分成一些单元区间,每个单元区间对应线段树中的一个叶结点。 (严格来说:二叉查找树(Binary Search Tree),(又:二叉搜索树,二叉排序树)它或者是一...
  • 【算法】线段树详解

    万次阅读 多人点赞 2018-08-20 15:32:29
    线段树,是一种二叉搜索树。它功能强大,支持区间求和,区间最大值,区间修改,单点修改等操作。 它的时间复杂度是O(nlogn)的。 十分良心,欢迎阅读!
  • zkw线段树详解

    千次阅读 2019-06-19 16:11:41
    定义 我们已经了解了线段树的...和普通的线段树相比,zkw线段树主要有这样几个不同点: 1.所有的叶子结点都在同一深度 2.在左右两端各增加了一个哨兵 3.每个点可以根据自己的编号计算父节点编号 以上三点保证了...
  • 线段树详解 (原理,实现与应用)

    万次阅读 多人点赞 2015-09-09 01:58:46
    线段树详解 By 岩之痕 一:综述 线段树是一种可以快速进行区间修改和区间查询的数据结构。点修改,区间修改和区间查询的复杂度都是O(log2(n)) 并且,线段树可以维护很多种类的信息。说到线段树就不得不提一下树状...
  • 对节点建权值线段树,考虑将左右孩子的线段树合并时,不反转的情况下,每次统计左孩子对右孩子的影响的数量,然后递归合并下去。反转的情况下就是考虑右孩子对左孩子的影响。 其实这里本质上和cdq分治是一样的,...
  • 线段树详解与实现

    2020-08-08 22:27:31
    那么为什么会产生线段树这种数据结构,线段树到底是为了解决什么样的一种问题呢? 其实这里的线段可以理解为区间,线段树就是为了解决区间问题的。 有一个很经典的线段树问题是:区间染色。 假设有一面墙,长度为 n...
  • 线段树 详解 一、线段树简介 线段树是算法竞赛中常用的用来维护 区间信息 的数据结构。 线段树可以在 O(log⁡N)O(\log N)O(logN) 的时间复杂度内实现单点修改、区间修改、区间查询(区间求和,求区间最大值,求区间...
  • 线段树入门详解

    2019-09-28 00:51:37
    目录 线段树入门详解 本文适用人群 线段树大致思路 本人代码习惯 单点修改 单点查询 区间查询 区间加减 Last 线段树入门详解 本文适用人群 不算特别入门啦...
  • 线段树详解

    2019-09-28 13:26:41
    线段树详解】1. 什么是线段树2. 使用线段树的必要条件 - 区间加法3. 线段树的基本操作3.1 初始化(建树)3.2 单点修改3.3 区间修改3.4 区间查询4.线段树的整体代码(例: POJ - 3468 A Simple Problem with ...
  • 逆序对——线段树

    2020-08-04 10:43:25
    逆序对——线段树做法大体思路三道题目Sort it(模板题)Inversion(线段树+离散化)Minimum Inversion Number(线段树+思维)错误提示 大体思路 使用线段树统计逆序对。建立一个空树。注意树的范围,如果数组中的...
  • 二维线段树详解

    2019-08-17 00:06:54
    二维线段树最主要用于平面统计问题。类似一维线段树,最经典的就是求区间最值(或区间和),推广到二维,求得就是矩形区域最值(或矩形区域和),对于矩形区域和,二维树状数组更加高效,而矩形区域最值,更加高效的...
  • 线段树算法详解

    2019-04-18 15:56:00
    线段树基本概念 线段树,顾名思义就是由一个一个线段组成的一颗树,每个结点都是一个线段(叶子结点是单元结点),那么每个结点应该包括: 区间左右端点。 区间要维护的信息(视情况而定)。 即每个结点是一...
  • 输出[l,r]中有几段不同的数字题解:这题可以采用启发式合并,也就是每次把个数少的往个数大的上面合并,这样如果要合并成n个一样的最坏的情况是nlogn的(n/2*logn)然后合并的时候用线段树单点更新下就行时间复杂度O(nlog...
  • 文章目录通过做题目思考:为什么我们要学线段树呢?一.详细讲解线段树。1.建树2.单点查询3.单点修改4.区间查询 通过做题目思考:为什么我们要学线段树呢? 下面的抛出两个问题一起思考一下: 问题1 : 给1000个正...
  • 线段树区间合并的板子题。。。对刚开始触及到的萌新还是稍微提一下: 我们设置变量lsum,rsum,sum,f分别表示节点从左端点开始最大的连续区间,从右端点开始的连续区间,整段区间的最大连续区间,标记。 区间和...
  • 线段树总结详解

    2017-08-23 19:40:37
    线段树详解 By 岩之痕 目录: 一:综述 二:原理 三:递归实现 四:非递归原理 五:非递归实现 六:线段树解题模型 七:扫描线 八:可持久化 (主席树) 九:练习题 一:综述 假设有...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 725
精华内容 290
热门标签
关键字:

线段树合并详解