区修单查：

Description

给你N个整数A[1], A[2], … , A[N]。你需要处理两类问题：
　　 “C a b c”表示给A[a], A[a+1], … , A[b]之间的每个数都加上c(-10000≤c≤10000)。
　　 “Q a”表示询问数列中第x个数的值；

Input

输入的第一行包含两个整数N和Q(1≤N,Q≤100000)；
　　第二行包含N个整数Ai(-10^9≤Ai≤10^9)
　　接下来Q行，表示Q个问题，形式如题；

Output

输出要求计算出的区间总和，每行一个。

Sample Input

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

Sample Output

4
1
2
5

c++代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
long long n,q,a[100005],sum1[100005],sum2[100005];
long long lowbit(long long x){return x&(-x);}
void add(long long x,long long d)
{
    for(long long i=x;i<=n;i+=lowbit(i))
    {
        sum1[i]+=d;//维护前缀和c[i] 
        sum2[i]+=d*(x-1);//维护前缀和c[i] * (i-1)
    }
}
long long ask(int x)
{
    long long ans=0;
    for(long long i=x;i>0;i-=lowbit(i)) ans+=x*sum1[i]-sum2[i];//通项公式 
    return ans;
}
int main()
{
    scanf("%lld%lld",&n,&q);
    for(int i=1;i<=n;++i)
    {
        scanf("%lld",&a[i]);
        add(i,a[i]-a[i-1]);//维护差分数组 
    }
    while(q--)
    {
        char f; long long f1,f2,f3; cin>>f;
        if(f=='Q')
        {
            scanf("%lld%lld",&f1,&f2);
            printf("%lld\n",ask(f2)-ask(f1-1));
        }
        else if(f=='C')
        {
            scanf("%lld%lld%lld",&f1,&f2,&f3);
            add(f1,f3); add(f2+1,-f3);
        }
    }
    return 0;
}

区修区查：

Description

给你N个整数A[1], A[2], … , A[N]。你需要处理两类问题：
　　 “C a b c”表示给A[a], A[a+1], … , A[b]之间的每个数都加上c(-10000≤c≤10000)。
　　 “Q a b”求A[a], A[a+1], … , A[b]之间数字的总和；

Input

输入的第一行包含两个整数N和Q(1≤N,Q≤100000)；
　　第二行包含N个整数Ai(-10^9≤Ai≤10^9)
　　接下来Q行，表示Q个问题，形式如题；

Output

输出要求计算出的区间总和，每行一个。

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

附 :注意开long long，输入输出lld

C++ 代码

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
long long n,q,a[100005],sum1[100005],sum2[100005];
long long lowbit(long long x){return x&(-x);}
void add(long long x,long long d)
{
    for(long long i=x;i<=n;i+=lowbit(i))
    {
        sum1[i]+=d;//维护前缀和c[i] 
        sum2[i]+=d*(x-1);//维护前缀和c[i] * (i-1)
    }
}
long long ask(int x)
{
    long long ans=0;
    for(long long i=x;i>0;i-=lowbit(i)) ans+=x*sum1[i]-sum2[i];//通项公式 
    return ans;
}
int main()
{
    scanf("%lld%lld",&n,&q);
    for(int i=1;i<=n;++i)
    {
        scanf("%lld",&a[i]);
        add(i,a[i]-a[i-1]);//维护差分数组 
    }
    while(q--)
    {
        char f; long long f1,f2,f3; cin>>f;
        if(f=='Q')
        {
            scanf("%lld%lld",&f1,&f2);
            printf("%lld\n",ask(f2)-ask(f1-1));
        }
        else if(f=='C')
        {
            scanf("%lld%lld%lld",&f1,&f2,&f3);
            add(f1,f3); add(f2+1,-f3);
        }
    }
    return 0;
}