• 洛谷 3368 树状数组 模板2


    模板2 区间修改,单点查询 

    这里有两种模板,详情见代码

    模板1:

     1 /*
     2  洛谷 3368 
     3  树状数组 模板 
     4  区间修改,单点求和 
     5 */ 
     6 
     7 #include <bits/stdc++.h>
     8 #define MAX 500010
     9 using namespace std;
    10 int c[MAX];
    11 int arr[MAX];
    12 int n,m;
    13 int lowbit(int x) { return x&(-x);
    14 }
    15 int query (int x)
    16 {
    17      int ans = 0;
    18    for (int i=x;i<=n;i+=lowbit(i))
    19       ans +=c[i];
    20       return ans;
    21 } 
    22 void update(int x,int val)
    23 {
    24     for (int i=x;i>0;i-=lowbit(i))
    25       c[i]+=val; 
    26 }
    27 
    28 int main ()
    29 {
    30   int a,b,d,e;
    31   memset(c,0,sizeof(c));
    32   cin >>n>>m;
    33   for (int i=1;i<=n;++i)
    34     scanf("%d",&arr[i]);
    35   for(int i=0;i<m;++i)
    36    {
    37         scanf("%d",&a);
    38         if (1==a)
    39            {
    40             scanf("%d%d%d",&b,&d,&e); 
    41             update(d,e);update(b-1,-e);
    42            }
    43         else
    44         {
    45              scanf ("%d",&b);
    46              printf ("%d
    ",query(b)+arr[b]) ;
    47         }
    48        
    49     } 
    50  return 0;
    51 }

    模板2:

     1 /*
     2  洛谷 3368 
     3  树状数组 模板 
     4  区间修改,单点求和 
     5 */ 
     6 // 模板 2  差分思想 
     7 #include <bits/stdc++.h>
     8 #define MAX 500010
     9 using namespace std;
    10 int c[MAX];
    11 int arr;
    12 int n,m;
    13 int lowbit(int x) { return x&(-x);
    14 }
    15 int query (int x)
    16 {
    17      int ans = 0;
    18    for (int i=x;i;i-=lowbit(i))
    19       ans +=c[i];
    20       return ans;
    21 } 
    22 void update(int x,int val)
    23 {
    24     for (int i=x;i<=n;i+=lowbit(i))
    25       c[i]+=val; 
    26 }
    27 
    28 int main ()
    29 {
    30   int a,b,d,e;
    31   memset(c,0,sizeof(c));
    32   cin >>n>>m;
    33   e = 0; 
    34   for (int i=1;i<=n;++i)
    35     {
    36       scanf("%d",&arr);
    37       update(i,arr-e); //差分输入 
    38       e = arr;
    39     } 
    40   for(int i=0;i<m;++i)
    41    {
    42         scanf("%d",&a);
    43         if (1==a)
    44            {
    45             scanf("%d%d%d",&b,&d,&e); 
    46             update(b,e);update(d+1,-e);//这里这样更新 
    47            }
    48         else
    49         {
    50              scanf ("%d",&b);
    51              printf ("%d
    ",query(b)) ;
    52         }
    53        
    54     } 
    55  return 0;
    56 }
  • 相关阅读:
  • 原文地址:https://www.cnblogs.com/yuluoluo/p/8666261.html
  • 最新文章
  • 热门文章
一二三 - 开发者的网上家园