求和问题

问题描述】

在一个长度为n的整数数列中取出连续的若干个数，并求它们的和。

【输入格式】

    输入由若干行组成，第一行有一个整数n
    第二行有n个整数
    第三行有一个整数m
    下面m行，每行两个整数i与j(i<=j)，表示求和的起始和终止位置。

【输出格式】

输出有m行, 每行一个整数，表示这个数段数列的和。

【输入样例】

输入文件

8
2 3 4 7 8 9 10 234
5
2 3
4 7
1 3
7 7
7 8

输出文件

7
34
9
10
244

【数据规模】

对于40%的数据，n<=1000,m<=1000,数列中的数不超过32767，数列的和不超过10^9
对于70%的数据，n<=10000,m<=2*10^5,数列中的数不超过32767
对于100%的数据，n<=10000,m<=2*10^5,数列中的数不超过10^9

简单的前缀和，用longlong就能过完，不用高精度，听说要用dp但是，我不想写。

 1 #include <iostream>
 2 #include <fstream>
 3 #include <cstdlib>
 4 /* run this program using the console pauser or add your own getch, system("pause") or input loop */
 5 using namespace std; 
 6 ifstream fin("sum.in");
 7 ofstream fout("sum.out");
 8 int cnt_num=0;long long int qzhuihe[100005]={0};
 9 int cnt_cha=0;
10 
11 int main(int argc, char *argv[]) {
12 　fin>>cnt_num; for(int x=1;x<=cnt_num;x++){  
13 　　int a;  
14 　　fin>>a;  
15 　　qzhuihe[x]=a+qzhuihe[x-1];      
16 　} 　
17 　fin>>cnt_cha; 
18 　for(int x=1;x<=cnt_cha;x++){
19   　int ks,js;
20   　fin>>ks>>js;
21   　long long ans=qzhuihe[js]-qzhuihe[ks-1];
22 　　 fout<<ans; 
23 　}    
24 return 0;
25 }