hdu 1166 敌兵布阵线段树第一题

题意：给定一个序列，动态更新值,然后多次询问，求每段和

解题思路：线段树基本操作

解题代码：

  1 #include <stdio.h>
  2 #include <string.h>
  3 #include <stdlib.h>
  4 #include <math.h>
  5 #define MAX 50005
  6 int a[MAX];
  7 int ans = 0 ;
  8 int L(int  c)
  9 {
 10   return c * 2;
 11 }
 12 int R(int c)
 13 {
 14    return c * 2 + 1;
 15 }
 16 
 17 struct node
 18 {
 19    int left , right ,mid;
 20    int sum;
 21 }tree[MAX * 3];
 22 void up(int c)
 23 {
 24    tree[c].sum = tree[L(c)].sum + tree[R(c)].sum;
 25 }
 26 void build(int c, int p , int v )
 27 {
 28     tree[c].left = p ;
 29     tree[c].right = v;
 30     tree[c].mid = (p + v )/2;
 31     tree[c].sum = 0 ;
 32     if(p == v )
 33     {
 34         tree[c].sum = a[p];
 35         return ;
 36     }
 37     build(L(c),p,tree[c].mid);
 38     build(R(c),tree[c].mid+1,v);
 39     up(c);
 40 }
 41 
 42 void update(int c, int p, int value)
 43 {
 44      if(tree[c].left == p  && tree[c].right == p)
 45      {
 46          tree[c].sum += value;
 47          return ;
 48      }
 49      if(p <= tree[c].mid)
 50      {
 51        update(L(c),p,value);
 52      }
 53      else
 54         update(R(c),p,value);
 55      up(c);
 56 }
 57 
 58 void sum (int c, int p , int v )
 59 {
 60     if(p <= tree[c].left && v >= tree[c].right)
 61     {
 62       ans += tree[c].sum;
 63       return ;
 64     }
 65     if(tree[c].mid <  p ) sum(R(c),p,v);
 66     else if(tree[c].mid >= v) sum(L(c),p,v);
 67     else
 68     {
 69       sum(L(c),p,tree[c].mid);
 70       sum(R(c),tree[c].mid+1,v);
 71     }
 72 }
 73 int main()
 74 {
 75     int t ;
 76     scanf("%d",&t);
 77     for(int CASE = 1; CASE <= t ;  CASE ++)
 78     {
 79        int n ;
 80        scanf("%d",&n);
 81        for(int i = 1;i <= n;i ++)
 82         scanf("%d",&a[i]);
 83        build(1,1,n);
 84 
 85        printf("Case %d:
",CASE);
 86        for(int i = 1; ;i ++)
 87        {
 88          char str[10];
 89          scanf("%s",str);
 90 
 91          if(str[0] == 'E')
 92             break;
 93          else if(str[0] == 'A')
 94          {
 95 
 96              int a, b ;
 97              scanf("%d %d",&a,&b);
 98              update(1,a,b);
 99          }
100          else if(str[0] == 'S')
101          {
102              int a, b ;
103              scanf("%d %d",&a,&b);
104              update(1,a,-b);
105          }
106          else if(str[0] == 'Q')
107          {
108              int a, b ;
109              scanf("%d %d",&a,&b);
110              ans = 0 ;
111              sum(1,a,b);
112              printf("%d
",ans);
113          }
114 
115        }
116     }
117     return 0 ;
118 }

View Code

ps：线段树第一题，学是找了好久的资料啊，过几天再写总结吧

没有梦想，何谈远方

hdu 1166 敌兵布阵 线段树第一题

hdu 1166 敌兵布阵线段树第一题