【51Nod】1081 子段求和
程序员文章站
2022-05-11 17:04:26
...
题意
给出一个长度为N的数组,进行Q次查询,查询从第i个元素开始长度为l的子段所有元素之和。
例如,1 3 7 9 -1,查询第2个元素开始长度为3的子段和,1 {3 7 9} -1。3 + 7 + 9 = 19,输出19。
解题思路
线段树求区间和
参考代码
#include <iostream>
using namespace std;
#define MAXN 50000+1
typedef long long ll;
struct Node{
int l,r;
ll x;
}tree[4*MAXN];
void build(int node,int l,int r){
tree[node].l=l,tree[node].r=r;
if (l==r){
cin>>tree[node].x;
return;
}
int mid=(l+r)/2;
build(node*2,l,mid);
build(node*2+1,mid+1,r);
tree[node].x=tree[node*2].x+tree[node*2+1].x;
}
ll query(int node,int l,int r){
if (l<=tree[node].l && tree[node].r<=r)
return tree[node].x;
int mid=(tree[node].l+tree[node].r)/2;
if (r<=mid) return query(node*2,l,r);
else if (l>mid) return query(node*2+1,l,r);
else return query(node*2,l,mid)+query(node*2+1,mid+1,r);
}
int main(){
int n,q,i,l;
while (cin>>n){
build(1,1,n);
cin>>q;
while (q--){
cin>>i>>l;
cout<<query(1,i,i+l-1)<<endl;
}
}
return 0;
}