(未完待续)
题目链接:LibreOJ 10113/信息学奥赛一本通 T1535。
题目
题目描述
给定 $n$ 个数列,规定有两种操作,一是修改某个元素,二是求子数列 $[a,b]$ 的连续和。数列元素个数最多 $10^5$ 个,询问操作最多 $10^5$ 次。
题解
思路
这显然是树状数组模板题。
代码
没什么好说的,就看代码吧。
算法的时间复杂度为 $\Theta((n+m)\log _ 2n)$,可以过。
#include<cstdio>
typedef long long ll;
//以上为头文件
const int MAXN=100000+5;//N的最大范围
const int MAXM=100000+5;//M的最大范围
struct TreeArray{//树状数组模板
#define lowbit(x) ( (x)&( - (x) ) )//宏定义lowbit(x)
ll n;
ll unit[MAXN];
void Update(ll ID,ll val){
while(ID<=n){
unit[ID]+=val;
ID+=lowbit(ID);
}
return;
}
ll Query(ll x){
register ll ans=0;
while(x){
ans+=unit[x];
x-=lowbit(x);
}
return ans;
}
ll Query(ll x,ll y){//区间查询
return Query(y)-Query(x-1);
}
};
ll n,m;
TreeArray T;
int main(void){
register ll i;
scanf("%lld%lld",&n,&m);
T.n=n;
for(i=1;i<=n;++i){
static ll a;
scanf("%lld",&a);
T.Update(i,a);
}
for(i=1;i<=m;++i){//m次操作
static ll k,a,b;
scanf("%lld%lld%lld",&k,&a,&b);
if(k==0)
printf("%lld\n",T.Query(a,b));
if(k==1)
T.Update(a,b);
}
return 0;
}
近期评论