动态求区间和

复杂度mlogn
question
树状数组做法

#include<iostream>
using namespace std;
const   int N=100010;
int tr[N],w[N];
int n,m; int lowbit(int x)
{
   
    return x&-x;
}
void add(int a,int b)
{
   
    for(int i=a;i<=n;i+=lowbit(i))
    tr[i]+=b;
}
int query(int a)
{
   
    int res=0;
    for(int i=a;i;i-=lowbit(i))
    res+=tr[i];
    return res;
}
int main()
{
   
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    cin>>w[i];
    for(int i=1;i<=n;i++)
    add(i,w[i]); while(m--)
    {
   
        int k,a,b;
        cin>>k>>a>>b; if(k==0)
        {
   
            printf("%d\n",query(b)-query(a-1));   
        }
        else
        {
   
            add(a,b);
        }
    }
    return 0;
}

线段树做法

#include<iostream>
using namespace std;
const   int N=100010; struct node{
   
    int l;
    int r;
    int sum;
}tr[N*4];
int w[N]; void pushup(int u)
{
   
    tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
}
void build(int u,int l,int r)
{
   
    if(l==r)
    {
   
        tr[u]={
   l,r,w[l]};
    }
    else
    {
   
        int mid=(l+r)>>1; tr[u]={
   l,r};
        build(u<<1,l,mid);
        build(u<<1|1,mid+1,r);
        pushup(u);
    }
}
int query(int u,int l,int r)
{
   
    if(l<=tr[u].l&&r>=tr[u].r)
    return tr[u].sum;
    int mid=tr[u].l+tr[u].r>>1;
    int sum=0;
    if(l<=mid)  sum+=query(u<<1,l,r);
    if(r>mid)   sum+=query(u<<1|1,l,r);
    return sum;
}
void modify(int u,int a,int b)
{
   
    if(tr[u].l==tr[u].r)
    tr[u].sum+=b; else
    {
   
        int mid=tr[u].l + tr[u].r>>1;
        if(a<=mid)  modify(u<<1,a,b);
        else    modify(u<<1|1,a,b);
        pushup(u);
    }
}
int main()
{
   
    int m,n;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    cin>>w[i];
    build(1,1,n); while(m--)
    {
   
        int k,a,b;
        cin>>k>>a>>b; if(k==0)
        {
   
            printf("%d\n",query(1,a,b))   ;
        }
        else
            modify(1,a,b);
    }
    return 0;
}