线段树·POJ-3468·区间加减区间求和

题目大意：两种操作：

C a b c  a-b区间加上c；

Q查询区间和；

解题思路：

基本的线段树模板，唯一要提的就是和HDU-1698相比，lazy标记的处理不一样，这题需要区间加减，所以向下传递的时候需要加点，而HDU-1698是区间替换，只需要用lazy标记替换下一个即可；

AC代码：

#include <map>
#include <set>
#include <stack>
#include <cmath>
#include <queue>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <fstream>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
#pragma comment(linker, "/STACK:1024000000,1024000000")

using namespace std;
#define   maxn          1010
#define lson l , m , rt << 1

#define rson m + 1 , r , rt << 1 | 1
#define   ms(x,y)      memset(x,y,sizeof(x))
#define   rep(i,n)      for(int i=0;i<(n);i++)
#define   repf(i,a,b)   for(int i=(a);i<=(b);i++)
#define   PI           pair<int,int>
//#define   mp            make_pair
#define   FI            first
#define   SE            second
#define   IT            iterator
#define   PB            push_back
#define   Times         10
typedef   long long     ll;
typedef   unsigned long long ull;
typedef   long double   ld;
typedef   pair<int ,int > P;
//#define N 100
const double eps = 1e-10;
const double  pi = acos(-1.0);
const  ll    mod = 1e9+7;
const  int   inf = 0x3f3f3f3f;
const  ll    INF = (ll)1e18+300;
const int   maxd = 101000 + 10;

int ac[maxd];
ll sum[maxd<<2];
ll add[maxd<<2];
void push_up(int rt) {
    sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}
void push_down(int rt, int m) {
    if(add[rt]) {
        add[rt<<1] += add[rt];
        add[rt<<1|1] += add[rt];
        sum[rt<<1] += add[rt]*(m - (m>>1));
        sum[rt<<1|1] += add[rt] * (m>>1);
        add[rt] = 0;
    }
}
void build(int l, int r, int rt) {
    add[rt] = 0;
    if(l == r) {
        //cin >> sum[rt];
        scanf("%lld", &sum[rt]);
        return;
    }
    int m = (l + r) >> 1;
    build(lson);
    build(rson);
    push_up(rt);
}
void update(int L, int R, int c, int l, int r, int rt) {
    if(L <= l && r <= R) {
        add[rt] += c;
        sum[rt] += (ll)c * (r - l + 1);
        return ;
    }
    push_down(rt, r - l + 1);
    int m = (l + r) >> 1;
    if(L <= m) {
        update(L, R, c, lson);
    }
    if(R > m) {
        update(L, R, c, rson);
    }
    push_up(rt);
}
ll query(int L, int R, int l , int r, int rt) {
    ll res = 0;
    if(L <= l && r <= R) {
        return sum[rt];
    }
    push_down(rt, r - l + 1);
    int m = (l + r) >> 1;
    if(L <= m) {
        res += query(L, R, lson);
    }
    if(R > m) {
        res += query(L, R, rson);
    }
    return res;
}

int main() {
    int n, q;
    scanf("%d%d", &n, &q);
    //cin >> n >> q;
    //getchar();
    //cin >> n >> q;
    build(1, n, 1);
    getchar();
    for (int i = 0; i < q; i++){
        char c[2];
        ll a, b;
        scanf("%s%lld%lld", &c, &a, &b);
        //cout <<"+**-/*-/  " << c << "   ++--*//*-" << a << " " << b << endl;
        //cin >> c >> a >> b;
        if(c[0] == 'Q') {
            cout << query(a, b, 1, n, 1) << endl;
        }
        else {
            ll cc;
            scanf("%lld", &cc);
            //cin >> cc;
            update(a, b, cc, 1, n, 1);
        }
    }
}