线段树的定义 但是这种二叉树较为平衡,和静态二叉树一样,提前根据应用的部分建立好树形结构。针对性强,所以效率要高。一般来说,动态结构较为灵活,但是速度较慢;静态结构节省内存,速度较快。 hud1166: /*------------------------------------------------ @file hdu1166 解题: 线段树模板 @author fripSide @date 2014/02/15 ------------------------------------------------*/ #include <cstdio> const int MAXN = 50009; struct line { int l; int r; int num; } Tree[MAXN << 2]; void modify(int t) { Tree[t].num = Tree[t << 1].num + Tree[t << 1 | 1].num; } void build(int l, int r, int t) { Tree[t].l = l; Tree[t].r = r; Tree[t].num = 0; if (l == r) { scanf("%d", &Tree[t].num); return; } int m = (l + r) >> 1; build(l, m, t << 1); build(m + 1, r, t << 1 | 1); modify(t); } void update(int v, int add, int t) { if (Tree[t].l == v && Tree[t].r == v) { Tree[t].num += add; return; } int m = (Tree[t].l + Tree[t].r) >> 1; if (v <= m) { update(v, add, t << 1); } else { update(v, add, t << 1 | 1); } modify(t); } int query(int l, int r, int t) { if (Tree[t].l == l && Tree[t].r == r) { return Tree[t].num; } int m = (Tree[t].l + Tree[t].r) >> 1; if (l > m) { //左子树 return query(l, r, t << 1 | 1); } else if (r <= m) { //右子树 return query(l, r, t << 1); } else { return query(l, m, t << 1) + query(m + 1, r, t << 1 | 1); } } int main() { int t; while (scanf("%d", &t) != EOF && t != 0) { for (int cas = 1; cas <= t; ++cas) { printf("Case %d:\n", cas); int n; scanf("%d", &n); build(1, n, 1); char op[9]; while (scanf("%s", op) != EOF) { if (op[0] == 'E') { break; } int a, b; scanf("%d%d", &a, &b); if (op[0] == 'Q') { printf("%d\n", query(a, b, 1)); } else if (op[0] == 'A') { update(a, b, 1); } else { update(a, -b, 1); } } } } return 0; } hud1754 1 /*------------------------------------------------ 2 @file jd1456 3 解题: 4 线段树 5 1.建树 6 2.修改 7 3.查询 8 9 @author fripSide 10 @date 2014/02/11 11 ------------------------------------------------*/ 12 13 #include <cstdio> 14 #include <algorithm> 15 16 using namespace std; 17 18 const int MAXN = 200009; 19 20 struct line { 21 int l; 22 int r; 23 int cmax; 24 } Tree[MAXN * 4]; 25 26 void pushUp(int t) { 27 int x = t << 1; 28 Tree[t].cmax = max(Tree[x + 1].cmax, Tree[x + 2].cmax); 29 } 30 31 void buildTree(int l, int r, int t) { //[l, r] t表示结点编号 32 Tree[t].l = l; 33 Tree[t].r = r; 34 Tree[t].cmax = 0; 35 if (l == r) { //叶结点 36 scanf("%d", &Tree[t].cmax); 37 return; 38 } 39 int x = (l + r) >> 1; 40 buildTree(l, x, t << 1 | 1); 41 buildTree(x + 1, r, (t << 1) + 2); 42 pushUp(t); 43 } 44 45 void updateTree(int v, int cn, int t) { 46 if (Tree[t].l == v && Tree[t].r == v) { 47 Tree[t].cmax = cn; 48 return; 49 } 50 int m = (Tree[t].l + Tree[t].r) >> 1; 51 if (v <= m) { 52 updateTree(v, cn, t << 1 | 1); 53 } else { 54 updateTree(v, cn, (t << 1) + 2); 55 } 56 pushUp(t); 57 } 58 59 int queryTree(int l, int r, int t) { 60 if (Tree[t].l == l && Tree[t].r == r) { 61 return Tree[t].cmax; 62 } 63 int m = (Tree[t].l + Tree[t].r) >> 1; 64 if (l > m) { 65 return queryTree(l, r, (t << 1) + 2); 66 } else if (r <= m) { 67 return queryTree(l, r, t << 1 | 1); 68 } else { 69 int ret1 = queryTree(l, m, t << 1 | 1); 70 int ret2 = queryTree(m + 1, r, (t << 1) + 2); 71 return max(ret1, ret2); 72 } 73 } 74 75 int main() { 79 80 int n, m; 81 while (scanf("%d%d", &n, &m) != EOF) { 82 buildTree(1, n, 0); 83 while (m--) { 84 char op[2]; 85 int a, b; 86 scanf("%s%d%d", op, &a, &b); 87 if (op[0] == 'Q') { 88 printf("%d\n", queryTree(a, b, 0)); 89 } else { 90 updateTree(a, b, 0); 91 } 92 } 93 } 94 return 0; 95 }
|
|