### 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); }