//??[7/24/2014?Sjm] /* 第一道用線段樹做的題，照著大神的代碼風格寫的，，就當作線段樹單點更新的模板吧。。。。(當年用樹狀數組做的：代碼見這里) */
1 #include <iostream> 2 #include <cstdlib> 3 #include <cstdio> 4 #include <algorithm> 5 #include <cstring> 6 using namespace std; 7 #define lson l, m, rt << 1 8 #define rson m + 1, r, rt << 1 | 1 9 #define GetMid l + ((r-l) >> 1) 10 11 const int MAX = 50005; 12 int sum[MAX << 2]; 13 14 void PushUp(int rt) { sum[rt] = sum[rt << 1] + sum[rt << 1 | 1]; } 15 16 void Build(int l, int r, int rt) { 17 if (l == r) { scanf("%d", &sum[rt]); return; } 18 int m = GetMid; 19 Build(lson); 20 Build(rson); 21 PushUp(rt); 22 } 23 24 void Update(int pos, int add, int l, int r, int rt) { 25 if (l == r) { sum[rt] += add; return; } 26 int m = GetMid; 27 if (pos <= m) { Update(pos, add, lson); } 28 else { Update(pos, add, rson); } 29 PushUp(rt); 30 } 31 32 int Query(int L, int R, int l, int r, int rt) { 33 if (L <= l && r <= R) { return sum[rt]; } 34 int ret = 0; 35 int m = GetMid; 36 if (L <= m) { ret += Query(L, R, lson); } 37 if (R > m) { ret += Query(L, R, rson); } 38 return ret; 39 } 40 41 int main() 42 { 43 //freopen("input.txt", "r", stdin); 44 int T, N, a, b; 45 scanf("%d", &T); 46 for (int cas = 1; cas <= T; ++cas) { 47 printf("Case %d:\n", cas); 48 scanf("%d", &N); 49 Build(1, N, 1); 50 char str[10]; 51 while (scanf("%s", str) && 'E' != str[0]) { 52 scanf("%d %d", &a, &b); 53 if ('Q' == str[0]) { printf("%d\n", Query(a, b, 1, N, 1)); } 54 else { 55 if ('A' == str[0]) { Update(a, b, 1, N, 1); } 56 else { Update(a, -b, 1, N, 1); } 57 } 58 } 59 } 60 return 0; 61 }

轉載于:https://www.cnblogs.com/shijianming/p/4140819.html

總結

以上是生活随笔為你收集整理的线段树（单点更新（模板）） 之 hdu 1166的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。