树状数组模板

海绵猴子 · 2020-04-17 23:01:00 · 个人记录

咕了这么久总算是学了

以前一直觉得会了线段树就没必要学树状数组了

直到……它的出现

something useful

讲的很透彻 (虽然我只是对着他的代码写了一遍而已)

其实需要背的真的只有五六行 怪我以前太懒

时间复杂度O(NlogN)

之后是两种比较经典的题型

以下为单点修改 区间查询模板题P3374的AC代码

#include <bits/stdc++.h>
using namespace std;
int n,m;
const int N=5e5+9;
int a[N],c[N];

int lowbit(int x){
    return x&(-x);
}
void modify(int x,int del){
    while (x<=n){
        c[x]+=del;
        x+=lowbit(x);
    }
}

int ask(int x){
    int sum=0;
    while (x>0){
        sum+=c[x];
        x-=lowbit(x);
    }
    return sum;
}

int main()
{
    memset(a,0,sizeof(a));
    memset(c,0,sizeof(c));
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;++i){
        scanf("%d",&a[i]);
        modify(i,a[i]);
    }
    int tmp,x,y;
    while (m--){
        scanf("%d%d%d",&tmp,&x,&y);
        if (tmp==1){
            modify(x,y);
        }
        else{
            printf("%d\n",ask(y)-ask(x-1));
        }
    }

    return 0;
}

以下为区间修改 单点查询的模板题P3368的AC代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n,m;
const int N=5e5+9;
ll a[N],c[N],d[N];

int lowbit(int x){
    return x&(-x);
}
void modify(int x,ll del){
    while (x<=n){
        c[x]+=del;
        x+=lowbit(x);
    }
}

ll ask(int x){
    ll sum=0;
    while (x>0){
        sum+=c[x];
        x-=lowbit(x);
    }
    return sum;
}

int main()
{
    memset(a,0,sizeof(a));
    memset(c,0,sizeof(c));
    scanf("%d%d",&n,&m);
    d[0]=0;
    for (int i=1;i<=n;++i){
        scanf("%lld",&a[i]);
        d[i]=a[i]-a[i-1];
        modify(i,d[i]);
    }
    int tmp,x,y;
    ll k;
    while (m--){
        scanf("%d",&tmp);
        if (tmp==1){
            scanf("%d%d%lld",&x,&y,&k);
            modify(x,k);
            modify(y+1,-k);
        }
        else{
            scanf("%d",&x);
            printf("%lld\n",ask(x));
        }
    }

    return 0;
}