poj 3468-A Simple Proble with Integers(樹状配列解法)

A Simple Proble with Integers
Time Limit: 5000 MS
 
メモリLimit: 131313722 K
Total Submissions: 59247
 
Acceepted: 18032
Case Time Limit: 2000 MS
Description
You have N integers A 1、 A 2,… AN.You need to deal with two kids of operations.One type of operation is to add some given number to each number in a given interval.The other is to ask for the sum of numbers in a given interval.
Input
The first line contains two numbers N and Q.1≦ N,Q ≦100000.The second line contains N numbers,the initial values of A 1、 A 2,… AN.-100000≦ Ai ≤100000万.Each of the next Q LINE represents an operation."C a. b c「means adding」 c to each of Aa、 A+1,… Ab.-10000≦ c ≦10000."Q a. b"means querying the sum of Aa、 A+1,… Ab.
Output
You need to answer all Q command in order.One answer in a line.
Sample Input

10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4

Sample Output

4
55
9
15

ベント
The sums may exceed the range of 32-bit integers.
ソurce
POJ Monthly-207..11.25,Yang Yi
出自するhttp://kenby.iteye.com/blog/962159
n個の数、m回の動作、Q x yの問い合わせ［x,y］の和、C x y bの［x,y］の各数にbを加算する.
まず、1からiの初期値(a配列に記録)、Q x yの和を記録します. sum=a[y]-a[x-1]+S(動作変化の値)は、配列k[],k[i]はiからnまでの全ての値にk[i]を加算することを意味し、C x y bは
:k[x]+b,k[y＋1]-b;S= Sy-S(x-1)Si=a[1]*i+a[2]*(i-1)+.a[i]*1-->> Si=(i＋1)*(k[1]+k[2]+k[3].k[i]-(k[1]*1+k[2]*2+k[3]*3.
これにより、k[1]の累積からk[i]の和を要求するために、k[1]*1がk[i]*iに加算される和に変換され、ツリー配列を用いてlog(n)の時間を求めることができる.

#include 
#include 
#define LL long long int
LL a[100010] , b[100010] , c[100010] ;
int lowbit(int x)
{
    return x & -x;
}
void add(LL *s,int i,int x,int n)
{
    while( i <= n )
    {
        s[i] += x ;
        i += lowbit(i) ;
    }
}
LL get(LL *s,int i)
{
    LL sum = 0;
    while( i )
    {
        sum += s[i] ;
        i -= lowbit(i) ;
    }
    return sum;
}
LL f(int i)
{
    LL sum = a[i] ;
    sum +=  ( (i+1)*get(b,i) - get(c,i) ) ;
    return sum ;
}
int main()
{
    int i , n , m , l , r ;
    LL x , sum ;
    char ch ;
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    memset(c,0,sizeof(c));
    scanf("%d %d", &n, &m);
    for(i = 1 ; i <= n ; i++)
    {
        scanf("%lld", &x);
        a[i] += a[i-1] + x ;
    }
    while(m--)
    {
        getchar();
        scanf("%c", &ch);
        if(ch == 'Q')
        {
            scanf("%d %d", &l, &r);
            sum = f(r) - f(l-1) ;
            printf("%lld
", sum) ;
        }
        else
        {
            scanf("%d %d %d", &l, &r, &x);
            add(b,l,x,n) ;
            add(b,r+1,-x,n);
            add(c,l, x*l ,n);
            add(c,r+1, -(x*(r+1)),n);
        }
    }
    return 0;
}