• 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
  • 相关阅读:
  • 原文地址:https://www.cnblogs.com/yuluoluo/p/8666036.html
  • 最新文章
  • 热门文章
一二三 - 开发者的网上家园