P3374 【模板】树状数组 1

wflengxuenong · 2023-11-26 17:45:04 · 个人记录

线段树写法。tzt模板。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
struct node
{
    int l,r,w;
}a[1000001];
int aa[600000],n,m,t=1;
void build(int u,int l,int r)//建立线段树！！！ 
{
    if(l==r)
        a[u].w=aa[l];
    else
    {
        int mid=(l+r)/2;
        a[u].l=++t; 
        build(a[u].l,l,mid);
        a[u].r=++t;
        build(a[u].r,mid+1,r);
        a[u].w=a[a[u].r].w+a[a[u].l].w;
    }
}
void update(int u,int l,int r,int x,int k)//进行单点修改 
{
    if(l==r)
    {
        a[u].w+=k;
    }
    else
    {
        int mid=(l+r)/2;;
        if(x<=mid)update(a[u].l,l,mid,x,k);
        else update(a[u].r,mid+1,r,x,k);
            a[u].w=a[a[u].l].w+a[a[u].r].w;
    }
} 
int query(int u,int l,int r,int ll,int rr)
{
    int ans=0;
    if(l>=ll&&r<=rr)
    {
        return ans+=a[u].w;
    }
    else
    {
        int mid=(l+r)/2;
        if(rr>mid)ans+=query(a[u].r,mid+1,r,ll,rr);
        if(ll<=mid)ans+=query(a[u].l,l,mid,ll,rr);
        return ans;
    }
} 
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)scanf("%d",&aa[i]);
    build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        int u,x,k;
       // cin>>u>>x>>k;
        scanf("%d%d%d",&u,&x,&k);
        if(u==1)
            update(1,1,n,x,k);
        else
            printf("%d\n",query(1,1,n,x,k));
    } 
}