线段树的一般模板，1.结构体数组tree来存储  2.线段树的构建函数buildTree  3.改变元素值函数update   4.查询区间内总和的函数query

全部使用递归来实现

#####################################################################

#include
  
   
#include
   
     #include
    
      #include
     
       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; }