蓝桥杯——123

123

二分+���差数列求和+前缀和数组

题目分析

连续一段的和我们想到了前缀和，但是这里的l和r的范围为1e12，明显不能用O(n)的时间复杂度去求前缀和。那么我们开始观察序列的特点，可以按照等差数列对序列进行分块。如上图，在求前10个数的和的时候，我们可以这样求1+3（1+2）+6（1+2+3）+10（1+2+3+4）=20。我们不需要遍历10次就可以求出来。求前缀和代码如下

sum = new long[1500010];for (int i = 1; i     t += i;    sum[i] = sum[i-1]+t;}        int mid = (l + r) / 2;        if(sum(mid)