洛谷 P3374 【模板】树状数组 1 朴素算法/树状数组/线段树

洛谷 P3374 【模板】树状数组 1   朴素算法/树状数组/线段树

方法一：朴素算法

//洛谷P3374 【模板】树状数组 1
//在线测评地址https://www.luogu.org/problem/P3374
//朴素做法
//感觉long long比较稳妥
//样例通过，提交70分，测试点2,9,10 TLE.2019-11-12
#include <stdio.h>
#define LL long long
#define maxn 500100
int n,m,a[maxn];
int main(){
    int i,cmd,x,y;
    LL ans;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)scanf("%d",&a[i]);
    while(m--){
        scanf("%d%d%d",&cmd,&x,&y);
        if(cmd==1)a[x]+=y;
        else if(cmd==2){
            ans=0;
            for(i=x;i<=y;i++)ans+=a[i];
            printf("%lld\n",ans);
        }
    }
    return 0;
}

方法二：树状数组

//洛谷P3374 【模板】树状数组 1
//在线测评地址https://www.luogu.org/problem/P3374
//朴素做法
//感觉long long比较稳妥
//样例通过，提交70分，测试点2,9,10 TLE.2019-11-12
//在朴素算法基础上改用树状数组算法。2019-11-12
//样例结果输出不正确，排查
//for(i=1;i<=n;i++)scanf("%d",&a),add(i,a);//此处错写成for(i=1;i<=n;i++)scanf("%d",&a[i]);
//样例通过，提交AC.2019-11-12
#include <stdio.h>
#include <string.h>
#define LL long long
#define maxn 500100
int n,m,a;
LL c[maxn];
int lowbit(int x){
    return x&-x;
}
void add(int x,int delta){
    while(x<=n)c[x]+=delta,x+=lowbit(x);
}
LL sum(int x){
    LL ret=0;
    while(x>0)ret+=c[x],x-=lowbit(x);
    return ret;
}
int main(){
    int i,cmd,x,y;
    memset(c,0,sizeof(c));
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)scanf("%d",&a),add(i,a);//此处错写成for(i=1;i<=n;i++)scanf("%d",&a[i]);
    while(m--){
        scanf("%d%d%d",&cmd,&x,&y);
        if(cmd==1)add(x,y);
        else if(cmd==2)printf("%lld\n",sum(y)-sum(x-1));
    }
    return 0;
}

方法三：线段树

//洛谷P3374 【模板】树状数组 1
//在线测评地址https://www.luogu.org/problem/P3374
//朴素做法
//感觉long long比较稳妥
//样例通过，提交70分，测试点2,9,10 TLE.2019-11-12
//在朴素算法基础上改用树状数组算法。2019-11-12
//样例结果输出不正确，排查
//for(i=1;i<=n;i++)scanf("%d",&a),add(i,a);//此处错写成for(i=1;i<=n;i++)scanf("%d",&a[i]);
//样例通过，提交AC.2019-11-12
//尝试线段树
//编写过程中，还是有些疙瘩，已在代码中体现。
//样例通过，提交AC.2019-11-12
//编写的难度来说，线段树是要大些。建议读者在编写过程中，画出线段树，对着进行编码，才能快速解决许多细节问题。
#include <stdio.h>
#define LL long long
#define maxn 500100
#define lson k<<1
#define rson k<<1|1
int n,m;
struct node{
    int l,r;
    LL v;
}a[maxn<<2];
void pushup(int k){
    a[k].v=a[lson].v+a[rson].v;
}
void build(int k,int l,int r){
    int mid=(l+r)/2;
    a[k].l=l,a[k].r=r;//漏了此行。
    if(l==r){
        scanf("%lld",&a[k].v);
        return;
    }
    build(lson,l,mid);
    build(rson,mid+1,r);
    pushup(k);
}
void update(int k,int l,int r,int delta){
    int mid=(a[k].l+a[k].r)/2;
    if(l<=a[k].l&&a[k].r<=r){
        a[k].v+=delta;
        return ;
    }
    if(l<=mid)update(lson,l,r,delta);
    if(mid+1<=r)update(rson,l,r,delta);
    pushup(k);//漏了此句
}
LL query(int k,int l,int r){
    int mid=(a[k].l+a[k].r)/2;
    LL ans=0;
    if(l<=a[k].l&&a[k].r<=r)return a[k].v;
    if(l<=mid)ans+=query(lson,l,r);
    if(mid+1<=r)ans+=query(rson,l,r);
    return ans;
}
int main(){
    int i,cmd,x,y;
    scanf("%d%d",&n,&m);
    build(1,1,n);
    while(m--){
        scanf("%d%d%d",&cmd,&x,&y);
        if(cmd==1)update(1,x,x,y);
        else if(cmd==2)printf("%lld\n",query(1,x,y));
    }
    return 0;
}