【线段树 + 简单题】杭电 hdu 1166 敌兵布阵
/* THE PROGRAM IS MADE BY PYY *//*----------------------------------------// Copyright (c) 2011 panyanyany All rights reserved. URL : http://acm.hdu.edu.cn/showproblem.php?pid=1166 Name : 1166 敌兵布阵 Date : Sunday, September 18, 2011 Time Stage : half an hour Result: 46227082011-09-18 15:43:38Accepted116646MS1764K2586 BC++pyy小号46227062011-09-18 15:43:14Runtime Error(ACCESS_VIOLATION)116615MS1164K2586 BC++pyy小号 Test Data :Review :线段树的感觉，比较麻烦一点，同时空间和时间消耗都比树状数组要大//----------------------------------------*/#define _CRT_SECURE_NO_WARNINGS#include <stdio.h>#include <string.h>#define MAXSIZE 50001typedef struct {int left, right ;int sum ;} NODE ;inttcase, n ;NODEtree[MAXSIZE * 4] ;void build (int node, int left, int right){tree[node].left= left ;tree[node].right= right ;tree[node].sum= 0 ;if (left == right) return ;int mid = (left + right) / 2 ;build (node * 2, left, mid) ;build (node * 2 + 1, mid + 1, right) ;}void update (int node, int pos, int val){// 当前区间的总人数增加tree[node].sum += val ;// 刚好走到第pos 个营地所在的叶子if (tree[node].left == pos && tree[node].right == pos){return ;}int mid = (tree[node].left + tree[node].right) / 2 ;// 若营地在当前区间的左半边if (pos <= mid)update (node * 2, pos, val) ;// 若营地在当前区间的右半边else update (node * 2 + 1, pos, val) ;return ;}int query (int node, int left, int right){// 若区间刚好匹配if (tree[node].left == left &&tree[node].right == right)return tree[node].sum ;// 若区间无交集if (tree[node].left > right ||tree[node].right < left)return 0 ;// 若区间有交集int mid = (tree[node].left + tree[node].right) / 2 ;// 若查询区间在左半边if (right <= mid)return query (node * 2, left, right) ;// 若查查询区间在右半边else if (mid < left)return query (node * 2 + 1, left, right) ;// 若查询区间横跨当前区间的中点elsereturn query (node * 2, left, mid) + query (node * 2 + 1, mid + 1, right) ;}int main (){charstr[20] ;inti, j ;intx, y ;while (scanf ("%d", &tcase) != EOF){for (j = 1 ; j <= tcase ; ++j){scanf ("%d", &n) ;build (1, 1, n) ;for (i = 1 ; i <= n ; ++i){scanf ("%d", &x) ;// 从根部开始查找，第i 个营地的值增加xupdate (1, i, x) ;}printf ("Case %d:\n", j) ;while (scanf ("%s", str), *str != 'E'){scanf ("%d%d", &x, &y) ;if (*str == 'Q')printf ("%d\n", query (1, x, y)) ;else if (*str == 'A')update (1, x, y) ;else if (*str == 'S')update (1, x, -y) ;}}}return 0 ;}