树状数组

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=100010;
int a[N],tr[N];
//tr[]数组 为树状数组
int n,m;
//最后由k个连续的0，就返回2^k
int lowbit(int i)
{
    return i&-i;
}
//树状数组的+操作 将x位置上的数+上y
void add(int x,int y)
{
    for(int i=x;i<=n;i+=lowbit(i))
    {
        tr[i]+=y;
    }
}
//求和以 1到x区间的和
int query(int n)
{
    int ret=0;
    for(int i=n;i>=1;i-=lowbit(i))
    {
        ret+=tr[i];
    }
    return ret;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        add(i,a[i]);
    }
    while(m--)
    {
        int k,a,b;
        cin>>k>>a>>b;
        if(k==0)printf("%d\n",query(b)-query(a-1));
        if(k==1)add(a,b);
    }
    return 0;
}

线段树

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=100010;
int a[N];
struct node{
    int l,r;
    int sum;
}tr[4*N];
int n,m;
//pushup 求x这个节点的权值=左儿子的权值+右儿子的权值
void pushup(int u)
{
    tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
}
//建立l ~ r 的线段树
void build(int u,int l,int r)
{
    //如果l==r 说明这个区间已经不能再分(长度为1)
    //直接给它赋值
    if(l==r)tr[u]={l,r,a[l]};
    else
    {
        //不是叶子节点 先给他的l r 当前l r
        tr[u]={l,r,0};
        int mid=(tr[u].l+tr[u].r)>>1;
        //递归分出 左边 右边
        build(u<<1,l,mid),build(u<<1|1,mid+1,r);
        //递归结束后回溯算出 每个父亲的区间和
        pushup(u);
    }
}
//查询函数 给定根节点 查询l~r这个子区间的和
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].l==a)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()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    //建立线段树
    build(1,1,n);

    int k,a,b;
    while(m--)
    {
        cin>>k>>a>>b;
        if(k==0)cout<<query(1,a,b)<<endl;
        //输入 根节点 区间左端点 区间右端点
            //求出[l,r]区间和
        if(k==1)modify(1,a,b);
        //输入根节点 位置 x 加上y
    }
    return 0;
}