/**
*模版原题：HDU 1754
*线段树-单点加减
*区间求最值
*/
#include <cstdio>
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
const int maxn =
55555;
int sum[maxn<<
2];
void PushUP(
int rt)
{
sum[rt] = sum[rt<<
1] + sum[rt<<
1|
1];
// sum[rt]=sum[rt*2]+sum[rt*2+1];
}
//建立线段树；
//l,r为该点包含的范围 rt为该点所在数组的下标
void build(
int l,
int r,
int rt)
{
if (l == r)
//当查询到的点为最终的单个点时；
{
scanf("%d",&
sum[rt]);
return ;
}
int m = (l + r) >>
1;
//m=(l+r)/2;
build(lson);
build(rson);
PushUP(rt); //回溯更新父节点
}
//单点修改（加）
//p为待更新点下标 add为待更新参数值 l,r,rt为查找范围和范围内的最高祖先
void update(
int p,
int add,
int l,
int r,
int rt)
{
if (l == r)
//如果查找到该点为最终单点，执行更新
{
sum[rt] +=
add;
return ;
}
int m = (l + r) >>
1;
//如非最终点，取范围中间值判断目标点是在该点左子树还是右子树
if (p <=
m) update(p , add , lson);
else update(p , add , rson);
PushUP(rt); //回溯更新父节点
}
//查询线段树
//L R为输入的区间 l r为查找范围和范围内的最高祖先
int query(
int L,
int R,
int l,
int r,
int rt)
{
if (L <= l && r <= R)
//如果预先出现某节点范围属于原始L R内，赋予该节点值。不再查询该节点的子节点
{
return sum[rt];
}
int m = (l + r) >>
1;
//如为如上退出，这判断L R 包含的区域是在该点左右哪子树
int ret =
0;
if (L <= m) ret +=
query(L , R , lson);
if (R > m) ret +=
query(L , R , rson);
return ret;
}
int main()
{
int T , n;
scanf("%d",&
T);
for (
int cas =
1 ; cas <= T ; cas ++
)
{
printf("Case %d:\n",cas);
scanf("%d",&
n);
//线段树起点下标由1开始到n
build(
1 , n ,
1);
char op[
10];
while (scanf(
"%s",op))
{
if (op[
0] ==
'E')
break;
int a , b;
scanf("%d%d",&a,&
b);
if (op[
0] ==
'Q')
printf("%d\n",query(a , b ,
1 , n ,
1));
else if (op[
0] ==
'S')
update(a , -b ,
1 , n ,
1);
else
update(a , b , 1 , n ,
1);
}
}
return 0;
}
转载于:https://www.cnblogs.com/mochenmochen/p/5156771.html
