程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ 3468 A Simple Problem with Integers（線段樹|區間加減&&區間求和）

POJ 3468 A Simple Problem with Integers（線段樹|區間加減&&區間求和）

編輯：C++入門知識

POJ 3468 A Simple Problem with Integers（線段樹|區間加減&&區間求和）

題意：區間加減，區間求和。

該題是線段樹區間增減和區間求和的模板題。和區間修改值一樣，在每個結點上維護一個之前加減的值，那麼每次經過一個結點時，當前結點一定已經擁有所有結點信息。

每次遞歸前下傳結點信息，這就是所謂的懶惰標記。

細節參見代碼：

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 1000000000;
const int maxn = 100000 + 10;
int T,n,l,r,q,v;
ll sum[maxn<<2],addv[maxn<<2];
char s[10];
void push_up(int o) {
    sum[o] = sum[o<<1] + sum[o<<1|1];
}
void build(int l, int r, int o) {
    int m = (l + r) >> 1;
    addv[o] = 0;
    if(l == r) {
        scanf("%lld",&sum[o]);
        return ;
    }
    build(l, m, o<<1);
    build(m+1, r, o<<1|1);
    push_up(o);
}
void pushdown(int o, int l, int r) {
    if(addv[o]) {
        int m = (l + r) >> 1;
        addv[o<<1] += addv[o];
        addv[o<<1|1] += addv[o];
        sum[o<<1] += (ll)(m - l + 1) * addv[o];
        sum[o<<1|1] += (ll)(r - m) * addv[o];
        addv[o] = 0;
    }
}
void update(int L, int R, int v, int l, int r, int o) {
    int m = (l + r) >> 1;
    if(L <= l && r <= R) {
        addv[o] += v;
        sum[o] += (ll)v * (r - l + 1);
        return ;
    }
    pushdown(o, l, r);
    if(L <= m) update(L, R, v, l, m, o<<1);
    if(m < R) update(L, R, v, m+1, r, o<<1|1);
    push_up(o);
}
ll query(int L, int R, int l, int r, int o) {
    int m = (l + r) >> 1;
    if(L <= l && r <= R) {
        return sum[o]; //當前結點一定已經擁有所有的標記
    }
    ll ans = 0;
    pushdown(o, l, r);
    if(L <= m) ans += query(L, R, l, m, o<<1);
    if(m < R) ans += query(L, R, m+1, r, o<<1|1);
    push_up(o);
    return ans;
}
int main() {
    while(~scanf("%d%d",&n,&q)) {
        build(1, n, 1);
        while(q--) {
            scanf("%s%d%d",s,&l,&r);
            if(s[0] == 'Q') {
                printf("%lld\n",query(l, r, 1, n, 1));
            }
            else {
                scanf("%d",&v);
                update(l, r, v, 1, n, 1);
            }
        }
    }
    return 0;
}