時(shí)間限制：1.2 s?? 內(nèi)存限制：128 MB

【問(wèn)題描述】 在一個(gè)長(zhǎng)度為n的整數(shù)數(shù)列中取出連續(xù)的若干個(gè)數(shù)，并求它們的和。 【輸入格式】 輸入由若干行組成，第一行有一個(gè)整數(shù)n
??? 第二行有n個(gè)整數(shù)
??? 第三行有一個(gè)整數(shù)m
??? 下面m行，每行兩個(gè)整數(shù)i與j(i<=j)，表示求和的起始和終止位置。 【輸出格式】

??? 輸出有m行, 每行一個(gè)整數(shù)，表示這個(gè)數(shù)段數(shù)列的和。

【輸入樣例】 輸入文件 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 【數(shù)據(jù)規(guī)?！?對(duì)于40%的數(shù)據(jù)，n<=1000,m<=1000,數(shù)列中的數(shù)不超過(guò)32767，數(shù)列的和不超過(guò)10^9
對(duì)于70%的數(shù)據(jù)，n<=10000,m<=2*10^5,數(shù)列中的數(shù)不超過(guò)32767
對(duì)于100%的數(shù)據(jù)，n<=10000,m<=2*10^5,數(shù)列中的數(shù)不超過(guò)10^9 線段樹(shù)區(qū)間求和? 屠龍寶刀點(diǎn)擊就送 #include <cstdio>using namespace std;typedef long long LL; struct node {LL l,r,dis; }tree[1000001]; LL ans,u,v,m,n,i,j; void up(LL now) {tree[now].dis=tree[now*2].dis+tree[now*2+1].dis; } void read(LL &x) {x=0;LL f=1;char ch=getchar();while(ch>'9'||ch<'0'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+(LL)ch-48;ch=getchar();}x=x*f; } void build(LL l,LL r,LL now) {tree[now].l=l;tree[now].r=r;if(tree[now].l==tree[now].r){read(tree[now].dis);return;}LL mid=(l+r)>>1;build(l,mid,now*2);build(mid+1,r,now*2+1);up(now); } void query(LL now) {if(tree[now].l>=u&&tree[now].r<=v){ans+=tree[now].dis;return;}LL m=(tree[now].l+tree[now].r)>>1;if(u<=m) query(now<<1);if(v>m) query(now<<1|1); } int main() {freopen("sum.in","r",stdin);freopen("sum.out","w",stdout);read(n);build(1,n,1);read(m);while(m--){read(u);read(v);ans=0;query(1);printf("%lld\n",ans);}fclose(stdin);fclose(stdout);return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/ruojisun/p/6506345.html

總結(jié)

以上是生活随笔為你收集整理的COGS 36. 求和问题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。