【Codeforces Round #510 (Div. 2) D.Petya and Array】 树状数组

题目链接
http://codeforces.com/contest/1042/problem/D
题意
就是查询一个数组所区间有和小于t的区间的个数
做法
这类区间和的问题都可以转换为两个前缀和相减的问题，那么我们就可以遍历前缀和数组，求每个位置前面有多少个满足条件的前缀和即可。设当前前缀和为sum2,要寻找的前缀和为sum1,则应该满足$sum2-sum1&lt;t$sum2−sum1<t,所以有$sum1&gt;sum2-t$sum1>sum2−t ，于是我们只要统计之前有多少个前缀和满足这个条件即可，由于这道题会出现负数，我们要整体加上一个BASE，树状数组可能会开到2e14，但实际用到的数组却不多，所以我们可以用map来保存，也就避免了离散化。
代码

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
typedef long long ll;
const int maxn = 2e5+10;
const ll MAX = 2e14+10;
map<ll,int>mp;
ll lowbit(ll x)
{
    return x&(-x);
}
void add(ll x)
{
    while(x<=2LL*MAX)
    {
        mp[x]++;
        x+=lowbit(x);
    }
    return ;
}
ll GetSum(ll x)
{
    ll ans=0;
    while(x>0)
    {
        ans+=mp[x];
        x-=lowbit(x);
    }
    return ans;
}
ll a[maxn];
int main()
{
    int n;
    ll t;
    scanf("%d%lld",&n,&t);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        a[i]=a[i]+a[i-1];
    }
    ll ans=0;
    add(MAX);
    for(int i=1;i<=n;i++)
    {
        ll tmp2=GetSum(a[i]-t+MAX);
        ans+=(i-tmp2);
        add(a[i]+MAX);
    }
    printf("%lld\n",ans);
    return 0;
}