2022年8月16日总结:
一场CF,两场牛客
第一场CF 
第一题确实写得快,但是第二题的时候当时的第一想法错了,当即就决定跳题了,C题结论得出的也比较快,D题确实比较可惜,思路是对的就是有特殊情况没有考虑到
第一场牛客
总体来说还是不是那么的稳
第二场牛客
D题确实是可以尝试一下,逻辑没有写好,F题也是血亏6发
本周学习内容:
莫队算法:主要用来处理区间性的问题,n√n的复杂度,底层逻辑还是暴力的思想,但是是分块的暴力,将提问的区间问题根据分块排序,然后通过l和r指针的移动来进行"暴力"求解,但是是比较有规划的暴力求解,对于可能比较复杂的区间性问题,在时间复杂度允许的情况下,确实是可以作为尝试
普通平衡树(treap):tree和heap的结合,tree是二叉搜索树,主要是通过旋转操作以及随机键值key来维护heap,从而达到接近平衡树,便于后序的操作.
FHQ平衡树:和普通平衡树一样tree和heap的结合,但是不是通过旋转来维护heap,而是通过两种操作split(撕裂,将一棵二叉树根据值v分成两个二叉树)和merge(合并,将两个二叉树根据随机键值key以及heap的性质合并),总体上的时间复杂度要比普通平衡树要低一些,操作也相对比较的简单,所有的操作都是通过split和merge来维护
splay平衡树:对比于上面两种平衡树不再需要heap来维护平衡树的状态,核心操作只有splay,对于所有的访问操作都将目标节点通过双旋的操作将节点旋转到根,双旋根据特定的旋转将树尽可能的接近平衡树的状态,又因为每次将要操作的节点旋转到根,所以对于集中的区域访问效率会非常的高.
树剖:将树状图强行降维为线形图的一种算法,幸运的是刚学完牛客就用上了,主要处理树上的区间性修改以及询问,还能够实现lca(最近公共祖先)的功能,比一般的lca要更加的快,因为树剖的跳点是直接跳转到对应的根节点,初始需要两遍bfs来进行初始化,第一遍bfs主要记录父节点,节点深度,重子节点,节点所在子树节点数,重子节点为所有的子节点子树节点数最多的子节点,第二次bfs主要就是更新节点的跳点,时间戳,时间戳对应的点权值,最终将树状图降维为线性图,通过线段树等来维护树的区间性问题.
树状数组:原理和线段树非常的类似,处理速度也要优于线段树,对于每个节点都需要管理一块数组,管理的区域就是节点编号的最后一个二进制为为1的大小,对于a来说统计的大小为a&-a,以当前节点为基准,记录前面的个数.主要是用前缀和以及差分来处理问题.
点分治:分治的思想求解类似于树上有多少个距离为k的d(u,v)问题,将树上任意的两个节点u,v,以及一个root节点划分成两种u-v经过root的节点和u-v不经过root的节点,对于每个经过节点root的节点都记录d(root,v),这样d(u,v)=d(u,root)+d(v,root).
最后总结:平衡树基本上是学完了,红黑树和替罪羊树还没有去看,主要是代码量大,失误率高,以及考试中出现的频率极低,所以目前先把一些简单实用的算法都学完.
后序规划:最近学的一些算法很多都是模板型的算法,写题目前也多是写了一个模板题,还是得多去看看思维型的题目
标签：总结,算法,heap,操作,平衡,root,节点 From： https://www.cnblogs.com/zhou-mo/p/16590464.html