HDOJ(HDU).1166 敌兵布阵 (ST 单点更新 区间求和)
题意分析
根据数据范围和询问次数的规模，应该不难看出是个数据结构题目，题目比较裸。题中包括以下命令：
1.Add(i,j)表示 a[i]+=j;
2.Sub(i,j)表示 a[i]-=j;
3.Query(i,j)表示 Σ(a[i],a[j])。
Add操作和Sub操作分别是单点更新，Query是区间求和。题目比较裸，但是在写ST模板的时候还是不能一次写对，出的错记录如下:
1.由于对模板的不熟悉，rt打成rn导致编译不能通过；
2.对于区间询问的函数不熟悉，判断的条件应该是L>=l&&r<=R,这表示当前节点所表示的区间[l,r]全部包含在要查询的区间[L,R]内，故应该直接返回其节点的值以便累加。
代码总览
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define nmax 50005
using namespace std;
int a[nmax],add[nmax<<2],sum[nmax<<2];
void pushup(int rt)
{
sum[rt] = sum[rt<<1]+sum[rt<<1|1];
}
void pushdown(int rt, int ln, int rn)
{
if(add[rt]){
add[rt<<1]+=add[rt];
add[rt<<1|1]+=add[rt];
sum[rt<<1]+=add[rt]*ln;
sum[rt<<1|1]+=add[rt]*rn;
add[rt] = 0;
}
}
void build(int l ,int r, int rt)
{
if(l == r){
sum[rt] = a[l];
return;
}
int m = (l+r)>>1;
build(l,m,rt<<1);
build(m+1,r,rt<<1|1);
pushup(rt);
}
void updatep(int L, int c, int l, int r, int rt)
{
if(l == r){
sum[rt]+=c;
return;
}
int m = (l+r)>>1;
pushdown(rt,m-l+1,r-m);
if(L<=m) updatep(L,c,l,m,rt<<1);
else updatep(L,c,m+1,r,rt<<1|1);
pushup(rt);
}
void updatei(int L, int R, int c, int l, int r, int rt)
{
if( l>=L && r<= R){
sum[rt]+=c*(r-l+1);
add[rt]+=c;
return;
}
int m = (l+r)>>1;
pushdown(rt,m-l+1,r-m);
if(L<=m) updatei(L,R,c,l,m,rt<<1);
if(R>m) updatei(L,R,c,m+1,r,rt<<1);
pushup(rt);
}
int query(int L, int R, int l ,int r, int rt)
{
if(L<=l && r<=R){
return sum[rt];
}
int m = (l+r)>>1;
pushdown(rt,m-l+1,r-m);
int ANS =0;
if(L<=m) ANS+= query(L,R,l,m,rt<<1);
if(R>m) ANS+=query(L,R,m+1,r,rt<<1|1);
return ANS;
}
int main()
{
//freopen("in.txt","r",stdin);
int t;
scanf("%d",&t);
for(int i =1 ;i<=t; ++i){
char com[10];
printf("Case %d:\n",i);
int n;
scanf("%d",&n);
for(int j =1 ;j<=n;++j) scanf("%d",&a[j]);
build(1,n,1);
while(scanf("%s",com) && com[0] != 'E'){
if(com[0] == 'Q'){
int L,R;
scanf("%d%d",&L,&R);
printf("%d\n",query(L,R,1,n,1));
}else if(com[0] == 'A'){
int L,c;
scanf("%d%d",&L,&c);
updatep(L,c,1,n,1);
}else if(com[0] == 'S'){
int L,c;
scanf("%d%d",&L,&c);
updatep(L,-c,1,n,1);
}
}
}
return 0;
}