称号：
标准段树模板代码：
#include#include const int maxn = 500000 + 10;struct Node{ int left, right, count;}node[maxn];int a[maxn];/**************************************************建树****************************i是区间序号**************l是区间i左边界。r是区间i右边界***从1到n開始建树，直到区间长度为1***即l=r时，结束。count记录区间和**************************************/void maketree(int l, int r, int i){ node[i].left = l; node[i].right = r; if(l == r){ node[i].count = a[l]; return ; } int m = (l + r)/2; maketree(l, m, 2*i); maketree(m + 1, r, 2*i + 1); node[i].count = node[2*i].count + node[2*i + 1].count;}/*********************************************************更新********************i区间序号。x要更新的点。
y要更新的值* *********flag推断更新方式************* ****************************************/ void updatetree(int i, int x, int y, int flag){ int l = node[i].left; int r = node[i].right; int m = (l + r)/2; if(r == l){ if(flag) node[i].count += y; else node[i].count -= y; return; } if(x <= m) updatetree(2*i, x, y, flag); else updatetree(2*i + 1, x, y, flag); if(flag) node[i].count += y; else node[i].count -= y; return; } /*********************************** ***************查询**************** ************************************/ int querytree(int l, int r, int i){ int m = (node[i].left + node[i].right)/2; if(node[i].right <= r && node[i].left >= l) return node[i].count; int ans = 0; if(r <= m) return querytree(l, r, 2*i); else if(l > m) return querytree(l, r, 2*i + 1); else return querytree(l, m, 2*i) + querytree(m + 1, r, 2*i + 1); } int main(){ int T, n; char str[20]; scanf("%d", &T); for(int i = 1; i <= T; i++){ printf("Case %d:\n", i); scanf("%d", &n); for(int i = 1; i <= n; i++) scanf("%d", &a[i]); maketree(1, n, 1); int x, y; while(scanf("%s", str)){ if(str[0] == 'E') break; scanf("%d%d", &x, &y); if(str[0] == 'Q') printf("%d\n", querytree(x, y, 1)); else if(str[0] == 'A') updatetree(1, x, y, true); else updatetree(1, x, y, false); } } return 0; }
：
#include上述两种代码思路同样。仅仅是代码风格不同，执行时间。占用内存还是同样的。此题仅仅涉及单点更新和区间求和。所以能够用树状数组求解，代码更简洁，执行速度更快。/*****************************灵活的使用宏定义******************************/#define lson l , m , rt << 1#define rson m + 1 , r , rt << 1 | 1const int maxn = 55555;int sum[maxn<<2];void PushUP(int rt) { sum[rt] = sum[rt<<1] + sum[rt<<1|1];}/***************************************************建树*************** 此处并没有使用结构体，仅仅是记录了区间和sum，但l，r与区间序号紧密关联***********************************/void build(int l,int r,int rt) { if (l == r) { scanf("%d",&sum[rt]); return ; } int m = (l + r) >> 1; build(lson); build(rson); PushUP(rt);}/*************************************** *****************更新***************** 此处没用标记更新方式（加或减）。巧妙 地在调用时处理了正负号，降低函数參数***************************************/void update(int p,int add,int l,int r,int rt) { if (l == r) { sum[rt] += add; return ; } int m = (l + r) >> 1; if (p <= m) update(p , add , lson); else update(p , add , rson); PushUP(rt);}/*********************************************************查询****************** 巧妙地引用了变量ret，降低了对m的讨论***************************************/int query(int L,int R,int l,int r,int rt) { if (L <= l && r <= R) { return sum[rt]; } int m = (l + r) >> 1; int ret = 0; if (L <= m) ret += query(L , R , lson); if (R > m) ret += query(L , R , rson); return ret;}int main() { int T , n; scanf("%d",&T); for (int cas = 1 ; cas <= T ; cas ++) { printf("Case %d:\n",cas); scanf("%d",&n); build(1 , n , 1); char op[10]; while (scanf("%s",op)) { if (op[0] == 'E') break; int a , b; scanf("%d%d",&a,&b); if (op[0] == 'Q') printf("%d\n",query(a , b , 1 , n , 1)); else if (op[0] == 'S') update(a , -b , 1 , n , 1); else update(a , b , 1 , n , 1); } } return 0;}
但树状数组能够求区间和，无法求出区间最值，通用解法仍是用线段树求解。
树状数组的代码：#include#include using namespace std;const int maxn = 50000 + 10;int len, a[maxn];char str[50];int lowbit(int x){ return x&(-x);}/******************************更新********************************/void update(int i, int v){ while(i <= len){ a[i] += v; i += lowbit(i); }}/*****************************求和******************************/int sum(int i){ int sum = 0; while(i > 0){ sum += a[i]; i -= lowbit(i); } return sum;}int main(){ int T, v; scanf("%d", &T); for(int i = 1; i <= T; i++){ memset(a, 0, sizeof(a)); scanf("%d", &len); for(int j = 1; j <= len; j++){ scanf("%d", &v); update(j, v); } printf("Case %d:\n", i); while(scanf("%s", str)){ if(str[0] == 'E') break; int x, y; scanf("%d%d", &x, &y); if(str[0] == 'A') update(x, y); else if(str[0] == 'S') update(x, -y); else printf("%d\n", sum(y)-sum(x-1)); } } return 0;}
版权声明：本文博主原创文章，博客，未经同意不得转载。