树状数组（区间修改，单点查询）

题目描述

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

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 #include<iostream>
 2 #include<cstdio> 
 3 using namespace std;
 4 
 5 long long n,m;
 6 long long a[500009]; 
 7 long long b[500009];
 8 long long lowbit(int x)
 9 {
10     return (x&(-x));
11 }
12 void change(int x,int k)
13 {
14     for(int i=x;i<=n;i+=lowbit(i))
15     {
16         b[i]+=k;
17     }
18 }
19 long long query(int x)
20 {
21     long long sum=0;
22     for(int i=x;i>=1;i-=lowbit(i))
23     {
24         sum+=b[i];
25     }
26     return sum;
27 }
28 int main()
29 {
30     cin>>n>>m;
31     for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
32     for(int i=1;i<=m;i++)
33     {
34         int p;
35         cin>>p;
36         if(p==1)
37         {
38             int x,y,k;
39             scanf("%d %d %d",&x,&y,&k);
40             change(x,k);
41             change(y+1,-k);
42         }
43         if(p==2)
44         {
45             int x;
46             scanf("%d",&x);
47             cout<<query(x)+a[x]<<endl;
48         }
49     }
50 }