树状数组 1 ：单点修改，区间查询

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<cmath>
 6 #include<queue>
 7 #define pn putchar('
')
 8 #define pd putchar(' ')
 9 #define num ch-'0'
10 #define reint register int
11 using namespace std;
12 template <typename T>
13 void read(T &res)
14 {
15     char ch;bool flag=false;
16     while(!isdigit(ch=getchar()))(ch=='-')&&(flag=true);
17     for(res=num;isdigit(ch=getchar());res=res*10+num);
18     flag&&(res=-res);
19 }
20 template <typename T>
21 void write(T x)
22 {
23     if(x<0)putchar('-'),x=-x;
24     if(x>9)write(x/10);
25     putchar(x%10+'0');
26 }
27 typedef long long ll;
28 const int INF=0x7fffffff;
29 const int inf=0x3f3f3f3f;
30 const int mod=1000000007;
31 const int maxn=1000005;
32 ll tree[maxn],a[maxn];
33 int n;
34 inline int lowbits(int x) {
35     return x&(-x);
36 }
37 inline void init(){
38     for(int i=1;i<=n;i++)
39         read(a[i]);
40     for(int i=1;i<=n;i++) {
41         int lowb=lowbits(i);
42         for(reint j=i-lowb+1;j<=i;j++)
43             tree[i]+=a[j];
44     }
45 }
46 inline void add(int p,ll v) {
47     for(int i=p;i<=n;i+=lowbits(i))
48         tree[i]+=v;
49 }
50 inline ll getsum(int l,int r) {
51     ll ans1=0,ans2=0;
52     for(int i=l;i>=1;i-=lowbits(i))
53         ans1+=tree[i];
54     for(int i=r;i>=1;i-=lowbits(i))
55         ans2+=tree[i];
56     return ans2-ans1;
57 }
58 int main()
59 {
60     int q;
61     read(n);read(q);
62     init();
63     while(q--) {
64         int oper,l,r,p;
65         ll v;
66         read(oper);
67         if(--oper) {
68             read(l),read(r);
69             write(getsum(l-1,r)); pn;
70         }
71         else {
72             read(p),read(v);
73             add(p,v);
74         }
75     }
76     return 0;
77 }

View Code

树状数组 2 ：区间修改，单点查询

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<cmath>
 6 #include<queue>
 7 #define pn putchar('
')
 8 #define pd putchar(' ')
 9 #define num ch-'0'
10 #define reint register int
11 using namespace std;
12 template <typename T>
13 void read(T &res)
14 {
15     char ch;bool flag=false;
16     while(!isdigit(ch=getchar()))(ch=='-')&&(flag=true);
17     for(res=num;isdigit(ch=getchar());res=res*10+num);
18     flag&&(res=-res);
19 }
20 template <typename T>
21 void write(T x)
22 {
23     if(x<0)putchar('-'),x=-x;
24     if(x>9)write(x/10);
25     putchar(x%10+'0');
26 }
27 typedef long long ll;
28 const int INF=0x7fffffff;
29 const int inf=0x3f3f3f3f;
30 const int mod=1000000007;
31 const int maxn=1000005;
32 int n;
33 ll d[maxn],tree[maxn];
34 inline int lowbits(int x) {
35     return x&-x;
36 }
37 inline void init() {
38     ll a,b=0;
39     for(int i=1;i<=n;i++) {
40         read(a);
41         d[i]=a-b;
42         b=a;
43     }
44     for(int i=1;i<=n;i++)
45         for(int j=i-lowbits(i)+1;j<=i;j++)
46             tree[i]+=d[j];
47 }
48 inline ll query(int p) {
49     ll ans=0;
50     while(p) ans+=tree[p],p-=lowbits(p);
51     return ans;
52 }
53 inline void add(int p,ll v) {
54     while(p<=n) {
55         tree[p]+=v;
56         p+=lowbits(p);
57     }
58 }
59 int main()
60 {
61     int q,oper;
62     read(n),read(q);
63     init();
64     while(q--) {
65         read(oper);
66         if(--oper) {
67             int p; read(p);
68             write(query(p)),pn;
69         }
70         else {
71             int l,r;
72             ll v;
73             read(l),read(r),read(v);
74             add(l,v),add(r+1,-v);
75         }
76     }
77     return 0;
78 }

View Code