链接：
自己第一次在没有看题解AC出来的线段树，写的可能不是太好，再贴个学长的代码，学习一下
发现自己的Update部分写了很多废话，直接用a[r]里的值就好了，我还传了那么多的值，真傻！
代码：
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 7 #define Lson r<<1 8 #define Rson r<<1|1 9 10 const int N = 1e6+5; 11 12 struct SegmentTree 13 { 14 int L, R; 15 int sum, e; 16 int Mid() 17 { 18 return (R+L)>>1; 19 } 20 }a[N<<2]; 21 22 void BuildSegTree(int r, int L, int R) 23 { 24 a[r].L=L, a[r].R=R; 25 a[r].e=0; 26 27 if(L==R) 28 { 29 scanf("%d", &a[r].sum); 30 return ; 31 } 32 33 BuildSegTree(Lson, L, a[r].Mid()); 34 BuildSegTree(Rson, a[r].Mid()+1, R); 35 36 a[r].sum = a[Lson].sum + a[Rson].sum; 37 } 38 39 void Update(int r, int L, int R, int i, int e) 40 { 41 a[r].sum += e; 42 43 if(L==R && L==i) 44 return ; 45 46 if(i<=a[r].Mid()) 47 Update(Lson, L, a[r].Mid(), i, e); 48 else if(i>a[r].Mid()) 49 Update(Rson, a[r].Mid()+1, R, i, e); 50 } 51 52 int Query(int r, int L, int R) 53 { 54 if(a[r].L==L && a[r].R==R) 55 return a[r].sum; 56 57 if(R<=a[r].Mid()) 58 return Query(Lson, L, R); 59 else if(L>a[r].Mid()) 60 return Query(Rson, L, R); 61 else 62 { 63 long long Lsum = Query(Lson, L, a[r].Mid()); 64 long long Rsum = Query(Rson, a[r].Mid()+1, R); 65 66 return Lsum + Rsum; 67 } 68 } 69 70 int main() 71 { 72 int t, k=1; 73 scanf("%d", &t); 74 while(t--) 75 { 76 int n; 77 scanf("%d", &n); 78 BuildSegTree(1, 1, n); 79 80 char s[20]; 81 int L, R, i, e; 82 83 printf("Case %d:\n", k++); 84 85 while(scanf("%s", s), strcmp(s, "End")) 86 { 87 if(strcmp(s, "Query")==0) 88 { 89 scanf("%d%d", &L, &R); 90 printf("%d\n", Query(1, L, R)); 91 } 92 else if(strcmp(s, "Add")==0) 93 { 94 scanf("%d%d", &i, &e); 95 Update(1, 1, n, i, e); 96 } 97 else 98 { 99 scanf("%d%d", &i, &e);100 Update(1, 1, n, i, -e);101 }102 }103 }104 return 0;105 }
学长的代码：
1 #include2 #include 3 #include 4 5 #define maxn 50005 6 7 struct node 8 { 9 int L, R, sum;//左右子树,sum记录区间和10 int Mid(){ return (L+R)/2;}11 }tree[maxn*4];//为了保险起见一般定义是四倍12 int val[maxn];//保存每个阵地原来的人数13 14 void Build(int root, int L, int R)//建树15 {16 tree[root].L = L, tree[root].R = R;17 18 if(L == R)19 {20 tree[root].sum = val[L];21 return ;22 }23 24 Build(root<<1, L, tree[root].Mid());//<<1 运算符相当于乘上 2，因为是数往左移一位25 Build(root<<1|1, tree[root].Mid()+1, R);//|1， 因为左移后最后一位是0， 所以与1进行|相当于+126 27 tree[root].sum = tree[root<<1].sum+tree[root<<1|1].sum;//区间和等于左右区间的和28 }29 //k表示需要更新的点，e表示需要更新的值30 void Insert(int root, int k, int e)31 {32 tree[root].sum += e;33 if(tree[root].L == tree[root].R)34 return ;35 36 if(k <= tree[root].Mid())37 Insert(root<<1, k, e);38 else39 Insert(root<<1|1, k, e);40 }41 //查询区间LR的和42 int Query(int root, int L, int R)43 {44 if(tree[root].L == L && tree[root].R == R)45 return tree[root].sum;46 47 //如果在左子树区间48 if(R <= tree[root].Mid())49 return Query(root<<1, L, R);50 else if(L > tree[root].Mid())//如果在右子树区间51 return Query(root<<1|1, L, R);52 else53 { //在左右子树54 int Lsum = Query(root<<1, L, tree[root].Mid());55 int Rsum = Query(root<<1|1, tree[root].Mid()+1, R);56 57 return Lsum + Rsum;58 }59 }60 61 int main()62 {63 int T, t=1;64 65 scanf("%d", &T);66 67 while(T--)68 {69 int i, N, x, y;70 71 scanf("%d", &N);72 73 for(i=1; i<=N; i++)74 scanf("%d", &val[i]);75 Build(1, 1, N);76 77 char s[10];78 79 printf("Case %d:\n", t++);80 81 while(scanf("%s", s), s[0] != 'E')82 {83 scanf("%d%d", &x, &y);84 85 if(s[0] == 'A')86 Insert(1, x, y);87 else if(s[0] == 'S')88 Insert(1, x, -y);89 else90 {91 int ans = Query(1, x, y);92 printf("%d\n", ans);93 }94 }95 }96 97 return 0;98 }