这两个技巧的意义在于能够把一段连续的区间操作简化为两个数字的操作:

注意 事项:有可能出现空间复杂度不够用,前缀和和原本数组可以是一个数组

前缀和

激光炸弹

依次枚举每个正方形就可以,而一个正方形是可以被左上方的点和右下方的点来唯一确定,依次枚举左上点的坐标和右下方 的坐标,这个题目还有一个坑点在于如果刚上来r的范围就巨大,机会出现没有办法枚举,所以提前写好判断,如果说r特别大,直接输出最后一个前缀和就可以

差分:

问题情景:我有一段序列,我需要对这段序列的每个数字都加

上一个数字,序列长度:100000,我会进行多次操作,如果直接朴素循环, 对于一个长度100000的数列,我的询问次数也是100000,询问次数乘以长度是1e10,时间上过不去,我假设我操作的数组是前缀和,那么一段区间加上一个数字,可以很方便的转换为差分数组对一个数字进行操作,等操作完成之后我们再对于原数组进行复原就可以了

0 条评论

目前还没有评论...