zufe 神奇的序列计算 (树状数组)

树状数组)"/>

zufe 神奇的序列计算 (树状数组)

树状数组维护一下增加的值！！好题啊

Description

小胖是一个数学爱好者，他总是喜欢提出一些奇怪的问题，给出一个长度为N的序列，每次提出l,r（1<=l<=r<=N）,要求求出
a[l]*1+a[l+1]*2+...+a[r]*(r-l+1)的值(序列中数字均大于等于0)，其中1<=N<=100000,询问共M次，1<=M<=100000，询问操作有两种，第一种为更新序列，
形式如：add X 表示a[x]的值增加1，第二种为query L R  表示询问L，R区间的值，求和方式如上面所描述的(所有输入都在整数范围内)。

Input

第一行输入N，M，N为序列大小，M为询问个数。接下来一行为N个数字，表示初始序列。接下来M行，每行开头为一个字符串，如果字符串为
add，则为增加操作，那么之后有一个数字X，表示要增加1的序列下标。如果为query,后面有两个数字 L，R，表示要询问L，R区间的和。
这里由于答案会比较大，我们要求输出答案对1000000007取余。

Output

对于query的询问，输出一个数字，表示得到的答案对1000000007取余的结果。

Sample Input

5 4
1 2 3 4 5
query 1 2
query 3 4
add 1
query 1 2

Sample Output

5
11
6

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const LL maxn=100000+100;
const LL mod=1000000007;
char str[10];
LL sum[maxn],bit1[maxn],bit2[maxn],n,a[maxn],pre[maxn]; // sum系数和， pre 求1的和 
LL sum1(int i) // 求1的和 
{LL s=0;while(i>0) {s=(s+bit1[i])%mod;i-=i&(-i);} return s;
}
void add1(int i,LL x)
{while(i<=n) {bit1[i]=(bit1[i]+x)%mod;i+=i&(-i);}
}LL sum2(int i)   //求系数之和 
{LL s=0;while(i>0) {s=(s+bit2[i])%mod;i-=i&(-i);} return s;
}
void add2(int i,LL x)
{while(i<=n) {bit2[i]=(bit2[i]+x)%mod;i+=i&(-i);}
}int main()
{int m,t;LL l,r,t1,t2,ans,i,j;while(scanf("%lld%d",&n,&m)!=EOF) {memset(sum,0,sizeof(sum));memset(bit1,0,sizeof(bit1));memset(bit2,0,sizeof(bit2));memset(pre,0,sizeof(pre));for(i=1;i<=n;i++) {scanf("%lld",&a[i]);a[i]=a[i]%mod;sum[i]=(sum[i-1]+a[i]*i%mod)%mod;pre[i]=(pre[i-1]+a[i])%mod;}while(m--) {scanf("%s",str);if(strcmp(str,"query")==0) {scanf("%lld%lld",&l,&r);t1=(sum[r]-sum[l-1]+mod-(pre[r]-pre[l-1])*(l-1)%mod+mod)%mod;t2=(sum2(r)-sum2(l-1)+mod-(sum1(r)-sum1(l-1))*(l-1)%mod+mod)%mod;ans=(t1+t2)%mod;printf("%lld\n",ans);}else {scanf("%d",&t);add1(t,LL(1));add2(t,LL(t));}}}return 0;
}