首页 > 代码库 > 常用优化

常用优化

优化一:预处理优化
预处理优化之——前缀和优化:
非常常见的优化方式。此处的前缀和指某数组的前i项和。
如给定数组a[n],求sum[n]。其中sum[i]=a[0]+a[1]+...+a[i]
这里的sum[]数组即为数组a的前缀和数组。
那么前缀和有什么用处呢?
假设我要求a[x]+a[x+1]+a[x+2]+...+a[y]
那么这个答案就等于 sum[y]-sum[x-1](x!=0)。若x=0则等于sum[y]。
有一点:如果原数组的数字是非负的,那么sum数组则是非递减的,在搜索的时候可以考虑使用二分。

其他预处理优化。
预处理根据题目需要求的问题,事先处理好保存起来,解决问题的时候可能需要多次使用,这样的话,只需要计算一遍,不用每次需要用的时候重复计算。

优化二:离线处理
解决问题时可能会需要很多问题的答案,而这些问题是无序的。但是假如这些问题是有序的,可以一次性直接处理出结果。那么我们可以先将询问排序,然后一次性处理出所有结果,然后再将结果按照询问的顺序给出。
总的来说,离线处理即预先保存好所有询问,然后一次性给出所有结果。
当然这么做的前提是能提高效率。

常用优化