首页 > 代码库 > 线段树---HDU1166敌兵布阵

线段树---HDU1166敌兵布阵

这个是线段树中最入门的题目,但是由于不了解线段树的概念,当然更不知道怎么样,所以觉得挺费劲,整了一会发现还是基本的思想,就是还是将一个线段继续分割,一直分割到不能分割,这道题目是知道多少个军营,也就是区间为1-n, 将它分割, 建立树, 可以不用保存它区间的左端点和右端点,用数组下标代表就可以了, 数组的值代表当前军营里人的个数,然后这个题就是单个点的增加或者减少,其实增加减少都是增加,减少只是把增加的数目变成负数就行了,还有就是更新完最下面的点还要一直往上更新。那样查找区间的时候才不会出错。下面是代码的实现

  1 #include <stdio.h>  2 #include <math.h>  3   4 const int MAX = 50010 * 4;  5 int segment[MAX];//存放线段树,因为类似完全二叉树, 所以可以用数组来表示  6 //更新root节点的值,即兵营里的人数  7 void pushUp(int root, int add_num)  8 {  9     segment[root] = segment[root * 2] + segment[root * 2 + 1]; 10 } 11 //建树,只需要两个点,一个起点,一个终点 12 void buildTree(int root, int left, int right) 13 { 14     if(left == right) 15     { 16         //输入兵营里的人数 17         scanf("%d", &segment[root]); 18         return; 19     } 20     int mid = (left + right) / 2; 21     buildTree(root * 2, left, mid); 22     buildTree(root * 2 + 1, mid + 1, right); 23     //调整它的上面节点的值 24     pushUp(root); 25 } 26 /*更新最下面节点的值,而且要更新以上给他有关联的节点的值, root代表根节点, 27 pos代表更新的位置, add_num 代表增加的值,如果是负数,说明是减少的,left和right 28 分别为当前节点区间的左右端点*/ 29 void update(int root, int pos, int add_num, int left, int right) 30 { 31     if (left == right) 32     { 33         segment[root] += add_num; 34         return; 35     } 36     int mid = (left + right) / 2; 37     if (pos <= mid) 38         update(root * 2, pos, add_num, left, mid); 39     else 40         update(root * 2 + 1, pos, add_num, mid + 1, right); 41     //向上调整 42     pushUp(root); 43 } 44 //获取指定区间内的总数 45 int getSum(int root, int left, int right, int L, int R) 46 { 47     if(left == L && right == R) 48     { 49         return segment[root]; 50     } 51     int mid = (L + R) / 2; 52     int res = 0; 53     //如果在当前节点的右半个区间内 54     if(left > mid) 55     { 56         res += getSum(root * 2 + 1, left, right, mid + 1, R); 57     } 58     //如果在当前节点的左半个区间内 59     else if(right <= mid) 60     { 61         res += getSum(root * 2, left, right, L, mid); 62     } 63     //一个在左边,一个在右边 64     else 65     { 66         res += getSum(root * 2, left, mid, L, mid); 67         res += getSum(root * 2 + 1, mid + 1, right, mid + 1, R); 68     } 69     return res; 70 } 71  72 int main() 73 { 74     int T; 75     scanf("%d", &T); 76     for(int kase = 1; kase <= T; kase++) 77     { 78  79         int n; 80         scanf("%d", &n); 81         buildTree(1, 1, n);//建树,同时输入节点的值,也就是兵营的人数 82         char op[10]; 83         int t1, t2; 84         printf("Case %d:\n", kase); 85         while(scanf("%s", op)) 86         { 87             if(op[0] == E) 88                 break; 89             scanf("%d %d", &t1, &t2); 90             if(op[0] == A) 91             { 92                 update(1, t1, t2, 1, n); 93             } 94             else if(op[0] == S) 95             { 96                 update(1, t1, -t2, 1, n); 97             } 98             else 99             {100                 printf("%d\n", getSum(1, t1, t2, 1, n));101             }102         }103     }104     return 0;105 }

 

线段树---HDU1166敌兵布阵