树状数组模版2

题目描述

如题，已知一个数列，你需要进行下面两种操作：

1.将某区间每一个数数加上x

2.求出某一个数的和

输入输出格式

输入格式：

第一行包含两个整数N、M，分别表示该数列数字的个数和操作的总个数。

第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。

接下来M行每行包含2或4个整数，表示一个操作，具体如下：

操作1：格式：1 x y k 含义：将区间[x,y]内每个数加上k

操作2：格式：2 x 含义：输出第x个数的值

输出格式：

输出包含若干行整数，即为所有操作2的结果。

输入输出样例

输入样例#1： 复制

输出样例#1： 复制

6
10

说明

时空限制：1000ms,128M

数据规模：

对于30%的数据：N<=8，M<=10

对于70%的数据：N<=10000，M<=10000

对于100%的数据：N<=500000，M<=500000

样例说明：

故输出结果为6、10

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<cmath>
 5 using namespace std;
 6 int i,j,m,n,x,y,op,a[500005] = {0},k,d[500005],tot = 0,ans[500005];
 7 int lowbit(int p)
 8 {
 9     return p & -p;
10 }
11 void add(int x,int k)
12 {
13     while(x <= n)
14     {
15         d[x] += k;
16         x += lowbit(x);
17     }
18 }
19 void range_add(int l,int r,int k)
20 {
21     add(l,k);
22     add(r + 1,-k);
23 }
24 int chaxun(int x)
25 {
26     int res = 0;
27     while(x > 0) 
28     {
29         res += d[x];
30         x -= lowbit(x);
31 
32     }
33     return res;
34 }
35 int main()
36 {
37     scanf("%d %d",&n,&m);
38     a[0] = 0;
39     for(i = 1;i <= n;i++)
40     {
41         scanf("%d",&a[i]);
42         add(i,a[i] - a[i - 1]);
43         
44     }    
45     for(i = 1;i <= m;i++)
46     {
47         scanf("%d",&op);
48         if(op == 1)
49         {
50             scanf("%d %d %d",&x,&y,&k);
51             range_add(x,y,k);
52         }
53         else
54         {
55             tot = tot + 1;
56             scanf("%d",&x);
57             ans[tot] = chaxun(x);
58         }
59     }
60     for(i = 1;i <= tot;i++)
61     {
62         printf("%d",ans[i]);
63         if(i != tot)
64         printf("
");
65     }
66     return 0;
67  }

一开始没AC，一个是因为d[i]存的不是a[i] - a[i - 1],还有一个原因是初始的时候我没把他们存到一个树状数组里面而是随便直接存到了一个数组里面。