1080 线段树练习

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 钻石 Diamond

题目描述 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 。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 
 5 using namespace std;
 6 const int N=100001;
 7 
 8 int a[N];
 9 int sum[N*4];
10 int n,m;
11 
12 void rushu(int jd)
13 {
14     sum[jd]=sum[jd*2]+sum[jd*2+1];
15 }
16 
17 void built(int l,int r,int jd)
18 {
19     if(l==r)
20     {
21         sum[jd]=a[l];
22         return ;
23     }
24     int mid=(l+r)/2;
25     built(l,mid,jd*2);
26     built(mid+1,r,jd*2+1);
27     rushu(jd);
28 }
29 
30 void gai(int l,int r,int jd,int q,int h)
31 {
32     if(l==r)
33     {
34         sum[jd]+=h;
35         return ;
36     }
37     int mid=(l+r)/2;
38     if(q<=mid)
39     {
40         gai(l,mid,jd*2,q,h);
41     }
42     else
43     {
44         gai(mid+1,r,jd*2+1,q,h);
45     }
46     rushu(jd);
47 }
48 
49 int js(int l,int r,int jd,int q,int h)
50 {
51     if(q<=l&&r<=h)
52     {
53         return sum[jd];
54     }
55     int mid=(l+r)/2;
56     int ans=0;
57     if(q<=mid)
58     {
59         ans+=js(l,mid,jd*2,q,h);
60     }
61     if(h>mid)
62     {
63         ans+=js(mid+1,r,jd*2+1,q,h);
64     }
65     return ans;
66 }
67 
68 int main()
69 {
70     cin>>n;
71     for(int i=1;i<=n;i++)
72     {
73         cin>>a[i];
74     }
75     built(1,n,1);
76     cin>>m;
77     for(int i=1;i<=m;i++)
78     {
79         int x,y,z;
80         cin>>x>>y>>z;
81         if(x==1)
82         {
83             gai(1,n,1,y,z);
84         }
85         else 
86         {
87             cout<<js(1,n,1,y,z)<<endl;
88         }
89     }
90 }

感谢留言

树状数组：

 1 #include<iostream>
 2 #include<cstdio>
 3 
 4 using namespace std;
 5 const int N=100001;
 6 
 7 int a[N],T[N];
 8 int s,x,y;
 9 int n,m;
10 
11 int LB(int x)
12 {
13     return x&(-x);
14 }
15 
16 void A_add(int x,int y)
17 {
18     while(x<=n)
19     {
20         T[x]+=y;
21         x+=LB(x);
22     }
23     return ;
24 }
25 
26 int sum(int x)
27 {
28     int ans=0;
29     while(x)
30     {
31         ans+=T[x];
32         x-=LB(x);
33     }
34     return ans;
35 }
36 
37 int main()
38 {
39     cin>>n;
40     for(int i=1;i<=n;i++)
41     {
42         cin>>a[i];
43         A_add(i,a[i]);
44     }
45     cin>>m;
46     while(m--)
47     {
48         cin>>s>>x>>y;
49         if(s==1)A_add(x,y);
50         else cout<<sum(y)-sum(x-1)<<endl;
51     }
52 }

结构体版线段树：

 1 #include<iostream>
 2 #include<cstdio>
 3 
 4 using namespace std;
 5 const int N=100001;
 6 
 7 int ans,z,x,y;
 8 int n,m;
 9 
10 struct node{
11     int l,r,w,f;
12 }T[N*4];
13 
14 void built(int l,int r,int jd)
15 {
16     T[jd].l=l;
17     T[jd].r=r;
18     if(T[jd].l==T[jd].r)
19     {
20         cin>>T[jd].w;
21         return ;
22     }
23     int mid=(T[jd].l+T[jd].r)>>1;
24     built(l,mid,jd<<1);
25     built(mid+1,r,jd<<1|1);
26     T[jd].w=T[jd<<1].w+T[jd<<1|1].w;
27 }
28 
29 void po_gai(int jd)
30 {
31     if(T[jd].l==T[jd].r)
32     {
33         T[jd].w+=y;
34         return ;
35     }
36     int mid=(T[jd].l+T[jd].r)>>1;
37     if(x<=mid)po_gai(jd<<1);
38     else po_gai(jd<<1|1);
39     T[jd].w=T[jd<<1].w+T[jd<<1|1].w;
40 }
41 
42 void po_ask(int jd)
43 {
44     if(x<=T[jd].l&&T[jd].r<=y)
45     {
46         ans+=T[jd].w;
47         return ;
48     }
49     int mid=(T[jd].l+T[jd].r)>>1;
50     if(x<=mid)po_ask(jd<<1);
51     if(y>mid)po_ask(jd<<1|1);
52 }
53 
54 int main()
55 {
56     cin>>n;
57     built(1,n,1);
58     cin>>m;
59     for(int i=1;i<=m;i++)
60     {
61         cin>>z>>x>>y;
62         if(z==1)po_gai(1);
63         ans=0;
64         po_ask(1);
65         if(z==2)cout<<ans<<endl;
66     }
67 }

注意：T[N*4]，T数组要开4倍空间，because it is a tree.