本文共 3481 字，大约阅读时间需要 11 分钟。
线段树就是区间的查找，如果区间不是当前线段树节点的区间，需要划分为左、右，再递归查找
#include#include #include using namespace std;const int maxn = 55555;int a[maxn];int tree[maxn << 2];//节点数是区间的4倍void pushUp(int curr) { tree[curr] = tree[2*curr] + tree[2*curr+1];}void buidTree(int left, int right, int curr) {//本节点在数组中的位置是curr;本节点的左边界是left，右边界是right if (left == right) { tree[curr] = a[left]; return; } int m = left + (right - left)/2; // if (m >= left) buidTree(left,m,2*curr); // if (m+1<=right) buidTree(m+1,right,2*curr + 1); pushUp(curr);}void update(int p, int add, int left, int right, int curr) {//第p个数，增加add;当前节点是curr,左是left，右是right;先找到p在哪个范围内,一定要找到精确的小范围，然后大范围是由小范围组合而成 if (left == right) { tree[curr] += add; return; } int m = left + (right - left)/2; if (p <= m) update(p,add,left,m,2*curr); else update(p,add,m+1,right,2*curr + 1); pushUp(curr);}int query(int ql, int qr, int currLeft, int currRight, int curr) {//查找区间[ql,qr] if (ql <= currLeft && qr >= currRight) { return tree[curr]; } int m = currLeft + (currRight - currLeft)/2; int sum = 0; if (ql <=m) sum = query(ql,qr,currLeft,m,2*curr); if (qr >m) sum += query(ql,qr,m+1,currRight,2*curr+1); return sum;}int main() { int t,n; scanf("%d", &t); for (int i = 0; i < t ; ++i ) { printf("Case %d:\n",i+1); scanf("%d",&n); memset(a,0,sizeof(a)); for (int j = 1; j <= n; ++j ) scanf("%d",a + j); buidTree(1,n,1); char op[10]; while(scanf("%s",&op)) { if (op[0] == 'E') break; int a1,a2; scanf("%d%d",&a1,&a2); if (op[0] == 'Q') printf("%d\n",query(a1,a2,1,n,1)); else if(op[0] == 'S') update(a1,-a2,1,n,1); else update(a1,a2,1,n,1); } }}
#include#include using namespace std;const int maxn = 55555;int a[maxn];int tree[maxn<<2];//线段树的每一个叶子节点就是a中的元素，还有其他的非叶子节点，应该需要2*maxn+1个元素void pushUp(int ind) { tree[ind] = tree[2*ind] + tree[2*ind+1];}void buildTree(int left, int right, int ind) {//找到叶子节点相应的位置, ind是这个节点的编号//left 和 right是这个节点所对应的范围 if (left == right) { tree[ind] = a[left]; return; } int mid = (left + right)/2; buildTree(left, mid, 2*ind); buildTree(mid+1, right, 2*ind + 1); pushUp(ind);}int query(int beg, int end , int left, int right, int ind){// beg, end是要查询的区间；left和right是这个节点的范围 if (beg<=left && end >= right) return tree[ind]; int mid = (left + right) / 2; int l = 0, r = 0; if (mid >= beg) l = query(beg,end,left,mid, 2*ind); if (mid < end) r = query(beg,end,mid +1,right, 2*ind+1); return l+ r;}void update(int pos, int value, int left, int right, int ind) { if(left == right) { tree[ind] += value; return; } int mid = (left + right) / 2; if (mid >=pos) update(pos, value, left, mid, 2*ind); else update(pos,value, mid + 1, right, 2*ind+1); pushUp(ind);}int main() { int t,n; scanf("%d", &t); for (int i = 0; i < t ; ++i) { printf("Case %d:\n", i + 1); scanf("%d", &n); memset(a,0,sizeof(a)); for(int j = 1; j <= n; ++j) scanf("%d", a + j); buildTree(1,n, 1); char op[10]; while (scanf("%s", op)){ if (op[0] == 'E') break; int a1, a2; scanf("%d%d", &a1,&a2); if (op[0] == 'Q') printf("%d\n", query(a1, a2,1,n,1)); else if(op[0] == 'S') update(a1,-a2,1,n,1); else update(a1,a2,1,n,1); } }}
转载地址：http://tteti.baihongyu.com/