POJ_3468(1)

    在消化了PPT上思想之后，又重新做了一下这个题目。

    不妨将原数组的元素记作a[i]，然后我们用堆建立两棵线段树，一棵的原数组为x[i](x[i]=a[i]-a[i-1]，即原数组的差分数组)，另一棵的原数组为ix[i](ix[i] = i*x[i])。

    为什么要这么做呢？原因如下。

    如果我们记S[i]为x[i]的前缀和，我们会发现S[i]实际上就是a[i]，也就是说差分的前缀和就等于原数组中的对应元素（因而才说差分是前缀和的逆运算）。我们不妨设SS[i]为S[i]的前缀和，在求区间和时用SS[b]–SS[a-1]自然是很方便的，然而对于修改操作，无论是维护S[i]还是SS[i]都会很麻烦，但恰恰是维护x[i]很简单，只需要修改两个值，x[a]和x[b+1]。

    那么能不能将两个方便之处统一到一起呢？当然可以，因为SS[n] = (n+1)*(x[1]+x[2]+…+x[n])-(1*x[1]+2*x[2]+…+n*x[n])，而i*x[i]自然就是前面提的ix[i]咯，于是我们只要维护x[i]和ix[i]即可，这样在修改的时候每次只需各修改两个值，并修改相应的祖先即可，于是把区间修改的复杂度降成了元素修改的复杂度。

    查询区间和的时候只需要用线段树求x[i]与ix[i]的前缀和并做一定运算即可。

#include
     
       #include
      
        #define MAXD 100010 int N, Q, M; long long int a[MAXD], x[4 * MAXD], ix[4 * MAXD]; char op[5]; void init() {
   int i, j; for(M = 1; M < N + 2; M <<= 1);     a[0] = 0; for(i = 1; i <= N; i ++)         scanf("%lld", &a[i]); for(i = N; i >= 1; i --)         a[i] -= a[i - 1];     memset(x, 0, sizeof(x));     memset(ix, 0, sizeof(ix)); for(i = 1, j = M + 1; i <= N; i ++, j ++)     {
           x[j] = a[i];         ix[j] = i * a[i];     } for(i = M - 1; i > 0; i --)     {
           x[i] = x[i * 2] + x[i * 2 + 1];         ix[i] = ix[i * 2] + ix[i * 2 + 1];     } } void solve() {
   int i, j, a, b, c;     scanf("%s", op); if(op[0] == 'C')     {
           scanf("%d%d%d", &a, &b, &c);         a = a + M;         x[a] += c, ix[a] += (a - M) * c; for(; a ^ 1; a >>= 1)         {
               x[a >> 1] = x[a] + x[a ^ 1];             ix[a >> 1] = ix[a] + ix[a ^ 1];         }         b = b + M + 1;         x[b] -= c, ix[b] -= (b - M) * c; for(; b ^ 1; b >>= 1)         {
               x[b >> 1] = x[b] + x[b ^ 1];             ix[b >> 1] = ix[b] + ix[b ^ 1];         }     } else     {
           scanf("%d%d", &a, &b); int s, t; long long int sum1, sum2, res;         sum1 = sum2 = 0;         s = M, t = a + M; for(; s ^ t ^ 1; s >>= 1, t >>= 1)         {
   if(~s & 1)                 sum1 += x[s ^ 1], sum2 += ix[s ^ 1]; if(t & 1)                 sum1 += x[t ^ 1], sum2 += ix[t ^ 1];         }         res = - a * sum1 + sum2;         sum1 = sum2 = 0;         s = M, t = b + M + 1; for(; s ^ t ^ 1; s >>= 1, t >>= 1)         {
   if(~s & 1)                 sum1 += x[s ^ 1], sum2 += ix[s ^ 1]; if(t & 1)                 sum1 += x[t ^ 1], sum2 += ix[t ^ 1];         }         res += (b + 1) * sum1 - sum2;         printf("%lld\n", res);     } } int main() {
   while(scanf("%d%d", &N, &Q) == 2)     {
           init(); for(int i = 0; i < Q; i ++)             solve();     } return 0; }