本文主要是介绍hdu 1166线段树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
线段树的一般模板，1.结构体数组tree来存储 2.线段树的构建函数buildTree 3.改变元素值函数update 4.查询区间内总和的函数query全部使用递归来实现
######################################################################include<iostream>
#include<stdio.h>
#include<string>
#include<string.h>using namespace std;const int maxn = 50050;
int ans;struct node{int left, right, sum;int mid(){return (left+right)/2;}
}tree[maxn*4];void buildTree(int left, int right, int rt)
{tree[rt].left = left;tree[rt].right = right;if(left == right){cin >> tree[rt].sum;return ;}int mid = tree[rt].mid();buildTree(left, mid, rt*2);buildTree(mid+1, right, rt*2+1);tree[rt].sum = tree[rt*2].sum + tree[rt*2+1].sum;
}void query(int left, int right, int rt, int L, int R)
{if(L <= left && R >= right){ans += tree[rt].sum;return ;}int mid = tree[rt].mid();if(R <= mid)query(left, mid, rt*2, L, R);else if(L > mid)query(mid+1, right, rt*2+1, L, R);else{query(left, mid, rt*2, L, R);query(mid+1, right, rt*2+1, L, R);}
}void update(int left, int right, int rt, int pos, int add)
{if(left == right){tree[rt].sum += add;return ;}int mid = tree[rt].mid();if(pos <= mid)update(left, mid, rt*2, pos, add);else update(mid+1, right, rt*2+1, pos, add);tree[rt].sum = tree[rt*2].sum + tree[rt*2+1].sum;
}int main()
{int T, N, temp;int a, b, Case = 0;string str;scanf("%d",&T);while(T --){cin >> N;buildTree(1, N, 1);Case ++;printf("Case %d:\n",Case);while( cin >> str ){if(str == "End") break;scanf("%d%d", &a, &b);if(str == "Add"){update(1, N, 1, a, b);}else if(str == "Sub"){update(1, N, 1, a, -b);}else {ans = 0;query(1, N, 1, a, b);printf("%d\n",ans); }}}return 0;
}这篇关于hdu 1166线段树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
