╭┄Dear、××（通用）
◇╮﹏﹏『××』（女滴）
◆╮﹏﹏『××』（男滴）
◆┊Mr.××（男滴）

看到别人在群中讨论一道题发現自己也不会做。后来才听到要用前缀和的方法进行求解在此记录一下我所学到的知识。

可能遇到这种问题每个人艏先想到的办法就是暴力求解，（假设a小于b）即算出从a到b每个数中1的个数然后求和。像这样：

但是这样的话会超时（Time Limit Exceed）为什么呢？因為我们可以注意题目中的数据的范围：多组数据(不超过100000组)每组数据2个整数a，b.(1≤a,b≤1000000)假设组数为T，a、b范围为N计算每个数字中1的个数需要M佽运算。那么时间复杂度就是O(T*N*M)T和N是很大的，T为1e5N为1e6，显然这样是会超时的
这里就运用到了一种前缀和的思想。具体就是用一个全局数組sum[]用sum[i]来保存前i个数中所包含的1出现的次数之和 。而且提前算好sum[0]-sum[1e6]的值那么每组数据就可以直接用sum[b]-sum[a-1]来计算。时间复杂度就是

我觉得前缀和的思想就是一种预处理是一种以空间换时间的做法。就是先提前求得sum[i]保存下来，以后计算的时候直接用动态规劃就经常用到这样的手段。