1264. 动态求连续区间和(树状数组---某个位置加上一个数/求在线(动态)前缀和/蓝桥杯)
2023-12-17 18:39:32
题目:
输入样例:
10 5
1 2 3 4 5 6 7 8 9 10
1 1 5
0 1 3
0 4 8
1 7 5
0 4 8
输出样例:
11
30
35
?树状数组:
代码:
#include<cstdio>
#include<iostream>
using namespace std;
const int N=100010;
int n,m;
int a[N],tr[N];
//2^k
int lowbit(int x)
{
return x&-x;
}
//改变数组某个值(加上某个值)
void add(int x,int v)
{
for(int i=x;i<=n;i+=lowbit(i))tr[i]+=v;
}
//求动态(在线)前缀和
int query(int x)
{
int res=0;
for(int i=x;i>0;i-=lowbit(i))res+=tr[i];
return res;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<=n;i++)add(i,a[i]);//求得tr[i]
while(m--){
int k,a,b;
scanf("%d%d%d",&k,&a,&b);
if(k==1)add(a,b);
else
printf("%d\n",query(b)-query(a-1));//在线区间和
}
return 0;
}
文章来源:https://blog.csdn.net/asdfghrfh/article/details/135046877
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!