洛谷 P3374 【模板】树状数组 1 & P3368 【模板】树状数组 2 题解

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #define maxn 500000+10
 6 using namespace std;
 7 inline int read() 
 8 {
 9     int x=0;
10     bool f=1;
11     char c=getchar();
12     for(; !isdigit(c); c=getchar()) if(c==‘-‘) f=0;
13     for(; isdigit(c); c=getchar()) x=(x<<3)+(x<<1)+c-‘0‘;
14     if(f) return x;
15     return 0-x;
16 }
17 inline void write(int x)
18 {
19     if(x<0){putchar(‘-‘);x=-x;}
20     if(x>9)write(x/10);
21     putchar(x%10+‘0‘);
22 }
23 int n,m;
24 int tree[maxn];
25 inline int lowbit(int num)
26 {
27     return num&-num;
28 }
29 inline void build(int s,int num)
30 {
31     for(int i=s;i<=n;i+=lowbit(i)) tree[i]+=num;
32 }
33 inline int ask(int s)
34 {
35     int ans=0;
36     for(int i=s;i>=1;i-=lowbit(i)) ans+=tree[i];
37     return ans;
38 }
39 int main()
40 {
41     n=read();m=read();
42     for(int i=1;i<=n;i++) 
43     {
44         int x;
45         x=read();
46         build(i,x);
47     }
48     for(int i=1;i<=m;i++)
49     {
50         int se;
51         se=read();
52         if(se==1)
53         {
54             int x,k;
55             x=read();k=read();
56             build(x,k);
57         }
58         else if(se==2)
59         {
60             int  x,y;
61             x=read();y=read();
62             write(ask(y)-ask(x-1));
63             printf("\n");
64         }
65     }
66     return 0;
67 }

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #define maxn 500000+10
 6 #define INF 2147483647/2-1
 7 using namespace std;
 8 inline int read() 
 9 {
10     int x=0;
11     bool f=1;
12     char c=getchar();
13     for(; !isdigit(c); c=getchar()) if(c==‘-‘) f=0;
14     for(; isdigit(c); c=getchar()) x=(x<<3)+(x<<1)+c-‘0‘;
15     if(f) return x;
16     return 0-x;
17 }
18 inline void write(int x)
19 {
20     if(x<0){putchar(‘-‘);x=-x;}
21     if(x>9)write(x/10);
22     putchar(x%10+‘0‘);
23 }
24 int n,m;
25 int tree[maxn],inn[maxn];
26 inline int lowbit(int num)
27 {
28     return num&-num;
29 }
30 inline void build(int s,int num)
31 {
32     for(int i=s;i<=n;i+=lowbit(i)) tree[i]+=num;
33 }
34 inline int ask(int s)
35 {
36     int ans=0;
37     for(int i=s;i>=1;i-=lowbit(i)) ans+=tree[i];
38     return ans;
39 }
40 int main()
41 {
42     n=read();m=read();
43     for(int i=1;i<=n;i++) inn[i]=read();
44     for(int i=1;i<=m;i++)
45     {
46         int se;
47         se=read();
48         if(se==1)
49         {
50             int x,y,k;
51             x=read();y=read();k=read();
52             build(x,k);build(y+1,-k);
53         }
54         else if(se==2)
55         {
56             int x;
57             x=read();
58             printf("%d\n",inn[x]+ask(x));
59         }
60     }
61     return 0;
62 }