树状数组TLE,求调
  • 板块P2068 统计和
  • 楼主CW_shy
  • 当前回复3
  • 已保存回复3
  • 发布时间2023/8/23 09:19
  • 上次更新2023/11/3 01:50:38
查看原帖
树状数组TLE,求调
602793
CW_shy楼主2023/8/23 09:19
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const long long N=1e5+5;
char s;
ll n,w,tree[N],xx,yy;
ll lowbit(ll x) {return (x)&(-x);}
void update(ll id,ll x)
{
    for(int pos=id;pos<=n;pos+=lowbit(pos)) tree[pos]+=x;
}
ll query(ll x)
{
    ll sum=0;
    for(int pos=x;pos;pos-=lowbit(x))
    {
        sum+=tree[pos];
    }
    return sum;
}
int main()
{
    scanf("%lld%lld",&n,&w);
    while(w--)
    {
        cin>>s;
        scanf("%lld%lld",&xx,&yy);
        if(s=='x') update(xx,yy);
        else printf("%lld\n",query(yy)-query(xx-1));
    }
    return 0;
}
2023/8/23 09:19
加载中...