POJ 3468 A Simple Problem with Integers

线段树，维护区间的和，支持区间范围修改，注意由于增加的标记传递时是累加起来，结果会超出 int ，要用 long long；

--------------------------------------------------------------

Description

You have N integers, A₁, A₂, ... , A_N. You need to deal with two kinds 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₁, A₂, ... , A_N. -1000000000 ≤ A_i ≤ 1000000000.
Each of the next Q lines represents an operation.
"C a b c" means adding c to each of A_a, A_a₊₁, ... , A_b. -10000 ≤ c ≤ 10000.
"Q a b" means querying the sum of A_a, A_a₊₁, ... , A_b.

Output

You need to answer all Q commands 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

--------------------------------------------------------------

# include <stdio.h>

# define N 100005
# define NON 0

typedef long long int LL;

int n, q, num[N];
LL sum[4 * N], ans;
LL bj[4 * N];

void update(int r)
{
    sum[r] = sum[r << 1] + sum[(r << 1) | 1];
}

void build(int r, int x, int y)
{
    bj[r] = NON;
    if (x == y)
    {
        sum[r] = num[x];
        return ;
    }
    int mid = (x+y) >> 1, ls = r << 1, rs = (r << 1) | 1;
    build(ls, x, mid);
    build(rs, mid+1, y);
    update(r);
}

void pushdown(int r, int x, int y)
{
    if (bj[r] != NON)
    {
        int mid = (x+y) >> 1, ls = r << 1, rs = (r << 1) | 1;
        sum[ls] += (mid-x+1) * bj[r];
        sum[rs] += (y - mid) * bj[r];
        bj[ls] += bj[r], bj[rs] += bj[r], bj[r] = NON;
    }
}

void add(int r, int x, int y, int s, int t, int val)
{
    if (s<=x && y<=t)
    {
        bj[r] += val;
        sum[r] += (y-x+1) * val;
        return ;
    }
    pushdown(r, x, y);
    int mid = (x+y) >> 1, ls = r << 1, rs = (r << 1) | 1;
    if (s <= mid) add(ls, x, mid, s, t, val);
    if (mid+1 <= t) add(rs, mid+1, y, s, t, val);
    update(r);
}

void query(int r, int x, int y, int s, int t, LL &ans)
{
    if (s<=x && y<=t)
    {
        ans += sum[r];
        return ;
    }
    pushdown(r, x, y);
    int mid = (x+y) >> 1, ls = r << 1, rs = (r << 1) | 1;
    if (s <= mid) query(ls, x, mid, s, t, ans);
    if (mid+1 <= t) query(rs, mid+1, y, s, t, ans);
}

void init(void)
{
    for (int i = 1; i <= n; ++i)
        scanf("%d", &num[i]);
    build(1, 1, n);
}

void solve(void)
{
    int s, t, val;
    char str[5];

    for (int i = 1; i <= q; ++i)
    {
        scanf("%s", str);
        switch(str[0])
        {
        case 'C': {scanf("%d%d%d", &s, &t, &val); add(1, 1, n, s, t, val); break;}
        case 'Q': {scanf("%d%d", &s, &t); ans = 0; query(1, 1, n, s, t, ans); printf("%lld\n", ans); break;}
        }
    }
}

int main()
{
    while (~scanf("%d%d", &n, &q))
    {
        init();
        solve();
    }

    return 0;
}

---------------------------------------------------------------