CPP进阶-树状数组

CPP进阶

树状数组

例题ACWING242

const int N=1e5+5;
typedef long long ll;
int n,m,x;
ll c[N],a[N];

lowbit函数,实际上是查询x在二进制下最后一个1的位数(?)

int lowbit(int x){return x&-x;}

修改

void add(int i,int x)
{
    while(i<=n)
    {
        c[i]+=x;
        i+=lowbit(i);
    }
}

求解

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

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    while(m--)
    {
        char op[2];
        scanf("%s%d",op,&x);
        if(op[0]=='Q')
            printf("%d\n",sum(x)+a[x]);
        else{
            int r,b;
            scanf("%d%d",&r,&b);
            add(x,b);add(r+1,-b);
        }
    }
    return 0;
}