7.22做题记录

 1 //树状数组单点修改和区间查询 
 2 #include <bits/stdc++.h>
 3 using namespace std;
 4 int n,m,f[1000005];
 5 int lowbit(int x)
 6 {
 7     return x&-x;
 8 }
 9 void add(int x,int k)
10 {
11     while(x<=n)
12     {
13         f[x]+=k;
14         x+=lowbit(x);
15     }
16 }
17 int sum(int x)
18 {
19     int ans=0;
20     while(x>0)
21     {
22         ans+=f[x];
23         x-=lowbit(x);
24     }
25     return ans;
26 }
27 int main()
28 {
29     cin>>n>>m;
30     for(int i=1;i<=n;i++)
31     {
32         int x;
33         cin>>x;
34         add(i,x);
35     }
36     for(int i=1;i<=m;i++)
37     {
38         int a,b,c;
39         cin>>a>>b>>c;
40         if(a==1)
41             add(b,c);
42         else
43             cout<<sum(c)-sum(b-1)<<endl;
44     }
45     return 0;
46 }

 1 //树状数组区间修改和单点查询
 2 #include <bits/stdc++.h>
 3 using namespace std;
 4 int n,m,a[5000005],f[5000005];
 5 int lowbit(int x)
 6 {
 7     return x&-x;
 8 }
 9 int search(int x)
10 {
11     int ans=0;
12     while(x>0)
13     {
14         ans+=f[x];
15         x-=lowbit(x);
16     }
17     return ans;
18 }
19 void add(int x,int k)
20 {
21     while(x<=n)
22     {
23         f[x]+=k;
24         x+=lowbit(x);
25     }
26 }
27 int main()
28 {
29     cin>>n>>m;
30     for(int i=1;i<=n;i++)
31         cin>>a[i];
32     for(int i=1;i<=m;i++)
33     {
34         int w;
35         cin>>w;
36         if(w==1)
37         {
38             int x,y,z;
39             cin>>x>>y>>z;
40             add(x,z);
41             add(y+1,-z);
42         }
43         else
44         {
45             int x;
46             cin>>x;
47             cout<<search(x)+a[x]<<'\n'; 
48         }
49     }
50     return 0;
51 }