該題之前用樹狀數組寫過， 最近在學習線段樹， 用線段樹重新寫了一遍。 在學習一種新的數據結構之前， 最重要的是要理解其結構是什么樣子的， 這個可以參照《算法競賽入門經典-訓練指南》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; } ~~~