题目链接：
题目大意：给出n个点，每个点有一个值，现在有三种操作，
1.在i点加上j
2.在i点减去j
3.查询i，j区间总和
这其实是一道非常裸的线段树，但是我还是卡了好久，结果最后发现竟然是自己的freopen和代码习惯惹的祸。这道题我用了两种方法，一种是比较常规的版本，一种是不用结构体的静态树
首先来看一个常规的代码（带结构体）
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #define maxn 500005 10 #define lson pos<<1 11 #define rson pos<<1|1 12 using namespace std; 13 14 struct node{ 15 int l,r,sum; 16 }e[maxn]; 17 18 int n,a[maxn],t; 19 20 void build(int l,int r,int pos) 21 { 22 e[pos].l=l;e[pos].r=r; 23 if(l==r)e[pos].sum=a[l]; 24 else{ 25 int mid=(l+r)>>1; 26 build(l,mid,lson);build(mid+1,r,rson); 27 e[pos].sum=e[lson].sum+e[rson].sum;//pushup操作 28 } 29 } 30 31 void add(int k,int x,int pos) 32 { 33 int l=e[pos].l,r=e[pos].r; 34 e[pos].sum+=x; 35 int mid=(l+r)>>1; 36 if(l==r&&l==k) 37 { 38 return; 39 }else{ 40 if(k<=mid)add(k,x,lson); 41 else add(k,x,rson); 42 } 43 } 44 45 void sub(int k,int x,int pos) 46 { 47 e[pos].sum-=x; 48 int l=e[pos].l;int r=e[pos].r; 49 int mid=(l+r)>>1; 50 if(l==r&&l==k) 51 { 52 return; 53 }else{ 54 if(k<=mid)sub(k,x,lson); 55 else sub(k,x,rson); 56 } 57 } 58 59 int summ; 60 void query(int l,int r,int pos) 61 { 62 if(e[pos].l>=l&&e[pos].r<=r){ 63 summ+=e[pos].sum; 64 } 65 else{ 66 int mid=(e[pos].l+e[pos].r)/2; 67 if(mid>=r){ 68 query(l,r,lson); 69 } 70 else{ 71 if(l>mid)query(l,r,rson); 72 else{ 73 query(l,r,lson);query(l,r,rson); 74 } 75 } 76 } 77 } 78 79 char ch[8]; 80 int main() 81 { 82 scanf("%d",&t);int y=0; 83 while(t--) 84 { 85 y++; 86 printf("Case %d:\n",y); 87 scanf("%d",&n); 88 for(int i=1;i<=n;i++) 89 scanf("%d",&a[i]); 90 scanf("\n"); 91 build(1,n,1); 92 93 while(1) 94 { scanf("%s",ch); 95 if(ch[0]=='E')break; 96 if(ch[0]=='A'){ 97 int x,y; 98 scanf("%d%d",&x,&y); 99 add(x,y,1);100 }101 if(ch[0]=='S')102 {103 int x,y;104 scanf("%d%d",&x,&y);105 sub(x,y,1);106 }107 if(ch[0]=='Q')108 { summ=0;109 int x,y;110 scanf("%d%d",&x,&y);111 query(x,y,1);112 printf("%d\n",summ);113 }114 115 }116 117 118 } 119 }
打完这个代码其实不难发现，每一个pos（节点）的左右区间其实是固定的，而且还可以推出来，画个图分析一下
红色数字为pos，黑色为l，r，可以发现其实pos对应的l，r不会变，就是一棵静态树，
所以我们就可以不用结构体，只用看一个sum数组就可以解决了
来看一看代码
1 #include2 #include 3 #include 4 #include 5 #include 6 #define lson pos<<1 7 #define rson pos<<1|1 8 #define maxn 500005 9 using namespace std;10 11 int sum[maxn<<2];12 int a[maxn],n,m,t;13 char ch[10];14 15 void pushup(int pos)16 {17 sum[pos]=sum[lson]+sum[rson];18 }19 20 void build(int l,int r,int pos)21 {22 if(l==r){sum[pos]=a[l];return;}23 int mid=(l+r)/2;24 build(l,mid,lson);25 build(mid+1,r,rson);26 pushup(pos);27 }28 29 void add(int k,int x,int pos,int l,int r)30 {31 if(l==r){sum[pos]+=x;return;}32 int mid=(l+r)>>1;33 if(k<=mid)add(k,x,lson,l,mid);34 else add(k,x,rson,mid+1,r);35 pushup(pos);36 }37 38 void sub(int k,int x,int pos,int l,int r)39 {40 if(l==r){sum[pos]-=x;return;}41 int mid=(l+r)>>1;42 if(k<=mid)sub(k,x,lson,l,mid);43 else sub(k,x,rson,mid+1,r);44 pushup(pos);45 }46 47 int query(int al,int ar,int l,int r,int pos)48 {49 if(al<=l&&r<=ar)return sum[pos];50 int mid=(l+r)>>1,s=0;51 if(al<=mid)s+=query(al,ar,l,mid,lson);52 if(ar>mid) s+=query(al,ar,mid+1,r,rson);53 return s;54 }55 56 int main()57 { 59 scanf("%d",&t);int y=0;60 while(t--)61 {62 cout<<"Case "<<++y<<":"<
PS：诸位OIer打代码特别是函数时要注意声明的左右点和pos的位置关系，要一一对应，不然就像我一样会调试一天