題意：不用多說了……
思路：一個入門的線段樹插點問線，解釋在代碼裡
AC代碼：
[cpp]
/*
線段樹 -插點問線：
1：線段樹中存的是對應區間的和。
2：某一點 更新值時，將該點的父節點（依次向上直到根節點）都更新
3：查詢時 找到在線段數中分成對應的各個小區間，求sum即可。
*/
#include<stdio.h>
#include<string.h>
#define Max 4*100000
#define LL(a) a<<1; //2*A
#define RR(a) a>>1|1; //2*a+1
#define Mid(x,y) (x+y)>>1 //(x+y)/2
int A[Max],cnt,ans;
struct hello
{
int l;
int r;
int sum;
}tree[Max];
void Build_tree(int l,int r,int t) // l,r 表示區間，t表示 區間節點
{
int x;
tree[t].l=l;
tree[t].r=r;
tree[t].sum=0;
if(l==r)
{
// tree[t].sum=A[l];
while(t!=0)
{
tree[t].sum+=A[l];
t/=2;
}
return ;
}
x=Mid(l,r);
Build_tree(l,x,2*t);
Build_tree(x+1,r,2*t+1);
}
void Updata_tree(int l,int r,int t) // l r 表示要更新的區間，t表示當前節點
{
if(tree[t].l==l&&tree[t].r==r)
{
while(t!=0)
{
tree[t].sum+=cnt;
t/=2;
}
return ;
}
int x=Mid(tree[t].l,tree[t].r);
if(x>=r)
Updata_tree(l,r,2*t);
else if(x+1<=l)
Updata_tree(l,r,2*t+1);
else
{
Updata_tree(l,x,2*t);
Updata_tree(x+1,r,2*t+1);
}
}
void Query_tree(int l,int r,int t) // l r 表示要查詢的區間 t表示當前節點
{
//printf("inin---------------\n");
if(tree[t].l==l&&tree[t].r==r)
{
//printf("outout------\n");
ans+=tree[t].sum;
return ;
}
int x=Mid(tree[t].l,tree[t].r);
if(x>=r)
Query_tree(l,r,2*t);
else if(x+1<=l)
Query_tree(l,r,2*t+1);
else
{
Query_tree(l,x,2*t);
Query_tree(x+1,r,2*t+1);
}
}
int main()
{
int i,j,n,m,ncase;
scanf("%d",&ncase);
for(n=1;n<=ncase;n++)
{
printf("Case %d:\n",n);
scanf("%d",&m);
for(i=1;i<=m;i++)
scanf("%d",&A[i]);
Build_tree(1,m,1);
char str[100];
while(scanf("%s",str)&&str[0]!='E')
{
int x,y;
if(str[0]=='S')
{
scanf("%d%d",&x,&cnt);
cnt=-cnt;
Updata_tree(x,x,1);
}
else if(str[0]=='A')
{
scanf("%d%d",&x,&cnt);
Updata_tree(x,x,1);
}
else if(str[0]=='Q')
{
scanf("%d%d",&x,&y);
ans=0;
Query_tree(x,y,1);
printf("%d\n",ans);
}
}
}
}
