首页 > 编程语言 > 详细

P3374 【模板】树状数组 1

时间:2020-05-21 21:04:32      阅读:77      评论:0      收藏:0      [点我收藏+]

模板

#include<bits/stdc++.h>
using namespace std;
const int maxn=5*1e5+5;
int tree[maxn];
int n,m,op,a,k;
int lowbit(int x){
    return x&(-x);
}
void add(int x,int k){
    while(x<=n){
        tree[x]+=k;
        x+=lowbit(x);
    }
}
int sum(int x){
    int ans=0;
    while(x!=0){
        ans+=tree[x];
        x-=lowbit(x);
    }
    return ans;
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        scanf("%d",&a);
        add(i,a);
    }

    for(int i=0;i<m;i++){
        cin>>op;
        if(op==1){
            scanf("%d%d",&a,&k);
            add(a,k);
        }
        else{
            scanf("%d%d",&a,&k);
            cout<<sum(k)-sum(a-1)<<endl;
        }
    }
    return 0;
}

 

P3374 【模板】树状数组 1

原文:https://www.cnblogs.com/mohari/p/12933349.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!