P3368树状数组2（树状数组//改段求点）

 1 /*
 2 段改求点
 3 用树状数组维护差分数组
 4 因为a[i]=d[1]...d[i]
 5 所以用差分数组的化就很好进行查询操作
 6 至于区间修改，因为[x,y]区间内加上k的操作对差分数组造成的改变只有d[x]和d[y+1]
 7 直接用树状数组的基本操作给加上就好了
 8 */
 9 #include<iostream>
10 using namespace std;
11 const int N=500009;
12 int d[N];
13 int c[N];
14 int n,m;
15 int lowbit(int x)
16 {
17     return x&(-x);
18 }
19 void add(int x,int y)//x位置加上y
20 {
21     d[x]+=y;
22     for(int i=x;i<=n;i+=lowbit(i))
23     {
24         c[i]+=y;
25     }
26 }
27 void update(int x,int y,int k)//[x,y]区间内加上k
28 {
29     add(x,k);
30     add(y+1,-k);
31 }
32 int ask(int x)//查询a[i]直接d[1]...d[i]的和就是a[i]
33 {
34     int res=0;
35     for(int i=x;i>0;i-=lowbit(i))
36     {
37         res+=c[i];
38     }
39     return res;
40 }
41 int main(void)
42 {
43     cin>>n>>m;
44     int t1=0;
45     for(int i=1;i<=n;i++)
46     {
47         int t;
48         cin>>t;
49         d[i]=t-t1;//差分
50         t1=t;
51         add(i,d[i]);//一定要记得构建树状数组
52     }//在差分的基础上构建树状数组
53     for(int i=1;i<=m;i++)
54     {
55         int type;
56         cin>>type;
57         if(type==1)//[x,y]区间内加上k
58         {
59             int x,y,k;
60             cin>>x>>y>>k;
61             update(x,y,k);
62         }
63         else if(type==2)//查询第x个元素
64         {
65             int x;
66             cin>>x;
67             cout<<ask(x)<<endl;
68 
69         }
70     }
71     return 0;
72 }