[模板]树状数组

1.单点修改区间查询

 1 #include<cstdio>
 2 #include<cstring>
 3 #define maxn 500000
 4 int n,m;
 5 struct BIT {
 6     int val[maxn];
 7     BIT() {
 8         memset(val,0,sizeof val);
 9     }
10     int lowbit(int x) {
11         return x&-x;
12     }
13     void modify(int p,const int x) {
14         while(p<=n) {
15             val[p]+=x;
16             p+=lowbit(p);
17         }
18     }
19     int query(int p) {
20         int ans=0;
21         while(p) {
22             ans+=val[p];
23             p-=lowbit(p);
24         }
25         return ans;
26     }
27 };
28 BIT tree;
29 int main() {
30     scanf("%d%d",&n,&m);
31     for(int i=1;i<=n;i++) {
32         int x;
33         scanf("%d",&x);
34         tree.modify(i,x);
35     }
36     while(m--) {
37         int op,x,y;
38         scanf("%d%d%d",&op,&x,&y);
39         if(op==1) {
40             tree.modify(x,y);
41         }
42         else {
43             printf("%d
",tree.query(y)-tree.query(x-1));
44         }
45     }
46     return 0;
47 }

2.区间修改单点查询

OJ题号：洛谷P3368

 1 #include<cstdio>
 2 #include<cstring>
 3 #define maxn 500001
 4 int n,m,a[maxn];
 5 struct BIT {
 6     int val[maxn];
 7     BIT() {
 8         memset(val,0,sizeof val);
 9     }
10     int lowbit(const int x) {
11         return x&-x;
12     }
13     void modify(int p,const int x) {
14         while(p) {
15             val[p]+=x;
16             p-=lowbit(p);
17         }
18     }
19     int query(int p) {
20         int ans=0;
21         while(p<=n) {
22             ans+=val[p];
23             p+=lowbit(p);
24         }
25         return ans;
26     }
27 };
28 BIT tree;
29 int main() {
30     scanf("%d%d",&n,&m);
31     for(int i=1;i<=n;i++) {
32         scanf("%d",&a[i]);
33     }
34     while(m--) {
35         int op;
36         scanf("%d",&op);
37         if(op==1) {
38             int x,y,k;
39             scanf("%d%d%d",&x,&y,&k);
40             tree.modify(y,k);
41             tree.modify(x-1,-k);
42         }
43         else {
44             int x;
45             scanf("%d",&x);
46             printf("%d
",a[x]+tree.query(x));
47         }
48     }
49     return 0;
50 }