本文主要是介绍51Nod-1081 子段求和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1081 子段求和 
基准时间限制：1 秒 空间限制：131072 KB 分值: 0 难度：基础题
给出一个长度为N的数组，进行Q次查询，查询从第i个元素开始长度为l的子段所有元素之和。
例如，1 3 7 9 -1，查询第2个元素开始长度为3的子段和，1 {3 7 9} -1。3 + 7 + 9 = 19，输出19。
Input
第1行：一个数N，N为数组的长度(2 <= N <= 50000)。 第2 至 N + 1行：数组的N个元素。(-10^9 <= N[i] <= 10^9) 第N + 2行：1个数Q，Q为查询的数量。 第N + 3 至 N + Q + 2行：每行2个数，i，l（1 <= i <= N，i + l <= N)
Output
共Q行，对应Q次查询的计算结果。
Input示例
5 1 3 7 9 -1 4 1 2 2 2 3 2 1 5
Output示例
4 10 16 19
连续子段求和，树状数组是极为方便的，插线取点
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;int n;
long long a[50010];int lowbit( int x ){return x & -x;
}void add( int pos , long long val ){while( pos<=n ){a[pos] += val;pos += lowbit(pos);}
}long long query( int pos ){if( pos==0 )return 0;long long sum = 0;while( pos>0 ){sum += a[pos];pos -= lowbit(pos);}return sum;
}int main(){
// freopen( "in.txt","r",stdin );while( ~scanf( "%d",&n ) ){int val;for( int i=1 ; i<=n ; i++ ){ scanf( "%lld",&val );add( i,val );}int q,s,e;scanf( "%d",&q );for( int i=0 ; i<n ; i++ ){scanf( "%d %d",&s,&e );printf( "%lld\n",query(s+e-1)-query(s-1) );} }return 0;
}
这篇关于51Nod-1081 子段求和的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
