郑州做网站公司电话,wordpress 管理插件,电子商务网站建设规划的内容,如何给网站流量来源做标记通过在网址后边加问号?我貌似和所有的数据结构都有些误会。。。。。。 在处理一些修改查询问题的时候#xff0c;我们可以利用分治的思想#xff0c;比如说把一个线性的数据不断分成一棵二叉树#xff0c;也就是我们所说的线段树#xff0c;这样我们就可以在logn的时限里做到修改和查询。同理我们…我貌似和所有的数据结构都有些误会。。。。。。 在处理一些修改查询问题的时候我们可以利用分治的思想比如说把一个线性的数据不断分成一棵二叉树也就是我们所说的线段树这样我们就可以在logn的时限里做到修改和查询。同理我们也可以把数据分成一个只有两层的树算上根节点三层每个节点分成sqrt该节点大小个节点这就是我们所说的分块了。 这里我们主要讲解分块的思想 话不多说先上一张图 如图我们这就是一个分好块的结构。 那么这个结构有个什么用呢很明显我们可以用它维护单点修改与查询区间的修改查询。。。 看上去有些眼熟是不是想起来了些什么 没错就是线段树那几个操作。那么现在我们继续可以发现分块的修改和查询操作都是Osqrtn的。那还要分块有个什么用 我们先来看这么一道题 我们刚开始看的时候可能觉得可以用数据结构实现什么线段树主席树平衡树都可以想一想不过一会你就会发现它们都不可行过了一会你会发现有一种线段树套平衡树的方法或许可做只不过代码复杂度很高而且估计要调不短的时间吧。这个时候就是分块出场的时候了。 为什么这个题不能通过线段树实现原因就在于第二个操作过于烦人线段树维护的区间信息无法找出单点的如果要查找一个区间中的所有点无法得到一个让人满意的复杂度。那么为什么分块就可以令人满意了呢 首先我们说明几个接下来经常会说的名词 整块查询范围内完全包括的块也就是范围内第二层的块。 零散块查询范围内除了整块其他的部分是第三层的块也就是一个一个的点。 接着声明几个变量 那么我们再修改的时候对于区间内所有的整块我们O(1)的打上加法标记即可。 那么对于所有的零散块呢 我们发现我们最多有两个部分的零散块其中每个部分里最多有不超过sqrtn个点我们直接暴力枚举下标修改即可那么整个修改操作的复杂度就是Osqrtn 那么我们再查询的时候对于每个整块我们可以知道它是完全有序的所以我们可以直接二分查找返回。对于零散块我们仍然选择暴力枚举那么查询操作的复杂度就是Osqrtnlogn。 所以整个操作我们就可以在Oqsqrtnlogn的复杂度内完成了。 笔者秉承懂了算法不看模板的法则自己手动实现了一下这个题目。接下来分块讲述一下代码的意义 这一部分就是预处理并且分块的部分和块的左右区间的处理。 然后在你的分块主体开始之前必须要有的一条语句 这条语句就是先把b数组的每一个块中的数据排好序这样要不然很有可能找的时候由于每一块的b数组还没有排序导致查找错误。 然后就是分块的主体部分我们分成修改和查询分别看一下 这个就是修改操作。要注意的是在读入的x和y点属于同一个块的时候我们要特殊操作。 如果不在同一个块里我们就遍历包含的所有整块打上标记。然后对于左右那两个零散块我们直接枚举就可以了。为什么用的是a数组而不是b数组因为b数组在排完序之后下标代表的意义是数的大小顺序而不是我们一开始读入的顺序不能直接修改b数组。还有一个就是这里笔者为了打上去方便修改b数组的时候用了sort这样我们的复杂度就增加了一个sqrtlogn但是我们使用归并重构零散块的话还是可以达到sqrtn的。对于 在同一个块里的我们也是直接暴力枚举就可以了。 为什么这些零散块可以暴力枚举复杂度不会很高么不会的在修改每一个零散块的时候我们最多也就修改sqrtn个点所以并不会有特别高的额复杂度。 这个是查询操作怎么查找刚才都已经说过了同样零散块我们就暴力枚举即可。 那么这道题就这么完成了。 纯粹让你用分块完成的题目比较少但是我们可以用这东西水一水分毕竟这玩意比线段树什么的好写多了。 转载于:https://www.cnblogs.com/victorique/p/8488216.html
