2019WIT Summer Camp

发布于 8 天前  11 次阅读


WIT Summer Camp —— Lzh 之假前培训 —— 分块、线段树、数状数组(单点更新,区间查询)板子题

单点更新,区间查询(模板)

分块

顾名思义,分块就是将整段区间分成若干个块,再以每个块为单位进行操作。

比如上题中,求一个区间 l 到 r 的和,那么,在 l 到 r 中必然存在若干个块,区间的和就可以转化为这些块之和,而对于区间两端不满一个块的部分,就直接暴力将每个数字遍历一次。

所以,我们只需要预处理出来每个块中包含的元素之和,将这个块记为一个新单位,求任意一段区间和就按上述操作执行一次即可。

而修改操作,也只需要修改这个点的值以及所处的块的值即可。

当然,为了更快的找到一个快的左右端点以及当前点位于哪一个块中 ,我们需要另开三个数组进行记录(具体实现看代码)。

PS:由于一些原因,这一部分并没有认真听讲(具体原因下文会阐述~~),上文的大部分内容纯属个人瞎bb~~而至于整段区间应该分成几块,也只隐约听到了什么根号~~那就这么分吧~~不管了,能过就好~~

感觉又会被喷码风奇怪~~

线段树

就是因为这个该死的线段树,一开始读错题了,写了一个贼复杂的,调了半天还是TLE~~所以上一段内容完美错过 嘤嘤嘤

每一个结点代表一段区间,此题中该结点所存储的信息就是这段区间的和。

在二叉树中,一个结点 p 的子节点的坐标分别为 p * 2, p * 2 + 1.对于每一段区间,都可以二分去查找两段更小的区间,在不能继续分的时候回溯,更新答案。(具体实现看代码~~)

PS:线段树需要开至少四倍内存,证明部分如下。

树状数组

这个数据结构跟二进制有着莫大的联系,简单的来说,任何一个数都可以用不同的二进制数来表示出来,那么,根据二进制数的01序列,我们来将数组划分。

一个二进制数,从低到高取出每一位1所代表的数字,相加即可得到这个数。

类似的,对于一个想要查询的点,相对应的,如果这个点的二进制位的1上储存的都是各自的前缀和,那么,相加之后得到的结果就是以这个点为右端点的之前所有数的前缀和。(干说比较抽象~~ 看图吧)

再顺便说一句lowbit运算,简单一句话就可以得出一个数二进制位上的最后一位1所代表的的数字。

x & -x

利用 与 运算来求最后一位1,那就要求就是 & 两边的数字只有这一位上的数字相同。由此我们可以直观的想到,将一个数字取反后再加上一的结果与上这一个数字,就可以实现lowbit操作,而在计算机中 -x = ~x + 1 (还是自己推一遍吧hh~~

被高数制裁了一下午~~ 然后过来写这个~~ 最后心态爆炸,WA了好几发~~ 晚上还得写认识实习报告~~ ε=(´ο`*)))唉


Σσ(・Д・;)我我我什么都没做!!!