树状数组

#include<bits/stdc++.h>

using namespace std;

const int N = 100010;
const int M = 100010;

int a[N],tree[N];
int m,n;


int lowbit(int x){
    return x& -x; //算出x的lowbit值,为非负整数x 在二进制表示下 “ 最低位的 1 及其后面的所有的 0 ” 的二进制构成的数值 
}

void add(int x,int v){
    //单点更新数据，若一个节点更改，则他所有的祖先更改，父节点的编号为x + lowbit(x)
    for(int i = x;i <=n ;i+=lowbit(i)) tree[i]+=v; 
}

int query(int x){
    int res = 0;
    for(int i= x;i>0;i-=lowbit(i)){
        res+=tree[i];  //算出前缀和，tree只是某一小段的和，区间大小是【x-lowbit(x),x】，需要将其加起来
    }
    return res;
}

int main(){

    scanf("%d %d",&n,&m);

    for(int i=1;i<=n;i++) scanf("%d",&a[i]);//输入原始数据

    for(int i=1;i<=n;i++) add(i,a[i]);//算出树状数组的数据,在编号为i的节点加a[i]，此时还没求和,从a[1]开始，所有加到a[1]的节点都要加上a[1]


    while(m--){

        int k,x,y;

        scanf("%d%d%d",&k,&x,&y);

        int sum;

        if(k==0){
            sum = query(y) - query(x-1);
            printf("%d\n",sum);
        }else{
            add(x,y);
        }
    }

    return 0;
}

线段树

#include<bits/stdc++.h>

using namespace std;

const int N = 100010;
int w[N];

struct treeNode{
    int l,r;
    int sum;
}tr[4*N];

int n,m;

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{
        tr[u]={l,r};//给节点左右边界赋值
        int mid = (l+r)>>1;//分段构造线段树
        build(u<<1,l,mid);
        build(u<<1|1,mid+1,r);
        pushup(u);//在每构造一个父节点时，都要更新当前的sum值
    }
}

void modify(int u,int x,int v){
    if(tr[u].l ==tr[u].r) tr[u].sum+=v;//若当前为叶子节点
    else{
        int mid = (tr[u].l + tr[u].r) >>1;
        if(x<=mid) modify(u<<1,x,v);//若在左半边修改的
        else modify(u<<1|1,x,v);
        pushup(u);//当前节点信息发生变化
    }
}

int query(int u,int l,int r){
    //判断当前树节点的区间是否完全包含在查询区间内
    if(tr[u].l >= l && tr[u].r <= r ) return tr[u].sum;
    else{
        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;
    }

} 


int main(){
    scanf("%d%d",&n,&m);

    for(int i=1;i<=n;i++){
        scanf("%d",&w[i]);
    }
    build(1,1,n);//构造线段树
    int k,a,b;
    while(m--){


        scanf("%d%d%d",&k,&a,&b);

        if(k==0){
            printf("%d\n",query(1,a,b));
        }else{
            modify(1,a,b);
        }
    }

    return 0;
}