树状数组-单点查询算法

原题P3374

lowbit()将某数在二进制下的高位1去掉，只剩最后一个最低位1。

例如 lowbit(3₁₀(101₂)) = 1₁₀(001₂)

那么，若有一个数组a[n]，它的前缀和的树状数组为t

那么

while(j<=n){

        t[j]+=a[i];

        j+=lowbit(j);//跳转到需要此值的地方

    }

（初始化）

若我们需要a[i] + a[i + 1] + · · · + a[j]，

则需要

    i--;//因为我们不能舍弃a[i]所以减1

    while(x){//寻找a[1]+a[2]+···+a[i-1]

        x_sum+=t[x];

        x-=lowbit(x);

    }

    while(y){//寻找a[1]+a[2]+···+a[j]

        y_sum+=t[y];

        y-=lowbit(y);

    }

    return y_sum-x_sum;

代码

#include<bits/stdc++.h>

int n,m,t[500002];

int lowbit(int k){

    return k&-k;

}

void add(int x,int y){

    while(x<=n){

        t[x]+=y;

        x+=lowbit(x);

    }

    return;

}

int sum(int x,int y){

    int x_sum=0,y_sum=0;

    x--;

    while(x){

        x_sum+=t[x];

        x-=lowbit(x);

    }

    while(y){

        y_sum+=t[y];

        y-=lowbit(y);

    }

    return y_sum-x_sum;

}

int main(){

    scanf("%d%d",&n,&m);

    for(int i(1);i<=n;i++){

        int in;

        scanf("%d",&in);

        add(i,in);

    }

    for(int i(1);i<=m;i++){

        int c,a,b;

        scanf("%d%d%d",&c,&a,&b);

        if(c==1){

            add(a,b);

        }else{

            printf("%d\n",sum(a,b));

        }

    }

    return 0;

}