HDU 1166 적군 포진 (선분 트 리 버 전)

이 문 제 는 전에 나무 모양 배열 로 썼 는데, 최근 에는 선분 트 리 를 공부 하면 서 선분 트 리 로 다시 썼 다.
새로운 데이터 구 조 를 배우 기 전에 가장 중요 한 것 은 그 구조 가 어떤 모습 인지 이해 하 는 것 이다. 이것 은 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:
",++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
",query(p,v,1,n,1));
        }
    }
    return 0;
}