当前位置：首页 > news >正文

hdu 1166 敌兵布阵（线段树或者树状数组）

news 来源：原创 2024/5/19 16:30:36

线段树：

 1 #include<cstdio>
 2 #include<cstring>
 3 using namespace std;
 4 int sum;
 5 int s1[100000],s2[1000000];
 6 int build(int l,int r,int p)
 7 {
 8    if (l==r) return s2[p]=s1[l];
 9    int m=(l+r)/2;
10    int a=build(l,m,2*p);
11    int b=build(m+1,r,2*p+1);
12    return s2[p]=a+b;
13 }
14 void un(int l,int r,int p,int pos,int c)
15 {
16     if (l<=pos&&r>=pos) s2[p]+=c;
17     if (l==r) return ;
18     int m=(l+r)/2;
19     if (pos<=m) un(l,m,2*p,pos,c);
20     else un(m+1,r,2*p+1,pos,c);
21     return ;
22 }
23 void find(int l,int r,int p,int ll,int rr)
24 {
25     if (ll<=l&&rr>=r) {sum+=s2[p];return ;}
26     if (ll>r||rr<l) return ;
27     int m=(l+r)/2;
28     find(l,m,2*p,ll,rr);
29     find(m+1,r,2*p+1,ll,rr);
30     return ;
31 }
32 int main()
33 {
34     int n,i,k,c,a,b;
35     char s[10];
36     scanf("%d",&c);
37     for (k=1;k<=c;k++)
38     {
39         //if (k!=1) printf("\n");
40         printf("Case %d:\n",k);
41         scanf("%d",&n);
42         for (i=1;i<=n;i++) scanf("%d",&s1[i]);
43         build(1,n,1);
44         while (~scanf("%s",&s))
45         {
46             if (s[0]=='E') break;
47             scanf("%d%d",&a,&b);
48             if (s[0]=='A') un(1,n,1,a,b);
49             if (s[0]=='S') un(1,n,1,a,-b);
50             if (s[0]=='Q')
51             {
52                 sum=0;
53                 find(1,n,1,a,b);
54                 printf("%d\n",sum);
55             }
56         }
57     }
58     return 0;
59 }

树状数组：

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 
 6 const int mx = 100005;
 7 int a[mx];
 8 int n;
 9 
10 int lowbit(int x)
11 {
12     return x&-x;
13 }
14 
15 void updata(int i,int x)
16 {
17     if (i>n) return ;
18     a[i]+=x;
19     i+=lowbit(i);
20     updata(i,x);
21 }
22 
23 int sum(int i)
24 {
25     if (i<=0) return 0;
26     return a[i]+sum(i-lowbit(i));
27 }
28 
29 int main()
30 {
31    int t;
32    scanf("%d",&t);
33    for (int cas=1;cas<=t;cas++)
34    {
35        printf("Case %d:\n",cas);
36        scanf("%d",&n);
37        memset(a,0,sizeof(a));
38        for (int i=1;i<=n;i++)
39        {
40            int b;
41            scanf("%d",&b);
42            updata(i,b);
43        }
44        char s[10];
45        while(1)
46        {
47            int u,v;
48            scanf("%s",s);
49            if (s[0]=='E') break;
50            scanf("%d%d",&u,&v);
51            if (s[0]=='Q') printf("%d\n",sum(v)-sum(u-1));
52            if (s[0]=='A') updata(u,v);
53            if (s[0]=='S') updata(u,-v);
54        }
55    }
56 }