poj 3468 树状数组区间修改区间求和

这是利用树状数组进行区间求和区间修改，写起来比线段树轻松许多，具体的原理参考大佬博客：https://blog.csdn.net/fsahfgsadhsakndas/article/details/52650026

代码如下

 1 /*
 2 POJ 3468 树状数组  区间修改 和 区间查询
 3 原理：https://blog.csdn.net/FSAHFGSADHSAKNDAS/article/details/52650026 
 4 c1 和 c2 是两个差分数组，所以输入数据时  c1[i]=a[i]-a[i-1]，
 5  
 6 */
 7 #include <stdio.h>
 8 #include <iostream>
 9 #include <string.h>
10 using namespace std;
11 #define MAX 100020
12 
13 __int64 c1[MAX],c2[MAX];//两个差分树状数组，这题数据太大所以__int64 
14 __int64 n,q;
15 __int64 lowbit(int x){ return x&(-x);}
16 
17 __int64 sum(__int64* r,__int64 x) //求和 
18 {
19    __int64 ans = 0;
20    for (__int64 i = x;i>0;i-=lowbit(i))
21     ans += r[i];
22    return ans;
23 }
24 void add(__int64 *r,__int64 x,__int64 val)//单点更新 
25 {
26   for (__int64 i=x;i<=n;i+=lowbit(i))
27      r[i]+=val;
28 }
29 
30 int main ()
31 { 
32   __int64 a,b,c,s1,s2;
33   memset(c1,0,sizeof(c1));
34   memset(c2,0,sizeof(c2));
35   b = 0;
36   scanf ("%I64d%I64d",&n,&q);
37   for (int i=1;i<=n;++i)
38    {
39         scanf ("%I64d",&a);
40      add(c1,i,a-b);//差分数组c1[n]，c1[i]=a[i]-a[i-1]
41      add(c2,i,(i-1)*(a-b));//C2[I] = C1[I]*(I-1);
42      b = a;
43    }
44     char ch = 0;
45    for (int i=0;i<q;++i)
46     {
47       cin >> ch;
48       if (ch =='C')
49        {
50             scanf ("%I64d%I64d%I64d",&a,&b,&c) ;//区间更新 
51             add(c1,a,c);add(c1,b+1,-c) ; //一正一负 
52             add(c2,a,(a-1)*c);add(c2,b+1,(b)*(-c));
53        }
54       else
55       {
56           scanf ("%I64d%I64d",&a,&b) ;
57           s1 = (a-1)*sum(c1,a-1) - sum(c2,a-1);//注意这里是a - 1,因为区间a --b 包含a  
58           s2 =  (b)*sum(c1,b) - sum(c2,b);
59           printf ("%I64d
",s2-s1);
60       }
61     }
62  return 0;
63 }

View Code

poj 3468 树状数组 区间修改 区间求和

poj 3468 树状数组区间修改区间求和