线段树点更新区间和 模板

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <queue> #include <math.h> #define mem(a) memset(a,0,sizeof(a)) #define L(u) (u<<1) #define R(u) (u<<1|1) using namespace std; const int maxn = 50009; struct Nodes { int l,r;//区间 int sum;//区间和 } node[maxn<<2];//大约需要开数据总数四倍的数组 int A[maxn]; void Pushup(int u)//维护当前线段和 { node[u].sum = node[L(u)].sum + node[R(u)].sum; return ; } void Build (int u,int left,int right)//创建一颗线段树 { node[u].l = left,node[u].r = right;//线段端点 if (node[u].l == node[u].r)//如果更新到叶子节点，就让该线段的区间和等于该点的值 { node[u].sum = A[left]; return ; } int mid = (node[u].l + node[u].r)>>1;//每个父节点分成两个子节点的区间。 Build (L(u),left,mid);//递归两个子节点 Build (R(u),mid+1,right); Pushup(u);//维护该线段的sum是该线段的区间和。 } void Update(int u,int pos,int val)//点更新操作。（给某个点增加或者减少某个值，更改值同理可得。） { if (node[u].l==node[u].r)//如果更新到叶子节点就直接更改该节点的值。 { node[u].sum += val; return ; } int mid = (node[u].l + node[u].r)>>1; //看需要更新的节点的位置在当前节点的左子树还是在当前节点的右子树，判断，然后递归修改值。 if (pos <= mid) Update(L(u),pos,val); else Update(R(u),pos,val); Pushup(u);//递归操作之后，维护当前节点是当前线段的区间和。 } int Query(int u,int left,int right)//查询操作 { if (left <= node[u].l&&node[u].r <= right) return node[u].sum; //如果当前所在的区间是需要查询的区间的子区间，那么直接返回该区间的区间和就OK. int mid = (node[u].l + node[u].r)>>1; if (right <= mid) return Query(L(u),left,right);//递归查询子区间，求区间和。 else if (left > mid) return Query(R(u),left,right); else return (Query(L(u),left,mid) + Query(R(u),mid+1,right)); Pushup(u);//可有可无。 } int main () { #ifndef ONLINE_JUDGE freopen("1","r",stdin); #endif // ONLINE_JUDGE ios_base::sync_with_stdio(false);//cin cout的输入输出与scanf printf同步，数据量大时省时间。 cin.tie(0); int T,n,m,t,i,x,add,a,b; char s[10]; scanf("%d",&T); for(t = 1; t <= T; t++) { scanf("%d",&n); printf("Case %d:\n",t); for(i = 1; i <= n; i ++) { scanf("%d",&A[i]); } Build(1,1,n); while(1) { scanf("%s",s); if(strcmp(s,"Add") == 0) { scanf("%d%d",&x,&add); Update(1,x,add); } else if(strcmp(s,"Sub") == 0) { scanf("%d%d",&x,&add); Update(1,x,-add); } else if(strcmp(s,"Query" ) == 0) { scanf("%d%d",&a,&b); printf("%d\n",Query(1,a,b)); } else { break; } } } return 0; }