Codevs1080 线段树练习

题目描述 Description

一行N个方格，开始每个格子里都有一个整数。现在动态地提出一些问题和修改：提问的形式是求某一个特定的子区间[a,b]中所有元素的和；修改的规则是指定某一个格子x，加上或者减去一个特定的值A。现在要求你能对每个提问作出正确的回答。1≤N<100000，,提问和修改的总数m<10000条。

输入描述 Input Description

输入文件第一行为一个整数N，接下来是n行n个整数，表示格子中原来的整数。接下一个正整数m，再接下来有m行，表示m个询问，第一个整数表示询问代号，询问代号1表示增加，后面的两个数x和A表示给位置X上的数值增加A，询问代号2表示区间求和，后面两个整数表示a和b，表示要求[a,b]之间的区间和。

输出描述 Output Description

共m行，每个整数

样例输入 Sample Input

1 3 5

2 1 4

1 1 9

2 2 6

样例输出 Sample Output

数据范围及提示 Data Size & Hint

1≤N≤100000， m≤10000 。

树状数组：

转载一篇详解：http://blog.csdn.net/hanhai768/article/details/37822773

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 using namespace std;
 5 
 6 int n,m;
 7 int f[100001];
 8 
 9 int read()
10 {
11     int x=0,f=1;char ch=getchar();
12     while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
13     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
14     return x*f;
15 }
16 
17 int lowbit(int x)
18 {
19     return x&(-x);
20 }
21 
22 void update(int x,int num)
23 {
24     while(x<=n)
25     {
26         f[x]+=num;
27         x+=lowbit(x);
28     }
29 }
30 
31 int sum(int x)
32 {
33     int sum=0;
34     while(x>0)
35     {
36         sum+=f[x];
37         x-=lowbit(x);
38     }
39     return sum;
40 }
41 
42 int main()
43 {
44     n=read();
45     for(int i=1;i<=n;i++)
46         update(i,read());
47     m=read();
48     for(int i=1;i<=m;i++)
49     {
50         int a=read(),x=read(),y=read();
51         if(a==1)update(x,y);
52         if(a==2)printf("%d
",sum(y)-sum(x-1));
53     }
54     return 0;
55 }

线段树：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 using namespace std;
 5 
 6 struct data
 7 {
 8     int l,r,sum;
 9 }tree[400000];
10 int n,m,a[100001];
11 
12 int read()
13 {
14     int x=0,f=1;char ch=getchar();
15     while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
16     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
17     return x*f;
18 }
19 
20 void build(int k,int s,int t)
21 {
22     tree[k].l=s;tree[k].r=t;
23     if(s==t){tree[k].sum=a[s];return;}
24     int mid=(s+t)>>1;
25     build(k<<1,s,mid);
26     build(k<<1|1,mid+1,t);
27     tree[k].sum=tree[k<<1].sum+tree[k<<1|1].sum;
28 }
29 
30 int sum(int k,int s,int t)
31 {
32     int l=tree[k].l,r=tree[k].r;
33     if(s==l&&t==r) return tree[k].sum;
34     int mid=(l+r)>>1;
35     if(t<=mid) return sum(k<<1,s,t);
36     if(s>mid) return sum(k<<1|1,s,t);
37     return sum(k<<1,s,mid)+sum(k<<1|1,mid+1,t);
38 }
39 
40 void update(int k,int x,int y)
41 {
42     tree[k].sum+=y;
43     int l=tree[k].l,r=tree[k].r;
44     if(l==r) return;
45     int mid=(l+r)>>1;
46     if(x<=mid) update(k<<1,x,y);
47     else update(k<<1|1,x,y);
48 }
49 
50 int main()
51 {
52     n=read();
53     for(int i=1;i<=n;i++)
54         a[i]=read();
55     build(1,1,n);
56     m=read();
57     for(int i=1;i<=m;i++)
58     {
59         int a=read(),b=read(),c=read();
60         if(a==1) update(1,b,c);
61         if(a==2) printf("%d
",sum(1,b,c));
62     }
63     return 0;
64 }

zkw线段树：张昆玮神的不能再神了

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 using namespace std;
 5 
 6 const int M=261244;
 7 
 8 int n,m;
 9 int f[524289];
10 
11 int read()
12 {
13     int x=0,f=1;char ch=getchar();
14     while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
15     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
16     return x*f;
17 }
18 
19 void update(int x,int num)
20 {
21     for(f[x+=M]+=num,x>>=1;x;x>>=1)
22         f[x]=f[x<<1]+f[x<<1|1];
23 }
24 
25 int query(int s,int t)
26 {
27     int ans=0;
28     for(s=s+M-1,t=t+M+1;s^t^1;s>>=1,t>>=1)
29     {
30         if(~s&1) ans+=f[s^1];
31         if(t&1) ans+=f[t^1];
32     }
33     return ans;
34 }
35 
36 int main()
37 {
38     n=read();
39     for(int i=1;i<=n;i++)
40         update(i,read());
41     m=read();
42     for(int i=1;i<=m;i++)
43     {
44         int a=read(),x=read(),y=read();
45         if(a==1)update(x,y);
46         if(a==2)printf("%d
",query(x,y));
47     }
48     return 0;
49 }