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