HDU 1166 敌兵布阵（线段树版）
最后更新于：2022-04-01 15:53:02
该题之前用树状数组写过， 最近在学习线段树， 用线段树重新写了一遍。
在学习一种新的数据结构之前， 最重要的是要理解其结构是什么样子的， 这个可以参照《算法竞赛入门经典-训练指南》P199页。
比较重要的是理解好几个变量：
1.每个结点有一个编号。 这个编号对应了其所统治的区间， 我们从线段树的祖先结点开始从上到下， 从左到右的顺序给所有结点编号，这样， 编号为i的结点其左右结点的编号就是2i和2i+1。
2.我们每次计算的m = (l + r) >> 1是当前区间[l, r]的中点， 为的是将当前区间不重复的分成两个子区间。 然后这两个子区间的结点编号又分别对应了2i 和 2i+1。
这样我们每次从祖先结点&&最大区间开始进行， 采用分治的思想， 就可以快速的进行计算了， 另外在更新操作的时候利用线段树的特点，每次递归结束之后顺带更新当前结点的值。
学习建议： 第一遍可以模仿， 建议模仿多个版本， 自己组建一个自己喜欢的代码风格，这样也有助于理解和记忆。
明白原理和过程之后， 以后尽量不要看模板， 自己手写出来， 这样可以加深理解。
细节参见代码：
~~~
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 1000000000;
const int maxn = 50000+10;
int T,p,v,n,m,kase=0,sum[maxn<<2];
void push_up(int o) {
sum[o] = sum[o<<1] + sum[o<<1|1];
}
void build(int l, int r, int o) {
int m = (l + r) >> 1;
if(l == r) {
scanf("%d",&sum[o]); return ;
}
build(l, m, o<<1);
build(m+1, r, o<<1|1);
push_up(o);
}
void update(int p, int add, int l, int r, int o) {
int m = (l + r) >> 1;
if(l == r) {
sum[o] += add; return ;
}
if(p <= m) update(p, add, l, m, o<<1);
else update(p, add, m+1, r, o<<1|1);
push_up(o);
}
int query(int L, int R, int l, int r, int o) {
int m = (l + r) >> 1, ans = 0;
if(L <= l && r <= R) {
return sum[o];
}
if(m >= L) ans += query(L, R, l, m, o<<1);
if(m+1 <= R) ans += query(L, R, m+1, r, o<<1|1);
return ans;
}
int main() {
scanf("%d",&T);
while(T--) {
scanf("%d",&n);
build(1,n,1);
char s[10];
printf("Case %d:\n",++kase);
while(~scanf("%s",s)) {
if(s[0] == 'E') break;
scanf("%d%d",&p,&v);
if(s[0] == 'A') update(p,v,1,n,1);
else if(s[0] == 'S') update(p,-v,1,n,1);
else printf("%d\n",query(p,v,1,n,1));
}
}
return 0;
}
~~~