by hansang:

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e5+10;
const LL P=1e9+9;
int n; LL c[N], a[N], b[N];
void add(LL x, LL w){
    for(int i=x; i<=n; i+=i&-i) c[i]=(c[i]+w)%P;
}
LL query(LL x){
    LL res=0;
    for(int i=x; i>=1; i-=i&-i) res=(res+c[i])%P;
    return res;
}
int main(){
    //freopen("a.in", "r", stdin);
    scanf("%d", &n); a[0]=b[0]=0;
    for(int i=1; i<=n; i++){
        scanf("%lld", &a[i]);
        a[i]+=a[i-1];
        b[i]=a[i];
    }
    sort(b, b+n+1);
    int len=unique(b+1, b+n+1)-b-1;
    for(int i=0; i<=n; i++){
        a[i]=lower_bound(b, b+len+1, a[i])-b+1;
    }
    add(a[0], 1); LL ans=0;
    for(int i=1; i<=n; i++){
        ans=query(a[i]);
        add(a[i], ans);
    }
    printf("%lld\n", ans%P);
    return 0;
}

超时：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5 , P = 1e9+9;
template<typename T>void qr(T& x)
{
	x=0;int f=1;char c=getchar();
	for( ;!isdigit(c);c=getchar())if(c=='-')f=-1;
	for( ; isdigit(c);c=getchar())x=x*10+c-48;
	x=x*f;
}
ll  s[N] , f[N];
int main() {
    int n;qr(n);
    s[0] = 0;
    for(int i = 1 , x; i <= n; i++) qr(x) , s[i] = s[i - 1] + x;
    f[0] = 1;
    for(int i = 1; i <= n; i++)
        if(s[i] >= 0) 
            for (int j=0; j < i; j++) 
                if(s[j] >= 0 && s[i] - s[j] >= 0) 
                    (f[i] += f[j])%=P;
    printf("%lld\n",f[n]);
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5 , P = 1e9 + 9;
template<typename T>void qr(T& x)
{
	x=0;int f=1;char c=getchar();
	for( ;!isdigit(c);c=getchar())if(c=='-')f=-1;
	for( ; isdigit(c);c=getchar())x=x*10+c-48;
	x=x*f;
}
int  n ;
ll a[N] , b[N] , s[N] , f[N] , c[N];
inline void add(int x , ll k)
{
    for( ; x <= n; x += x & -x) c[x] += k;
}
inline ll sum(int x)
{
    ll ans = 0;
    for( ; x; x -= x & -x) ans += c[x];
    return ans;
}
int main() {
    qr(n);
    s[0] = 0;for(int i = 1 , x; i <= n; i++) qr(x) , b[i]=s[i] = s[i - 1] + x;
    sort(b+1,b+n+1);
    int cnt=unique(b+1,b+n+1)-b-1;
    for(int i = 1; i <= n; i++)  a[i] = lower_bound(b+1,b+cnt+1,s[i]) - b;
    for(int i = 1; i <= n; i++)
        if(s[i] >= 0) 
            f[i]=(sum(a[i]) + 1)%P,
            add(a[i],f[i]);
    printf("%lld\n",f[n]);
    return 0;
}