树状数组 区间更新 区间查询

树状数组 区间更新 区间查询

【题目链接】codevs1082

【题目类型】树状数组 区间更新 区间查询

&题解：

转载自: http://blog.csdn.net/fsahfgsadhsakndas/article/details/52650026
【问题引入】

对于区间修改、区间查询这样的简单问题，打一大堆线段树确实是不划算，今天来介绍一下区间查询+区间修改的树状数组

【一些基础】

树状数组的基本知识不再介绍，请自行百度

我们假设sigma(r，i)表示r数组的前i项和，调用一次的复杂度是log2(i)

设原数组是a[n]，差分数组c[n]，c[i]=a[i]-a[i-1]，那么明显地a[i]=sigma(c,i)，如果想要修改a[i]到aj，只需令c[i]+=v,c[j+1]-=v

【今天的主要内容】

我们可以实现NlogN时间的“单点修改，区间查询”，“区间修改，单点查询”，其实后者就是前者的一个变形，要明白树状数组的本质就是“单点修改，区间查询”

怎么实现“区间修改，区间查询”呢？

观察式子：
a[1]+a[2]+...+a[n]

= (c[1]) + (c[1]+c[2]) + ... + (c[1]+c[2]+...+c[n])

= nc[1] + (n-1)c[2] +... +c[n]

= n * (c[1]+c[2]+...+c[n]) - (0c[1]+1c[2]+...+(n-1)*c[n]) (式子①)

那么我们就维护一个数组c2[n]，其中c2[i] = (i-1)*c[i]

每当修改c的时候，就同步修改一下c2，这样复杂度就不会改变

那么

式子①

=n*sigma(c,n) - sigma(c2,n)

于是我们做到了在O(logN)的时间内完成一次区间和查询

&代码：

#include <cstdio>
#define lowb(x) (x&-x)
#define ll long long
#define maxn 200009
using namespace std;
ll n, q, c1[maxn], c2[maxn], num[maxn];
void add(ll *r, ll i, ll x) {
   for(; i <= n; i += lowb(i))
      r[i] += x;
}
ll sum(ll *r, ll i) {
   ll s = 0;
   for(; i; i -= lowb(i))
      s += r[i];
   return s;
}

int main() {
   ll i, j, type, a, b, v, sum1, sum2;
   scanf("%lld", &n);
   for(int i = 1; i <= n; i++) {
      scanf("%lld", &num[i]);
      add(c1, i, num[i] - num[i - 1]);
      add(c2, i, (i - 1) * (num[i] - num[i - 1]));
   }
   scanf("%lld", &q);
   while(q--) {
      scanf("%lld", &type);
      if(type == 1) {
         scanf("%lld%lld%lld", &a, &b, &v);
         add(c1, a, v); add(c1, b + 1, -v);
         add(c2, a, v * (a - 1)); add(c2, b + 1, -v * b);
      }
      else {
         scanf("%lld%lld", &a, &b);
         sum1 = (a - 1) * sum(c1, a - 1) - sum(c2, a - 1);
         sum2 = b * sum(c1, b) - sum(c2, b);
         printf("%lld
", sum2 - sum1);
      }
   }
   return 0;
}