长乐(mian) Day7

众所周知因为一些原因没能写之前的几篇博客……时间紧迫,有空再慢慢补上吧。

今天的内容是线段树、倍增和LCA!

  • 线段树

    一种将一段区间分为若干段区间,每个节点都储存着一段区间的二叉搜索树。

    (某AKIOI的dalao用一根手指吊打了我和我的无知,据祂所说,树状数组区间修改居然比线段树复杂,请原谅我的无知)

    初始建树

    用二分的思想遍历整棵树。叶节点直接赋值即可,非叶节点就由左右子树信息合并而来啦。(非常好理解!!!)

    
    
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    void buil(int i,int l,int r){
        if (l==r){ //叶节点
            orz[i]=a[l];
            return;
        }
        buil(i*2,l,(l+r)/2);
        buil(i*2+1,(l+r)/2+1,r);
        orz[i]=orz[i*2]+orz[i*2+1];
        return;
    }//这是一棵维护区间和的线段树。不要在意函数和变量名,个人喜好而已(确信</pre>

    (单点查询和单点修改用树状数组就可以了吧……?所以下面就直接写区间查询和区间修改吧~)

    区间查询

    和区间修改有那么一丝丝相似之处。 似乎我需要重修小学语文的语言表达,那么就把思路放在注释里吧。
    
    
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    long long quer(int i,int ql,int qr,int l,int r){
        if (l>=ql&&r<=qr){  //如果整个区间都包含在查询范围内,直接返回区间和即可
            return orz[i];
        }
        downtag(i,l,r);  //下沉标记
        int mid=(l+r)/2;
        long long ret=0;
        if (ql<=mid){  //如果要查询的区间有一部分在左子树
            ret+=quer(i*2,ql,qr,l,mid);
        }
        if (qr>mid){  //如果要查询的区间有一部分在右子树
            ret+=quer(i*2+1,ql,qr,mid+1,r);
        }  //之所以用一个ret+=而不是直接返回,是因为咱也不敢保证查询区间就完美地落在左子树或者右子树上
        return ret;
    }

    区间修改

    和区间查询有那么一丝丝相似之处。

    需要用到懒标记:若遍历到的节点带有懒标记,则立即修改当前节点的信息,并把标记下放到左右儿子,然而左右子树的信息不变动,只有遍历到左/右节点时才修改其信息。

    
    
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    void downtag(int i,int l,int r){
        if (tag[i]==0){
            return;  //没有标记的话就没有下沉的必要啦
        }
        int mid=(l+r)/2;
        tag[i*2]+=tag[i];
        orz[i*2]+=(long long)tag[i]*(mid-l+1);
        tag[i*2+1]+=tag[i];
        orz[i*2+1]+=(long long)tag[i]*(r-mid);
        tag[i]=0;  //下沉了就可以清零啦,不然标记就重复啦,就会听取WA声一片啦
        return;
    }
    void modi(int i,int ql,int qr,int l,int r,int k){
        if (l>=ql&&r<=qr){
            orz[i]+=(long long)k*(r-l+1);  //同查询,如果整个都在修改范围内就直接全改啦
            tag[i]+=k;
            return;
        }
        downtag(i,l,r);  //下沉
        int mid=(l+r)/2;
        if (ql<=mid){  //整体思路同查询
            modi(i*2,ql,qr,l,mid,k);
        }
        if (qr>=mid+1){
            modi(i*2+1,ql,qr,mid+1,r,k);
        }
        orz[i]=orz[i*2]+orz[i*2+1];  //更新一下区间和(因为修改过所以需要更新一下)
        return;
    }

    小学数学的重要性

    可以用线段树维护同时的区间加和区间乘。

    非常简单,只需要多设一个乘法懒标记,然后利用小学学过的乘法分配律:(a+b)c=a*c+b*c即可。有了这个公式,想必大家都知道怎么写了吧~

  • 倍增

    我很逊,并没有完全理解倍增,更别提LCA啦。

    它大概就是从某个数据范围中不断划分出2的整数次幂然后查找?(我觉得我阅读理解能力和上课专注力有待提高)

    正确性来源于“二进制唯一分解定理”:每个正整数能且只能被表示为唯一的二进制数?

    ST表和LCA都用到倍增的思想。所以我不能摆烂不学啦。

    和二分很像但是不能像二分那样枚举答案,但是可以更快地枚举枚举信息较为复杂的问题。(咋又是枚举,让我想到了数论课上的LHX)

    例题1:查找编号

    题目大意:求整数q在单调不递减的非负整数序列a中的编号。

    
    
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    #include<bits/stdc++.h>
    using namespace std;  //如果答案存在,那它一定大于等于它前面的数,所以找出小于询问的数的最后一个数即可
    int n,m,a[1000001],ans=0;  //用ans存储找到的最后一个数
    int main()
    {
        cin>>n>>m;
        for (int i=1;i<=n;i++){
            cin>>a[i];
        }
        while (m--){
            int x;
            cin>>x;
            ans=0;
            for (int i=20;i>=0;i--){  //枚举指数
                if (ans+(1<<i)<=n){  //如果大于n那就越界了,RE警告(当然有时候也会是WA甚至TLE)
                    if (a[ans+(1<<i)]<x){  //如果ans+2^i<x的话就更新ans
                        ans+=(1<<i);   //(更新前的ans很显然不是小于询问的数的最后一个数)
                    }
                }
            }
            if (ans+1<=n&&a[ans+1]==x){  //如果小于询问的数的最后一个数的后一个数就是询问的数
                cout<<ans+1<<" ";
            }
            else{  //如果不是就证明找不到
                cout<<-1<<" ";
            }
        }
        return 0;
     }

    一道大水题……好吧其实是倍增这部分我唯一一道A了的题(

    例题2:开车旅行

    这题我搞了一下午仍然没有搞懂……(所以这就是我没写LCA的理由???)然后就被YY拉去吃烧烤然后又被某省一催着去写博客所以就没来得及A了它。思路是可以搞明白的,但书上的代码……看得我头晕,自己写的代码又漏洞百出连样例都过不了。(果然我还是太菜了)

    是利用倍增优化的dp+双向链表(事实证明我似乎连链表都学了个寂寞,偷的懒最终会成为埋葬自己的天坑)……

    今晚熬夜看看能不能搞掉这题,先滚去写LCA啦。

  • 最近公共祖先(LCA)

    被戏称为“最远私人祖坟”(划掉)

    就是在一棵有根树中满足同时是点x和点y的祖先且深度最大的节点啦。

    本着“暴力出奇迹”的信仰,我们可以通过暴力的方式求出LCA(x,y):标记x的所有祖先节点,再从y开始向上走直到第一个有标记的节点,这个节点就是LCA(x,y)啦~

    但是这么做的时间复杂度……TLE警告。我们知道倍增可以加快枚举速度,所以我们可以利用倍增来寻找LCA。首先我们要通过倍增将深度较大的节点向上转移到与另一个节点深度相同。当x,y深度相同时,若x,y指向同一个节点,这个节点就是LCA(x,y);否则就继续向上找啦。

    我们可以从大到小枚举i,判断从x,y分别出发走2^i步到达的节点是否相同,如果相同,不作任何变动(此时这个节点不一定是LCA(x,y),为什么呢?结合二进制想想吧);否则就让x,y各往上走2^i步。枚举结束时,x的父节点就是LCA(x,y)。然而我并没有做例题(万恶的开车旅行……)所以等到我做完例题之后重新编辑一下这个博客,把那些例题还有求LCA的标程都放上来吧。

字数统计:3050。能看到这里的你肯定是个温柔的人吧。^-^

《长乐(mian) Day7》有2个想法

发表评论

邮箱地址不会被公开。 必填项已用*标注