Brief description:

区间修改（+-d，区间求和的例题。

Analysis:

略）。。S[x] 表示和 (Sum 。。D[x] 表示作用在 x 结点区间上的修改操作，延迟下放标记。。(Delay
。。这类标记可以在打上去的时候就已经作用在 S[x] 上（完成时。。。
或者在下放之后才作用在 S[x] 上。。（未完成时。。。

。。线段树。。(完成时标记。。
。。线段树。。（未完成时标记。。

… （貌似区别不大 ? 。（。注意使用完成时标记修改时必须下放。。。
。。（其实我是来记录巨神犇的树状数组方法的。。。 /$:Orz ）

const int N = 100009;

LL B[N], C[N];
// Binary Index Tree
int n, m, a, b, d; char c;

LL Sum(int x){
    LL s1 = 0, s2 = 0, t = n - x; while (x <= n) s1 += B[x], s2 += C[x], x += low_bit(x);
    return s1 * t - s2;
}

void Add(int x, int d){
    LL t = (LL) (n - x - 1) * d;
    while (x) B[x] += d, C[x] += t, x ^= low_bit(x);
}

LL Sum(int l, int r){
    return Sum(l) - Sum(r+1);
}

void Add(int l, int r, int d){
    Add(r, d), Add(l-1, -d);
}

int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif

    RD(n, m); REP_1(i, n) Add(i, i, RD());

    DO(m){
        RC(c), RD(a, b);
        if (c == 'C') Add(a, b, RD());
        else OT(Sum(a, b));
    }
}

LL Sum(int x){
    LL s1 = 0, s2 = 0, t = x; while (x) s1 += B[x], s2 += C[x], x ^= low_bit(x);
    return s1 * t - s2;
}

void Add(int x, int d){
    LL t = (LL) (x - 1) * d;
    while (x <= n) B[x] += d, C[x] += t, x += low_bit(x);
}

LL Sum(int l, int r){
    return Sum(r) - Sum(l-1);
}

void Add(int l, int r, int d){
    Add(l, d), Add(r+1, -d);
}

External link:

http://poj.org/problem?id=3468

Posted by xiaodao
Category: POJ