网站建设公司哪家比较好,建设一个网站需要什么技术,关于网络营销的论文文献,哪里培训做网站123
二分等差数列求和前缀和数组
题目分析 连续一段的和我们想到了前缀和#xff0c;但是这里的l和r的范围为1e12#xff0c;明显不能用O(n)的时间复杂度去求前缀和。那么我们开始观察序列的特点#xff0c;可以按照等差数列对序列进行分块。如上图#xff0c;在求前10个…123
二分等差数列求和前缀和数组
题目分析 连续一段的和我们想到了前缀和但是这里的l和r的范围为1e12明显不能用O(n)的时间复杂度去求前缀和。那么我们开始观察序列的特点可以按照等差数列对序列进行分块。如上图在求前10个数的和的时候我们可以这样求1312612310123420。我们不需要遍历10次就可以求出来。求前缀和代码如下
sum new long[1500010];
for (int i 1; i 1500000; i) {t i;sum[i] sum[i-1]t;
}这里的t最开始等于1是第一块的数字和然后等于3是第二块数字的和然后等于6是第三块数字的和以此类推。sum[i]表示的是分块后前i块包含数字的和。
我们可以求出前n块数字的和那么我们需要知道第l个数字是在哪一块里面然后求第l个数字是所在块的第几个数字。因为对于最后一块来说不是所有的数字都会被包含进来我们要单独对最后一块求数字和。
第一阶段利用二分求第x个数所在的块 图1
如图1所示我们可以把这个序列分块第一块有1个数第二块有2个数第三块有3个数第四块有4个数每一块拥有数的个数是一个等差数列。现在要找到序列中第x个数所在的块数假设x3那么第x个数在第2块中如果x4那么第x个数在第3块中。求第x个数所在的块数就是求从左往右数前缀和第一个大于等于x的块。
比如第2块的前缀和就是3第三块的前缀和就是5。这个可以用二分去求。 int l 1;int r 1500000;//最多可以分的块数while(l r) {int mid (l r) / 2;if(sum(mid) x) {//求mid个块中包含的数字的个数如果小于x就是不符合条件我要向左找l mid 1;}else {//符合条件我要看前面的块是否也是大于等于x的r mid;}}这里的sum函数的作用就是求前mid块中包含的数字的个数因为是等差数列所以直接用等差数列的求和公式就可以了sum函数如下
private static long sum(long x) { return (1L x) * x / 2;
}第二阶段求前x个数的前缀和
接下来分析二分结束之和我要怎么操作我要求前x个数字的和。 假设x8那么第x个数在第4块中我还要知道第x个数是第4块中的第几个数字。如图第4块有4个数第x个数第4块的第2个数上那么第2个数是怎么来的呢就是x-sum(r-1)8-62。其实就是我二分算出来了第x个数在第r块上那么我只需要把前r-1块包含的数的个数减去就算出来x是在第r块上的第几个数上了。结合上图更好理解。那么前x个数的和就是前r-1块包含数的和加上第r块里面前x-sum(r-1)个数的和。
某一块里面包含的数也是等差数列求前n个数的和依然可以直接用sum(n)去求。而数组sum[r]里面记录的是前r块包含数字值的前缀和。所以二分结束后的代码是这样子的
private static long f(long x) {int l 1;int r 1500000;//最多可以分的块数while(l r) {int mid (l r) / 2;if(sum(mid) x) {//求mid个块中包含的数字的个数l mid 1;}else {r mid;}}//r--是表示完整的块的个数r--;//就是上文里的r-1//x表示x处在他所在块的第几个位置需要减去前面所有块包含的数的个数//本来要求x个数字前r个块中已经包含了sum(r)个数字第r1个块x - sum(r);//前r个块中已经包含了多少个数字return sum[r]sum(x);
}还是对于x8的例子二分求出来r4r–后r3sum[3]10。x-sum(3)8-62。sum[3]sum(2)10313
注意这道题里对于sum函数的多次应用但是不是每一次应用含义都是一样的。因为每一块包含的数字个数是等差数列而每一块内每个数字形成的也是等差数列。
题目代码
import java.util.Scanner;
public class Main {
static long[] sum;
public static void main(String[] args) {Scanner scanner new Scanner(System.in);long t 0;//前缀和的预处理sum new long[1500010];for (int i 1; i 1500000; i) {t i;sum[i] sum[i-1]t;}int n scanner.nextInt();while(n-- 0) {long l scanner.nextLong();long r scanner.nextLong();System.out.println(f(r)-f(l-1));//f(r)求的是序列中前r个数的和}
}
//二分 二分求的是x在哪一块中 n*n-1/2l的第一个n
private static long f(long x) {int l 1;int r 1500000;//最多可以分的块数while(l r) {int mid (l r) / 2;if(sum(mid) x) {//求mid个块中包含的数字的个数l mid 1;}else {r mid;}}//r--是表示完整的块的个数r--;//x表示x处在他所在块的第几个位置需要减去前面所有块包含的数的个数//本来要求x个数字前r个块中已经包含了sum(r)个数字第r1个块x - sum(r);//前r个块中已经包含了多少个数字return sum[r]sum(x);
}
//sum函数求前x块包含的数的个数同时也可以表示某一个块中前x个数的总和
private static long sum(long x) {// TODO Auto-generated method stub return (1L x) * x / 2;
}
}
