這道題題意很簡單就是如果字元為Q那麼就詢問[i,j]區間的和，如果為U,那麼就更新i點值為j；
線段樹基礎題目；
那什麼是線段樹？
我自己是這樣了解的：
線段是本質上就是一個區間的映射為一個節點+二叉樹的後序周遊；著名的RMQ問題就是很基礎的線段樹操作；
幾何了解：
可以發現線段樹就是把區間分塊，然後存下對應區間的問題規模（比如這個區間Max或者Min或者Sum或者平均值。。等等）；
可以很明顯發現這個二叉樹的子葉節點就是L==R（這裡要很明白，因為對後面的遞歸很有幫助！！）
是以這個問題就很容易了，我隻需要把問題規模存下來，然後遞歸一遍就OK了（如果你對二叉樹的三種周遊方式很熟悉，了解這個線段樹的遞歸就很容易了）；
線段樹的本質就是這個了；
但是如何Build和操作呢？
建樹時利用二叉樹的後序周遊+Tree來循序存儲線段樹的節點對應的值；
意思就是：
可以很明顯發現子節點和父節點的index的關系；是以利用這個關系我就可以Build了；
也就是（這裡就建立好了線段樹的邏輯存儲結構了）：
void Build(int root,int L,int R){//建樹
if(L==R){//當左端點==有端點時說明到了葉結點
scanf("%d",&Tree[root]);//根據節點編号輸入；
//cout<<":"<<Tree[L]<<" ";
return;
}else{
int mid=(L+R)/2;//二叉樹的後續周遊用來建立樹，至于為什麼看看書就可以了解了；
Build(2*root,L,mid);
Build(2*root+1,mid+1,R);
Tree[root]=Tree[root*2]+Tree[root*2+1];
//cout<<Tree[root]<<" ";
}
}
然後線段樹的單點更新，應該如何操作呢？肯定是遞歸下去，因為單點更新肯定會給index是以我按照index和區間[L,R]的包含關系進行遞歸知道L==R時說明找到了該點，然後就可以修改；但是為什麼呢？原因很簡單我可以發現線段樹有個這樣的特點：
就是它的子葉節點對應的區間（可以很明顯發現哦，根據上面的圖）其實就是元素在原數組的下标（因為這裡我簡化記憶體沒有寫成Tree[root]=a[L]，而是直接輸入的）；這點很重要！！是以根據這個我就可以遞歸找到端點然後改值，然後遞歸上去把父節點的值也跟着改動；
是以思路就是這樣滴(如果不能了解遞歸的建議把資料結構的樹的知識了解了解就好了，嘻嘻)；
本題的AC代碼：
#include<iostream>
#include<string>
#include<cstdio>
#include<set>
#include<map>
using namespace std;
const int maxn=5e4+10;
int Tree[maxn<<2],T,n;
int ans[maxn];
void Build(int root,int L,int R){//建樹
if(L==R){//遞歸建二叉樹
scanf("%d",&Tree[root]);
//cout<<":"<<Tree[L]<<" ";
return;
}else{
int mid=(L+R)/2;
Build(2*root,L,mid);
Build(2*root+1,mid+1,R);
Tree[root]=Tree[root*2]+Tree[root*2+1];
//cout<<Tree[root]<<" ";
}
}
int Query(int root,int L,int R,int l,int r){//區間和 //其實這個代碼寫法并不好！隻不過比較好了解些
if(l<=L&&R<=r)return Tree[root];//如果對于的區間重合時，那麼就表示這個區間剛好對應值
int mid=(L+R)/2;//這裡用筆算一下就知道了；
if(r<=mid) return Query(2*root,L,mid,l,r);//如果整個區間都在系統區間的mid的左邊
if(l>mid) return Query(2*root+1,mid+1,R,l,r);//如果整個區間都在系統區間的mid的右邊
return Query(2*root,L,mid,l,mid)+Query(2*root+1,mid+1,R,mid+1,r);//分兩邊走
}
void updatapoint(int root,int L,int R,int x,int val){//單點更新
if(L==R){//到了葉結點
Tree[root]+=val;return ;
}
int mid=(L+R)/2;
if(x<=mid)updatapoint(2*root,L,mid,x,val);//這裡可以這樣了解：如果x在mid的左邊，那麼我就去左邊區間找
else updatapoint((root<<1)|1,mid+1,R,x,val);//如果x在mid的右邊，那麼我就去右邊區間找
Tree[root]=Tree[root<<1]+Tree[(root<<1)|1];//然後求父節點對應的子節點的和，這裡的的2*root和2*root+1我用位移運算符+邏輯運算符表示的
}
int main(){
scanf("%d",&T);
char s[10]; //注意這裡題上說一個字元，但是我也不知道為什麼用char s就wa了，隻好改為數組了；估計應該是讀檔案的時候的問題
int a,b;
for(int i=1;i<=T;i++){
int g=0;
scanf("%d",&n);
Build(1,1,n);//建樹
while(scanf("%s",s)){
if(s[0]=='E')break;
scanf("%d %d",&a,&b);
if(s[0]=='A'){
updatapoint(1,1,n,a,b);
}else if(s[0]=='S'){
updatapoint(1,1,n,a,-b);
}else{
ans[g++]=Query(1,1,n,a,b);
}
}
printf("Case %d:\n",i);
for(int j=0;j<g;j++)printf("%d\n",ans[j]);
}
return 0;
}