树状数组模板

// 单点更新区间求和  树状数组 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n,c[1000010];
int lowbit(int x){
    return x&(-x);
}
void Add(int x,ll d){
    while(x<=n){
        c[x]+=d;
        x+=lowbit(x);
    }
}
ll sum(int x){
    ll ret=0;
    while(x>=1){
        ret+=c[x];
        x-=lowbit(x);
    }
    return ret;
}
int main(){//数组有n个数 m次操作 
    int i,m;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++){
        ll x;
        scanf("%lld",&x);
        Add(i,x);
    }
    while(m--){
        int num;
        scanf("%d",&num);
        if(num==1){// 第x个数增加k 
            int x;ll k;
            scanf("%d%lld",&x,&k);
            Add(x,k);
        }else{
            int x,y;//求区间x-y的和 
            scanf("%d%d",&x,&y);
            printf("%lld\n",sum(y)-sum(x-1));
        }
    }
    return 0;
}

 

全部评论

相关推荐

菜鸡29号:根据已有信息能初步得出以下几点: 1、硕士排了大本和大专 2、要求会多语言要么是招人很挑剔要么就是干的活杂 3、给出校招薪资范围过于巨大,说明里面的薪资制度(包括涨薪)可能有大坑
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务