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

题目链接
http://codeforces.com/contest/1042/problem/D
题意
就是查询一个数组所区间有和小于t的区间的个数
做法
这类区间和的问题都可以转换为两个前缀和相减的问题，那么我们就可以遍历前缀和数组，求每个位置前面有多少个满足条件的前缀和即可。设当前前缀和为sum2,要寻找的前缀和为sum1,则应该满足$sum2?sum1<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;
}