（未完待续）

题目链接：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;
}