51Nod 1081 子段求和(树状数组模板)
程序员文章站
2022-05-11 17:05:14
...
1081 子段求和
给出一个长度为N的数组,进行Q次查询,查询从第i个元素开始长度为l的子段所有元素之和。
例如,1 3 7 9 -1,查询第2个元素开始长度为3的子段和,1 {3 7 9} -1。3 + 7 + 9 = 19,输出19。
收起
输入
第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)
输出
共Q行,对应Q次查询的计算结果。
输入样例
5 1 3 7 9 -1 4 1 2 2 2 3 2 1 5
输出样例
4 10 16 19
树状数组:
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <set>
#include <cstring>
#include <stack>
#include <vector>
#include <queue>
#define Swap(a,b) a ^= b ^= a ^= b
using namespace std ;
typedef long long LL;
const int MAX = 50005;
const int inf = 0xffffff;
const LL mod = 1e9+7 ;
int minn = 0x3f3f3f3f ;
int maxx = -0x3f3f3f3f;
// --------------------------------
int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int n ;
LL c[MAX] ; // 树状数组
//int a[MAX] ; // 原数组
LL lowbit(LL x ) { return x&(-x);}
void update(int i,LL v){ // 单点更新
while(i<=n){
c[i]+=v;
i+=lowbit(i);// 由叶子节点向上更新树状数组 , 从左到右
}
}
LL sum(int i){
LL ans = 0 ;
while(i>0){
ans+=c[i];// 从右到左累加求和
i-=lowbit(i) ;
}
return ans ;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL),cout.tie(NULL);
cin >>n ;
int m ;
for(int i =1 ; i<= n ;i++)
{
LL x ;
cin >>x;
update(i,x);
}
cin >> m ;
while(m--)
{
int s , l ; // 开始 和 长度
cin >> s >>l ;
int e = s+l-1 ;
cout<<sum(e)- sum(s-1)<<endl;
}
return 0;
}
上一篇: php变量-单引号不编译,双引号编译
下一篇: iframe实现伪AJAX无刷新文件上传