树状数组超时,求助qaq(
查看原帖
树状数组超时,求助qaq(
322896
xixi_bang楼主2020/5/16 01:39

还有萌新刚开始用快读,但是我发现读取总是有问题啊,是不是我函数read()出现了问题啊QAQ

#include<iostream>
#include<stdio.h>
using namespace std;
const int N=5e5+3;
int k[N];
int n,m;

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

int read(){
    char c=getchar();
    int f=1,x=0;
    while(c>'9'||c<'0'){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x>>3)+(x>>1)+c-'0';
        c=getchar();
    }
    return x*f;
}

void add(int a,int b){
    for(int i=a;i<=n;i=i+lowbit(i)){
        k[i]+=b;
    }
}

int qury(int a){
    int ans=0;
    for(int i=a;i;i=i-lowbit(i)){
        ans+=k[i];
    }
    return ans;
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        add(i,x);//建立树状数组的时候也必须通过add操作
    }
    for(int i=1;i<=m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        if(a==1){
            add(b,c);
        }
        else{
            cout<<qury(c)-qury(b-1)<<endl;
           // printf("%d\n",);
        }
    }
}
2020/5/16 01:39
加载中...